| 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 |