Friday, July 4, 2008

Why are computer chess programs much stronger than the ones in GO?

Computer chess and Chinese chess programs have reached a very high playing level against human player. However, the computer GO programs are still in relatively low level. People have been contemplating the reasons behind it. Some think the complexity of GO is much higher than chess or Chinese chess, so today's computer can handle chess well but not GO yet. I would like to offer my current thoughts at current stage, so I can come back to examine it again at later time.

While the complexity of GO is much higher than chess, they are all astronomical number. Current computer speed can only examine very tiny portion of the game tree in tournament time control for it to be chess or GO. Come to think about it, it is amazing that the computer chess programs of today can reach such a high playing level by just examining such a small portion of the game tree. I think it has something to do with the very good prediction power of the middle game evaluation. In chess or Chinese chess, material advantage can be translated to final outcome with very good correction rate. One knight or one cannon up in the middle game almost guarantee a win, let along a rook up. With this character, local search of 10 to 15 plies can find a very high quality evaluation for best material gain. Since the material gain has very good prediction value in final outcome, the program can then perform at very high level. Looking at GO, it is very difficult to have a surrogate evaluation in the middle game that has good prediction power to final outcome. The relevant decision is hard to make based on local search and the long search just consumes too much time to be practical, hence the weak performance of GO program. The trend of GO programs now is Monte Carlo algorithm. Based on my limited understanding of the concept, people try to get a evaluation term based on a long search to the endgame, although the search quality was bad given the limited time. Since the local evaluation has very bad prediction power, the long search evaluation still do better due to it's relevance, although in bad quality.

If my assumption is correct, the way to improve computer GO program is to find a better predictor in the middle game within limited time. One way is to find high quality predictor in local search, which has been eluding people's attempts so far. The other way is to improve the quality of evaluation at long search. Since time is limited, it is a very difficult task. The one to find a better solution at one of these two ways should lead the field.

If you have thoughts on this topic, I encourage you to leave some comments here. We should be able to examine the condition again in the future.