[gnugo-devel] Revise TODO?

[Gunnar Farnebäck]

As mentioned in a previous message I'm not content with the state of
our TODO list and I think it's in a rather bad need of revision. I'll
start by stating my opinions on the current items. Please comment.


 * If you can, send us bug FIXES as well as bug reports. If you see
   some bad behavior, figure out what causes it, and what to do about
   fixing it. And send us a patch! If you find an interesting bug and
   cannot tell us how to fix it, we would be happy to have you tell us
   about it anyway. Send us the sgf file (if possible) and attach
   other relevant information, such as the GNU Go version number. In
   cases of assertion failures and segmentation faults we probably
   want to know what operating system and compiler you were using, in
   order to determine if the problem is platform dependent.

Still fine.


 * Add more checks in patterns/mkpat.c testing whether the main
   diagram and the constraint diagram are consistent.

Not very interesting. Pattern consistency hasn't been much of an issue
for a long time. If anything should be done with mkpat.c it's
redesign and a new clean implementation. That file is messy.


 * Break out handling of movelists into its own file and generalize
   it. This is started in 3.1.16. Move lists are used, among other
   places, in worms.c where it is used to store moves that capture,
   save, threaten to capture and threaten to save the worm.

I don't see much value in doing anything more on this.


 * Implement move lists storing important moves for dragons and eyes
   in the same way as it is used for worms. Half eyes are already
   halfway done. The moves are stored, but not the attack and defend
   codes (LOSE, KO_A, KO_B and WIN).

Could be done as part of algorithm improvements. It's not worth doing
for its own sake.


 * Make the cache not waste storage on 64 bit systems.

No big deal. Don't spend time on it.


 * The dragon data is split into two arrays, dragon[] and dragon2[].
   The dragon2 array only have one entry per dragon, in contrast to
   the dragon array where all the data is stored once for every
   intersection of the board. Complete the conversion of eye_data,
   half_eye_data, worm and dragon to use the same structure as the
   dragon2 array.

Also not worth doing for its own sake.


 * Support for ko in eyes.db and optics.c.

This doesn't necessarily have much impact on playing strength but I
would like to see it done sometime.


 * Integrate the time handling code in play_gtp.c with the autolevel
   code in clock.c. Alternatively, replace them both with something
   better. Basing it on some solid system identification theory and/or
   control theory wouldn't hurt.

This has already been done.


 * Write a script which plays through the joseki databases and checks
   that the engine really generates a joseki move for all positions in
   the databases. This would also be interesting to run with the
   --nojosekidb option.

Not very important but worth doing.


 * Extend the regression test suites.
   See the texinfo manual in the doc directory for a description of
   how to do this. In particular it would be useful with test suites
   for common life and death problems. Currently second line groups, L
   groups and the tripod shape are reasonably well covered, but there
   is for example almost nothing on comb formations, carpenter's
   square, and so on. Other areas where test suites would be most
   welcome are fuseki, tesuji, and endgame.

Always valuable but we should look for high quality tests. We have no
shortage of tests in more or less random positions where the choice
of accepted moves is far from obvious.

A special challenge is regression tests for Monte Carlo approaches.
There it may be necessary to have tests where the accepted moves lead
to a win and all other moves lead to a loss, assuming ideal play after
the first move. Very few of the current tests are of that kind.


 * Tuning the pattern databases. These are under constant revision.
   Tuning them is a sort of art. It is not necessary to do any
   programming to do this since most of the patterns do not require
   helpers. We would like it if a few more Dan level players would
   learn this skill.

This was written long ago when patterns much more directly controlled
the move generation, but it's to a large extent still true.


 * Extend and tune the Joseki database. It might be very useful to
   implement a semi-automatic way of doing this. The current method
   based on sgf files becomes difficult with existing tools.

Still relevant but the focus must be on automatic or semi-automatic
learning approaches. Entering joseki moves by hand is mostly a waste
of time.


 * The semeai module is still in need of improvement. (This is underway.)

It has been dramatically improved since this item was first written
but it remains true nevertheless.


 * GNU Go does not have a move generator that tries explicitly to
   build moyos, or reduce/invade opponent's moyos. Such a move
   generator could be built using the same type of code that is used
   in the owl life and death reader, or the connection reader
   mentioned in point 5 above.

