Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 |