So what’s the strongest program you can make with minimum effort and code size while keeping maximum clarity? Chess programers were exploring this for long time, e.g. with Sunfish, and that inspired me to try out something similar in Go over a few evening recently:
https://github.com/pasky/michi
Unfortunately, Chess rules are perhaps more complicated for humans, but much easier to play for computers! So the code is longer and more complicated than Sunfish, but hopefully it is still possible to understand it for a Computer Go newbie over a few hours. I will welcome any feedback and/or pull requests.
Contrary to other minimalistic UCT Go players, I wanted to create a program that actually plays reasonably. It can beat many beginners and on 15×15 fares about even with GNUGo; even on 19×19, it can win about 20% of its games with GNUGo on a beefier machine. Based on my observations, the limiting factor is time – Python is sloooow and a faster language with the exact same algorithm should be able to speed this up at least 5x, which should mean at least two ranks level-up. I attempt to leave the code also as my legacy, not sure if I’ll ever get back to Pachi – these parts of a Computer Go program I consider most essential. The biggest code omission wrt. strength is probably lack of 2-liberty semeai reading and more sophisticated self-atari detection.
P.S.: 6k KGS estimate has been based on playtesting against GNUGo over 40-60 games – winrate is about 50% with 4000 playouts/move. Best I can do… But you can connect the program itself to KGS too:
http://www.gokgs.com/gameArchives.jsp?user=michibot
Just a quick note – at the beginning of August, I have submitted my master thesis, titled Information Sharing in MCTS. MCTS means Monte Carlo Tree Search and it is a powerful technique for finding moves in games with large state space and difficult evaluation functions, such as Go.
The thesis presents the modern Computer Go techniques and open problems, my (not too weak) Go-playing program Pachi and some modest improvements of the MCTS algorithms. It might make a good introduction to state-of-art Computer Go.
Today I held a presentation on the “complete” state of art in implementation of AI playing the board game of Go (much harder than chess programs), showing hopefully all the current widely applicable results, most successful strategies and worst current problems (in my interpretation, of course) – it is available on my Go Stuff page. Some neat algorithms and general tricks and not too much math can be found inside. ;-)
The presentation has a section introducing basic Go rules and tactics so it should be suitable even for AI researches not very familiar with Go (there is an appendix .zip archive containing example sequences for the rules, and also examples of some games and playout strategies). Of course it is not perfect and some parts assume accompanying explanations and few formulas on blackboard, but I think it could still be good material to give quick overview on currently used approaches with sufficient depth to satisfy a computer science scholar, plus quick references to the papers.
P.S.: One IMHO important thing I now realize I’ve missed in the “open problems” section is parallelization on GPU.
Recent Comments