I think the break-in code covers this item, so it's already done.


 * A much improved combination module.  The combination module of
   today only finds combinations of threats to capture enemy groups.
   A more useful combination module would e.g. find combinations of
   threats to capture a group or enter opponent territory.  It would
   also be strong enough to find combinations of strategic moves and
   more indirect threats (a threat to a threat).  Possibly it could
   combine threats in AND-OR trees (DAGs?) that could be searched
   using ordinary tree search algorithms.  (Revision of combination.c
   is underway.)

Useful in theory but lots of complexity that might be better handled
by a global fullboard search.


 * Speed up the tactical reading. GNU Go is reasonably accurate when
   it comes to tactical reading, but not always very fast.  The main
   problem is that too many ineffective moves are tested, leading to
   strange variations that shouldn't need consideration.  To improve
   one could refine the move generation heuristics in the reading.
   Also, one should implement some more of the standard tree search
   optimizations used in alpha-beta readers.

I don't consider tactical reading as big problem but if someone wants
to do anything with it I would be more interested in seeing, e.g.,
what could be done with proof number search.


 * Improve the heuristics for assessment of the safety of a
   group. This might take into account number of eyes / half eyes,
   moyo in corners, moyo along the edge, moyo in the center, proximity
   to living friendly groups, weak opponent groups etc. It is of
   particular interest to be able to accurately determine how a move
   affects the safety of all groups on the board.

This is extremely important and could have a huge impact on the
strength of GNU Go.


 * A good GUI.
   A start is being made with GoThic, a goban widget based on the Qt
   toolkit.  This is linked from the GNU Go development web page on
   gnu.org. Other starts have been made based on GTK+, but so far
   nothing more than a start has been attempted.

Uninteresting. For playing there is no shortage of external GUIs
(e.g. Quarry, GoGui, Cgoban) and for debugging interface/view.pike
exists (although it could be improved). Additionally we are already
distributing an emacs GUI (gnugo.el).


 * A graphical pattern editor.
   This would make it much easier for non-programmers to improve the
   strength of GNU Go.  It could also be used as a debugging tool for
   the programmers.  This project has the GUI as a prerequisite.
   The challenge here is not to make a tool which makes it easier to
   create patterns but to make it easier to overview and maintain the
   database.

A waste of time in my opinion. The gain for the patterns would be
offset by the maintenance of the editor.


 * Make the engine thread safe and use multiple CPUs on an SMP
   machine.

As I've said before we should concentrate this on a Monte Carlo part
of the engine.


 * Making the engine use many machines loosely connected on the
   internet or in a cluster.

Very difficult. SlugGo tries.


 * Think on the opponent's time.

Would be good to have. Easiest done in a Monte Carlo framework. For
the current code, population of the persistent cache would be the most
reasonable approach.


 * A global alpha-beta reader.  This would probably be very slow and
   could only read 2 or 3 moves ahead.  Still it could find fatal
   errors and improve the moves that GNU Go makes.

Global reading would be nice to have.


 * A strategic module that identifies high-level goals and then gives
   these goals to the rest of the engine.  It should be able to
   identify if we are ahead in territory or thickness, if we should
   play safe or if we should play daringly (e.g. if behind).  It
   should also identify weak areas where we can attack or where we
   should defend.  Maybe this module doesn't have to be written in C.
   Maybe PROLOG, LISP or some other AI language would be better.

Very difficult but would be cool if it could be done.


 * A parameter that makes GNU Go play different styles.  Such styles
   could be 'play for territory', 'play aggressively', 'play tricky
   moves (hamete)', and so on.  It could be used to present human
   users with different kinds of opponents or to tell GNU Go how to
   play certain computer opponents in tournaments.

Some work has been done on this (e.g. the cosmic option). Not so
important but a nice touch.


 * Generalize representation and handling of threats so that we have a
   graph representation of threats that can be searched to see how
   different threats interact.

Mostly the same as the item about combinations above.


 * An endgame module based on ideas from combinatorial game theory.
   To be really useful this would have to deal with early endgame
   positions.

Monte Carlo is almost certainly more effective.


 * Fuseki tuning by hand is difficult. People who are interested
   in doing machine learning experiments with GNU Go could try
   working with fuseki. This may be one of the areas with most
   potential for substantial and reasonably quick improvements.

Very interesting and I think it's doable in the near future.


 * Create a paradigm for handling other types of ko (approach move ko,
   multi-step ko, etc) and then write code that handles them.

Maybe more of theoretical than practical interest.

/Gunnar