- OK, this is it. It's time for a MAJOR rewrite of the game engine interface. The current design of b0rken inheritance hierarchy is starting to cause nightmares with the network code. - players and game engines should be separate entities. Game engines contain players, but players (i.e. the current AI player) is NOT a "type of" game engine. Should have a separate player class which can then contain stuff like scores, nicknames, etc.. - players and interfaces are distinct things; the "human" player should simply be derived from a base player class in such a way that it connects to the interface. So XAtom-4 has an X11 player, textui has an ncurses player, etc.. Similarly, the AI player is its own player. Network players will just be another type of player. Interfaces should know how to work with any player type (the specialized player type for that interface can simply be an "active" class hooked off eventloop that triggers state changes in the interface; no need for special handling in the interface class itself). - game state change notification should also be expanded to cover events like round over, change of turn, etc.. Interfaces shouldn't have to keep on examining game state (although that should certainly be possible too). - Add history and playback capability - need network play! :-) - all the infrastructure is in place, just have to actually implement the network communications layer. + IDEA: + then attach textui to a fake game engine which is actually a network client that connects to the server. We'll have to change make_move() so that it will know to wait for a network response instead of asking the user for a response. (Although now it's arguable whether this should be in class interface instead of something else...) X replace textui with a network interface, which basically acts like a game server; + alternatively: + have textui able to choose between the real engine and a network engine. + textui will have two modes: standalone mode, where it gets input for both users, and network mode, where it gets input for one player from console, and the other from network. - AI: profile a search, and see if we can't optimize it by caching hdelta's. * actually, hdelta's are the least of your worries. The current big CPU hog appears to be find_legal_moves(). (Unsurprising; it has to scan the entire board to determine legal moves, and checks 6 neighbours per cell.) - implement permanent AI subprocess first! We can't cache anything if we're fork()ing each turn. We should probably just implement network play and have the AI communicate over the network layer. No need for yet another interface when one would do! - AI: make pcreated, pdestroyed weights configurable. - AI: add optional delay, so that we can (potentially) pit two AI's against each other :-) - more helpful failure codes from game::move(). Preferably we should standardize messages in the game engine instead of relying on the interface. + need to mark up board with coors so that players can see where to move; or alternatively, cycle ncurses cursor through all legal moves. + need to reset last_x,last_y and clear messages pane after restarting new game. + add color to pieces :-) + BUG: board window is one column smaller than it should be ('cos odd rows are shifted right, and require one more column to fit!) + should clearly indicate which color is which player (display player headings in the appropriate color!) + CRITICAL BUG: check_win() does NOT correctly detect wins if the last marble placed is in the center of the row of 4 instead of either end. X split off base class interface and subclass textui... then we can have a network interface, e.g. * Unnecessary. Just write a new UI. There is no compelling reason to use the same base class anyway, since the only public method is run()! X need to have independent player class (for scorekeeping and for keeping track of colors, etc) -- although maybe it's good enough to keep this in class interface. * scorekeeping is now in the game engine, as it should be. X need to clean up board representation; ideally, EMPTY_CELL should = 0, and BAD_CELL should = -1, and players' pieces should be stored as the player number. * Unnecessary. + implement new version of game, just to get a proof-of-concept of the new 2-player, 3-colors idea. * Hmm, it's harder to balance than I thought. Because of the way the colors are alternated, whoever lays down the N-1'th piece in a row will almost certainly lose; so there's not much motivation except to play defensive, in which case it's impossible to win. * Sounds like in order for this to be plausible, we're gonna have to explore the 8-color scheme. + need to implement a true multiplayer interface for game engine + game engine will be modal: DUAL (current), PEER (interface represents only a single player), WATCH (only receiving updates, not playing). + fix X11 interface to support modal engines! X should separate client from interface, maybe? X another idea: have game engine require two players to "plug in"; but we can connect the same interface to the engine twice to get the current setup + generalize class interface to allow integration with X11 client. + Clean up class atom4local mess!!! + should inherit from triboard and put all color-manipulation stuff in there. X Probably the best way is to templatize class triboard. + implement copy ctor for class triboard, so that it's easier to implement state-space search algos for the AI. + fix -a so that we can specify which player AI should be. + Implement AI player! It's a tad boring to play against myself :-P + can have configurable AI, assigning different weights to the following: + single-depth scores: + number of colors a move changes + number of propagators a move creates + number of opponent propagators a move destroys X number of opponent propagators vs. number of our propagators in resultant state space * Probably not necessary + recursive state-space searching scores: + even depths (opponent's turn): + losing move: if opponent has a winning move, assign negative score + (recursive) if all searched sub-moves result in states where opponent has a winning move, assign negative score + pruning: + instead of recursively considering all possible opponent moves, only consider those we would pick if we were in that position + winning move: if a move causes a win, pick it for sure! :-) + implemented min-max algorithm. Strangely, it seems quite inferior in terms of AI defense/offense (and takes a lot longer too!). + AI: implement a subprocess for the AI! that's what we have event loops for! + update README to explain the new 8-color game! :-) + [ncurses] should be updated to handle new 8-color system. + [ncurses] should be updated to support modal engines + make it easy to customize construction vars like PREFIX, DATADIR, etc. * can just use Cons' %ARG feature. + BUG: fix varexception so that catch(exception) will work properly!!!! + it shouldn't just work for catch(exception&) + we should probably merge the two into the base class anyway, so that we can do exception class hierarchies in a sane way. + BP: ambiguous prototypes exception(char*) and exception(char*, ...) * one solution may be to use the first char of the message as indicator (start with '@' for varexceptions). This should be minimally ugly, at least better than introducing a new parameter! + BUG: atom4 cannot be suspended with SIGSTOP; upon resume, event loop dies with Interrupted Syscall exception. (Should probably catch this condition, since it is something to be expected. Also, should probably make sure we don't die if 0 fd's are selected, which would happen when the process resumes after a SIGCONT.) + BUG: fix game engine so that it will detect stalemate (board filled up with no winners). This may be rare, but you don't want to be embarrassed when somebody actually manages to achieve that!! * Simplest way is just to maintain a counter initialized with w*h and decremented every time a non-blank piece is placed. + Write a tarball-building script! It's quite a pain to do it by hand each time. + Update the Debian package with the eventloop fix. X [ncurses] need to handle SIGWINCH. * May not need to after all; ncurses-dev comes with its own SIGWINCH handler. + [ncurses] fix non-updating board background on PuTTY. + AI: why is min-max algorithm performing so poorly?? * 'cos you did it wrong, dummy! You're supposed to evaluate the heuristic function only at leaf nodes. Otherwise the min-max propagation becomes meaningless, since it would effectively yield the path that leads to the best move (in terms of the color changes heuristic), rather than the path to the best game state. * somehow, the heuristic algorithm seems to perform best at depth=2. Trying depth=4 doesn't yield much improvement at all, and is just boringly slow. + implement REAL min-max algo!!! + IDEA: still base heuristic score on per-piece changes, but accumulate them in a struct, only evaluate them at leaf nodes. Then propagate them back using a real min-max selector. + this way, we can actually implement alpha-pruning...! + BBBBP: min-max algo still seems to perform horribly poorly. :-/ * Because you did it wrong again you dolt!!!! You forgot to invert hdelta between turns, so enemy advances were counted as gains!!! You fool!!!! + argh, something is SERIOUSLY wrong with your implementation!! It's not even detecting losing moves. X Must be that max=-min parameter, I think... * argh, something's wrong, it's not even detecting winning states... + Aha, found problem: in pick_best_move(), we treat equal scores equally; but pruned subtrees return max, which may get equal score with another non-pruned subtree. This is OK in score_opponent_move() because we use > instead of >=. But pick_best_move() uses >=, so it misidentifies a pruned branch as a good move. * FIXED!! Let's see how well it performs now... + [ncurses] do a message("") after board change happens (AI moved), so that the "it's not your turn" message doesn't continue sticking there after it *is* your turn. Or better, print a message saying what the AI moved. + AI: min-max algo is *still* not doing very well at increased search depths. At least -d2 seems to be at the same level as the original heuristic algo. -d3 and -d4 seem to be a regression though :-( Must be a problem with the heuristic value function... + Ack! Looks like there's a bug in the score propagation code. Negative scores from AI's turn doesn't change sign when propagated to opponent's turn. * FIXED!! Now the AI is pretty formidable at -d3 !! + [ncurses] After AI moves, should restore cursor pos to current board pos, else it looks misleading and player may make a mistake. + BUG: fixed incorrect negation of hdelta in AI. AI seems to be acting more rationally now. :-P * Wow, -d3 is now quite hard! + BUG: event loop postponed adds/deletes are inconsistent when the same fd is added/deleted within a single dispatch cycle. Before appending a new entry to the added/deleted list, we should check if it's already in the other list and remove it from the other list if necessary. + eventloop: we REALLY need to implement timers now. Use gettimeofday() to get the same precision select() uses. + Add timer to event loop