File: TODO

package info (click to toggle)
atom4 4.1-9
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 836 kB
  • ctags: 1,222
  • sloc: cpp: 4,451; makefile: 46; perl: 6
file content (195 lines) | stat: -rw-r--r-- 11,816 bytes parent folder | download | duplicates (6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
- 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