Debian Codegraph @

TODO

raw
1 - OK, this is it. It's time for a MAJOR rewrite of the game engine interface.
2 The current design of b0rken inheritance hierarchy is starting to cause
3 nightmares with the network code.
4 - players and game engines should be separate entities. Game engines contain
5 players, but players (i.e. the current AI player) is NOT a "type of" game
6 engine. Should have a separate player class which can then contain stuff
7 like scores, nicknames, etc..
8 - players and interfaces are distinct things; the "human" player should
9 simply be derived from a base player class in such a way that it connects
10 to the interface. So XAtom-4 has an X11 player, textui has an ncurses
11 player, etc.. Similarly, the AI player is its own player. Network players
12 will just be another type of player. Interfaces should know how to work
13 with any player type (the specialized player type for that interface can
14 simply be an "active" class hooked off eventloop that triggers state
15 changes in the interface; no need for special handling in the interface
16 class itself).
17 - game state change notification should also be expanded to cover events
18 like round over, change of turn, etc.. Interfaces shouldn't have to keep
19 on examining game state (although that should certainly be possible too).
20 - Add history and playback capability
21 - need network play! :-)
22 - all the infrastructure is in place, just have to actually implement the
23 network communications layer.
24 + IDEA:
25 + then attach textui to a fake game engine which is actually a network
26 client that connects to the server. We'll have to change make_move()
27 so that it will know to wait for a network response instead of asking
28 the user for a response. (Although now it's arguable whether this should
29 be in class interface instead of something else...)
30 X replace textui with a network interface, which basically acts like
31 a game server;
32 + alternatively:
33 + have textui able to choose between the real engine and a network engine.
34 + textui will have two modes: standalone mode, where it gets input for
35 both users, and network mode, where it gets input for one player from
36 console, and the other from network.
37 - AI: profile a search, and see if we can't optimize it by caching hdelta's.
38 * actually, hdelta's are the least of your worries. The current big CPU hog
39 appears to be find_legal_moves(). (Unsurprising; it has to scan the entire
40 board to determine legal moves, and checks 6 neighbours per cell.)
41 - implement permanent AI subprocess first! We can't cache anything if we're
42 fork()ing each turn. We should probably just implement network play and
43 have the AI communicate over the network layer. No need for yet another
44 interface when one would do!
45 - AI: make pcreated, pdestroyed weights configurable.
46 - AI: add optional delay, so that we can (potentially) pit two AI's against
47 each other :-)
48 - more helpful failure codes from game::move(). Preferably we should
49 standardize messages in the game engine instead of relying on the interface.
50 + need to mark up board with coors so that players can see where to move;
51 or alternatively, cycle ncurses cursor through all legal moves.
52 + need to reset last_x,last_y and clear messages pane after restarting new
53 game.
54 + add color to pieces :-)
55 + BUG: board window is one column smaller than it should be ('cos odd rows
56 are shifted right, and require one more column to fit!)
57 + should clearly indicate which color is which player (display player headings
58 in the appropriate color!)
59 + CRITICAL BUG: check_win() does NOT correctly detect wins if the last marble
60 placed is in the center of the row of 4 instead of either end.
61 X split off base class interface and subclass textui... then we can have a
62 network interface, e.g.
63 * Unnecessary. Just write a new UI. There is no compelling reason to use
64 the same base class anyway, since the only public method is run()!
65 X need to have independent player class (for scorekeeping and for keeping
66 track of colors, etc) -- although maybe it's good enough to keep this in
67 class interface.
68 * scorekeeping is now in the game engine, as it should be.
69 X need to clean up board representation; ideally, EMPTY_CELL should = 0, and
70 BAD_CELL should = -1, and players' pieces should be stored as the player
71 number.
72 * Unnecessary.
73 + implement new version of game, just to get a proof-of-concept of the new
74 2-player, 3-colors idea.
75 * Hmm, it's harder to balance than I thought. Because of the way the
76 colors are alternated, whoever lays down the N-1'th piece in a row will
77 almost certainly lose; so there's not much motivation except to play
78 defensive, in which case it's impossible to win.
79 * Sounds like in order for this to be plausible, we're gonna have to explore
80 the 8-color scheme.
81 + need to implement a true multiplayer interface for game engine
82 + game engine will be modal: DUAL (current), PEER (interface represents
83 only a single player), WATCH (only receiving updates, not playing).
84 + fix X11 interface to support modal engines!
85 X should separate client from interface, maybe?
86 X another idea: have game engine require two players to "plug in"; but
87 we can connect the same interface to the engine twice to get the
88 current setup
89 + generalize class interface to allow integration with X11 client.
90 + Clean up class atom4local mess!!!
91 + should inherit from triboard and put all color-manipulation stuff in there.
92 X Probably the best way is to templatize class triboard.
93 + implement copy ctor for class triboard, so that it's easier to implement
94 state-space search algos for the AI.
95 + fix -a so that we can specify which player AI should be.
96 + Implement AI player! It's a tad boring to play against myself :-P
97 + can have configurable AI, assigning different weights to the following:
98 + single-depth scores:
99 + number of colors a move changes
100 + number of propagators a move creates
101 + number of opponent propagators a move destroys
102 X number of opponent propagators vs. number of our propagators in
103 resultant state space
104 * Probably not necessary
105 + recursive state-space searching scores:
106 + even depths (opponent's turn):
107 + losing move: if opponent has a winning move, assign negative score
108 + (recursive) if all searched sub-moves result in states where
109 opponent has a winning move, assign negative score
110 + pruning:
111 + instead of recursively considering all possible opponent moves,
112 only consider those we would pick if we were in that position
113 + winning move: if a move causes a win, pick it for sure! :-)
114 + implemented min-max algorithm. Strangely, it seems quite inferior in
115 terms of AI defense/offense (and takes a lot longer too!).
116 + AI: implement a subprocess for the AI! that's what we have event loops for!
117 + update README to explain the new 8-color game! :-)
118 + [ncurses] should be updated to handle new 8-color system.
119 + [ncurses] should be updated to support modal engines
120 + make it easy to customize construction vars like PREFIX, DATADIR, etc.
121 * can just use Cons' %ARG feature.
122 + BUG: fix varexception so that catch(exception) will work properly!!!!
123 + it shouldn't just work for catch(exception&)
124 + we should probably merge the two into the base class anyway, so that we
125 can do exception class hierarchies in a sane way.
126 + BP: ambiguous prototypes exception(char*) and exception(char*, ...)
127 * one solution may be to use the first char of the message as indicator
128 (start with '@' for varexceptions). This should be minimally ugly,
129 at least better than introducing a new parameter!
130 + BUG: atom4 cannot be suspended with SIGSTOP; upon resume, event loop dies
131 with Interrupted Syscall exception. (Should probably catch this condition,
132 since it is something to be expected. Also, should probably make sure we
133 don't die if 0 fd's are selected, which would happen when the process
134 resumes after a SIGCONT.)
135 + BUG: fix game engine so that it will detect stalemate (board filled up with
136 no winners). This may be rare, but you don't want to be embarrassed when
137 somebody actually manages to achieve that!!
138 * Simplest way is just to maintain a counter initialized with w*h and
139 decremented every time a non-blank piece is placed.
140 + Write a tarball-building script! It's quite a pain to do it by hand each
141 time.
142 + Update the Debian package with the eventloop fix.
143 X [ncurses] need to handle SIGWINCH.
144 * May not need to after all; ncurses-dev comes with its own SIGWINCH
145 handler.
146 + [ncurses] fix non-updating board background on PuTTY.
147 + AI: why is min-max algorithm performing so poorly??
148 * 'cos you did it wrong, dummy! You're supposed to evaluate the heuristic
149 function only at leaf nodes. Otherwise the min-max propagation becomes
150 meaningless, since it would effectively yield the path that leads to
151 the best move (in terms of the color changes heuristic), rather than the
152 path to the best game state.
153 * somehow, the heuristic algorithm seems to perform best at depth=2. Trying
154 depth=4 doesn't yield much improvement at all, and is just boringly slow.
155 + implement REAL min-max algo!!!
156 + IDEA: still base heuristic score on per-piece changes, but accumulate
157 them in a struct, only evaluate them at leaf nodes. Then propagate them
158 back using a real min-max selector.
159 + this way, we can actually implement alpha-pruning...!
160 + BBBBP: min-max algo still seems to perform horribly poorly. :-/
161 * Because you did it wrong again you dolt!!!! You forgot to invert hdelta
162 between turns, so enemy advances were counted as gains!!! You fool!!!!
163 + argh, something is SERIOUSLY wrong with your implementation!! It's not
164 even detecting losing moves.
165 X Must be that max=-min parameter, I think...
166 * argh, something's wrong, it's not even detecting winning states...
167 + Aha, found problem: in pick_best_move(), we treat equal scores equally;
168 but pruned subtrees return max, which may get equal score with another
169 non-pruned subtree. This is OK in score_opponent_move() because we use
170 > instead of >=. But pick_best_move() uses >=, so it misidentifies a
171 pruned branch as a good move.
172 * FIXED!! Let's see how well it performs now...
173 + [ncurses] do a message("") after board change happens (AI moved), so that
174 the "it's not your turn" message doesn't continue sticking there after it
175 *is* your turn. Or better, print a message saying what the AI moved.
176 + AI: min-max algo is *still* not doing very well at increased search depths.
177 At least -d2 seems to be at the same level as the original heuristic algo.
178 -d3 and -d4 seem to be a regression though :-( Must be a problem with the
179 heuristic value function...
180 + Ack! Looks like there's a bug in the score propagation code. Negative
181 scores from AI's turn doesn't change sign when propagated to opponent's
182 turn.
183 * FIXED!! Now the AI is pretty formidable at -d3 !!
184 + [ncurses] After AI moves, should restore cursor pos to current board pos,
185 else it looks misleading and player may make a mistake.
186 + BUG: fixed incorrect negation of hdelta in AI. AI seems to be acting more
187 rationally now. :-P
188 * Wow, -d3 is now quite hard!
189 + BUG: event loop postponed adds/deletes are inconsistent when the same fd is
190 added/deleted within a single dispatch cycle. Before appending a new entry
191 to the added/deleted list, we should check if it's already in the other list
192 and remove it from the other list if necessary.
193 + eventloop: we REALLY need to implement timers now. Use gettimeofday() to get
194 the same precision select() uses.
195 + Add timer to event loop