[Computer-go] [ANN] Michi - 15x15 ~6k KGS in 540 lines of Python code

[Petr Baudis]

  Hi!

  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 15x15 fares about even with GNUGo; even on 19x19, 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

-- 
				Petr Baudis
	If you do not work on an important problem, it's unlikely
	you'll do important work.  -- R. Hamming
	http://www.cs.virginia.edu/~robins/YouAndYourResearch.html