| 1 | GNU Go Task List |
| 2 | |
| 3 | You can help make GNU Go the best Go program. |
| 4 | |
| 5 | This is a task-list for anyone who is interested in helping with GNU |
| 6 | Go. If you want to work on such a project you should correspond with |
| 7 | us until we reach a common vision of how the feature will work! |
| 8 | |
| 9 | A note about copyright. Before any code can be accepted as a part of |
| 10 | the official release of GNU Go, the Free Software Foundation will want |
| 11 | you to sign a copyright disclaimer. Of course you can work on a forked |
| 12 | version without signing such a disclaimer. If you want your changes to |
| 13 | the program to be incorporated into the version we distribute we need |
| 14 | such a disclaimer. Please contact the GNU Go maintainers, Daniel Bump |
| 15 | (bump@sporadic.stanford.edu) and Gunnar Farneback |
| 16 | (gunnar@lysator.liu.se), to get more information and the papers to |
| 17 | sign. |
| 18 | |
| 19 | Below is a list of things YOU could work on. We are already working on |
| 20 | some of these tasks, but don't let that stop you. Please contact us or |
| 21 | the person assigned to task for further discussion. |
| 22 | |
| 23 | //-------------------------------------------------------------- |
| 24 | // General |
| 25 | //-------------------------------------------------------------- |
| 26 | |
| 27 | * If you can, send us bug FIXES as well as bug reports. If you see |
| 28 | some bad behavior, figure out what causes it, and what to do about |
| 29 | fixing it. And send us a patch! If you find an interesting bug and |
| 30 | cannot tell us how to fix it, we would be happy to have you tell us |
| 31 | about it anyway. Send us the sgf file (if possible) and attach |
| 32 | other relevant information, such as the GNU Go version number. In |
| 33 | cases of assertion failures and segmentation faults we probably |
| 34 | want to know what operating system and compiler you were using, in |
| 35 | order to determine if the problem is platform dependent. |
| 36 | |
| 37 | //-------------------------------------------------------------- |
| 38 | // smaller projects |
| 39 | //-------------------------------------------------------------- |
| 40 | |
| 41 | These issues are of tactical nature, i.e. they concern some specific |
| 42 | feature or the infrastructure of the engine. Some of these are quiet |
| 43 | small, maybe doable in a day for an experienced GNU Go programmer. |
| 44 | They might also be useful project to start with for a new project |
| 45 | member. Some of them are bigger and demand a deeper knowledge of the |
| 46 | engine internals. The issues are presented here in an approximate |
| 47 | order of perceived difficulty. |
| 48 | |
| 49 | * Add more checks in patterns/mkpat.c testing whether the main diagram and |
| 50 | the constraint diagram are consistent. |
| 51 | |
| 52 | * Break out handling of movelists into its own file and generalize it. |
| 53 | This is started in 3.1.16. Move lists are used, among other places, |
| 54 | in worms.c where it is used to store moves that capture, save, |
| 55 | threaten to capture and threaten to save the worm. |
| 56 | |
| 57 | * Implement move lists storing important moves for dragons and eyes |
| 58 | in the same way as it is used for worms. Half eyes are already |
| 59 | halfway done. The moves are stored, but not the attack and defend |
| 60 | codes (LOSE, KO_A, KO_B and WIN). |
| 61 | |
| 62 | * Make the cache not waste storage on 64 bit systems. |
| 63 | |
| 64 | * The dragon data is split into two arrays, dragon[] and dragon2[]. |
| 65 | The dragon2 array only have one entry per dragon, in contrast to |
| 66 | the dragon array where all the data is stored once for every |
| 67 | intersection of the board. Complete the conversion of eye_data, |
| 68 | half_eye_data, worm and dragon to use the same structure as the |
| 69 | dragon2 array. |
| 70 | |
| 71 | * Support for ko in eyes.db and optics.c. |
| 72 | |
| 73 | * Integrate the time handling code in play_gtp.c with the autolevel |
| 74 | code in clock.c. Alternatively, replace them both with something |
| 75 | better. Basing it on some solid system identification theory and/or |
| 76 | control theory wouldn't hurt. |
| 77 | |
| 78 | * Write a script which plays through the joseki databases and checks |
| 79 | that the engine really generates a joseki move for all positions in |
| 80 | the databases. This would also be interesting to run with the |
| 81 | --nojosekidb option. |
| 82 | |
| 83 | |
| 84 | //-------------------------------------------------------------- |
| 85 | // long term issues |
| 86 | //-------------------------------------------------------------- |
| 87 | |
| 88 | |
| 89 | These issues are strategic in nature. They will help us to improve the |
| 90 | playing strength of the program and/or enhance certain aspects of it. |
| 91 | |
| 92 | * Extend the regression test suites. |
| 93 | See the texinfo manual in the doc directory for a description of |
| 94 | how to do this. In particular it would be useful with test suites |
| 95 | for common life and death problems. Currently second line groups, L |
| 96 | groups and the tripod shape are reasonably well covered, but there |
| 97 | is for example almost nothing on comb formations, carpenter's |
| 98 | square, and so on. Other areas where test suites would be most |
| 99 | welcome are fuseki, tesuji, and endgame. |
| 100 | |
| 101 | * Tuning the pattern databases. These are under constant revision. Tuning |
| 102 | them is a sort of art. It is not necessary to do any programming to do |
| 103 | this since most of the patterns do not require helpers. We would like it if |
| 104 | a few more Dan level players would learn this skill. |
| 105 | |
| 106 | * Extend and tune the Joseki database. It might be very useful to implement |
| 107 | a semi-automatic way of doing this. The current method based on sgf files |
| 108 | becomes difficult with existing tools. |
| 109 | |
| 110 | * The semeai module is still in need of improvement. (This is underway.) |
| 111 | |
| 112 | * GNU Go does not have a move generator that tries explicitly to build |
| 113 | moyos, or reduce/invade opponent's moyos. Such a move generator could |
| 114 | be built using the same type of code that is used in the owl life and |
| 115 | death reader, or the connection reader mentioned in point 5 above. |
| 116 | |
| 117 | * A much improved combination module. The combination module of |
| 118 | today only finds combinations of threats to capture enemy groups. |
| 119 | A more useful combination module would e.g. find combinations of |
| 120 | threats to capture a group or enter opponent territory. It would |
| 121 | also be strong enough to find combinations of strategic moves and |
| 122 | more indirect threats (a threat to a threat). Possibly it could |
| 123 | combine threats in AND-OR trees (DAGs?) that could be searched |
| 124 | using ordinary tree search algorithms. (Revision of combination.c |
| 125 | is underway.) |
| 126 | |
| 127 | * Speed up the tactical reading. GNU Go is reasonably accurate when |
| 128 | it comes to tactical reading, but not always very fast. The main |
| 129 | problem is that too many ineffective moves are tested, leading to |
| 130 | strange variations that shouldn't need consideration. To improve |
| 131 | one could refine the move generation heuristics in the reading. |
| 132 | Also, one should implement some more of the standard tree search |
| 133 | optimizations used in alpha-beta readers. |
| 134 | |
| 135 | * Improve the heuristics for assessment of the safety of a |
| 136 | group. This might take into account number of eyes / half eyes, |
| 137 | moyo in corners, moyo along the edge, moyo in the center, proximity |
| 138 | to living friendly groups, weak opponent groups etc. It is of |
| 139 | particular interest to be able to accurately determine how a move |
| 140 | affects the safety of all groups on the board. |
| 141 | |
| 142 | |
| 143 | //-------------------------------------------------------------- |
| 144 | // Ideas |
| 145 | //-------------------------------------------------------------- |
| 146 | |
| 147 | |
| 148 | These are some ideas that have been floated on the mailing list. Some |
| 149 | of them are down-to-earth, and some are just blue sky ramblings. They |
| 150 | are presented here for inspiration. |
| 151 | |
| 152 | * A good GUI. |
| 153 | A start is being made with GoThic, a goban widget based on the Qt |
| 154 | toolkit. This is linked from the GNU Go development web page on |
| 155 | gnu.org. Other starts have been made based on GTK+, but so far |
| 156 | nothing more than a start has been attempted. |
| 157 | |
| 158 | * A graphical pattern editor. |
| 159 | This would make it much easier for non-programmers to improve the |
| 160 | strength of GNU Go. It could also be used as a debugging tool for |
| 161 | the programmers. This project has the GUI as a prerequisite. |
| 162 | The challenge here is not to make a tool which makes it easier to |
| 163 | create patterns but to make it easier to overview and maintain the |
| 164 | database. |
| 165 | |
| 166 | * Make the engine thread safe and use multiple CPUs on an SMP |
| 167 | machine. |
| 168 | |
| 169 | * Making the engine use many machines loosely connected on the |
| 170 | internet or in a cluster. |
| 171 | |
| 172 | * Think on the opponent's time. |
| 173 | |
| 174 | * A global alpha-beta reader. This would probably be very slow and |
| 175 | could only read 2 or 3 moves ahead. Still it could find fatal |
| 176 | errors and improve the moves that GNU Go makes. |
| 177 | |
| 178 | * A strategic module that identifies high-level goals and then gives |
| 179 | these goals to the rest of the engine. It should be able to |
| 180 | identify if we are ahead in territory or thickness, if we should |
| 181 | play safe or if we should play daringly (e.g. if behind). It |
| 182 | should also identify weak areas where we can attack or where we |
| 183 | should defend. Maybe this module doesn't have to be written in C. |
| 184 | Maybe PROLOG, LISP or some other AI language would be better. |
| 185 | |
| 186 | * A parameter that makes GNU Go play different styles. Such styles |
| 187 | could be 'play for territory', 'play aggressively', 'play tricky |
| 188 | moves (hamete)', and so on. It could be used to present human |
| 189 | users with different kinds of opponents or to tell GNU Go how to |
| 190 | play certain computer opponents in tournaments. |
| 191 | |
| 192 | * Generalize representation and handling of threats so that we have a |
| 193 | graph representation of threats that can be searched to see how |
| 194 | different threats interact. |
| 195 | |
| 196 | * An endgame module based on ideas from combinatorial game theory. |
| 197 | To be really useful this would have to deal with early endgame |
| 198 | positions. |
| 199 | |
| 200 | * Fuseki tuning by hand is difficult. People who are interested |
| 201 | in doing machine learning experiments with GNU Go could try |
| 202 | working with fuseki. This may be one of the areas with most |
| 203 | potential for substantial and reasonably quick improvements. |
| 204 | |
| 205 | * Create a paradigm for handling other types of ko (approach move ko, |
| 206 | multi-step ko, etc) and then write code that handles them. |
| 207 | |