Michi - 15x15 ~6k KGS in 540 lines of Python code

[yoyoma]

Petr Baudis, author of Pachi, recently posted an annoucement of Michi on the computer-go mailing list. Here is his announcement:

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

[jeromie]

This is great! Thanks for posting this. I actually have a chance of understanding the algorithms being used in this implementation.

[wanyiwan]

Petr Baudis, author of Pachi, recently posted an annoucement of Michi on the computer-go mailing list. Here is his announcement:

I played michi on KGS a few days ago, the name looks like standing for minimal pachi.

[Bonobo]

Petr Baudis, author of Pachi, recently posted an annoucement of Michi on the computer-go mailing list. Here is his announcement:

I played michi on KGS a few days ago, the name looks like standing for minimal pachi.

It actually says so on the page Yoyoma linked to:

The ethymology of Michi is "Minimalistic Pachi".

[sic!]

[Mike Novack]

This is great! Thanks for posting this. I actually have a chance of understanding the algorithms being used in this implementation.

Just a suggestion for if somebody wants to try writing a faster implementation by using a different language (from somebody who in my day did this as part of my job*).

While simply rewriting the Python code into a different language might increase the speed (he gave an estimate of maybe 5x) that is not really the best way to go about it. You want to work from the algorithm in its abstract form, not the form where decisions about data representations, etc. have already been made to be reasonable for Python.

That is of course "reverse engineering", read a program and determine the original abstract algorithm being implemented. Not easy, especially if without a great deal of experience. Maybe he could be convinced to release a version (of the Python) that included as comments for all the parts what the abstract data and functions are. Or just as pseudo-code.


* To give an very extreme example -- sometimes this was rewriting a time critical process from COBOL to BAL (assembler for the IBM mainframe). There were a few times where my replacement in assembler code had far fewer lines of code than the COBOL being replaced! When you consider that each line of COBOL normally compiles to several machine instructions (and so lines of assembler code) you should realize how important what I am suggesting above. In other words, you want to understand what the code should be doing and then do that in a way suited to your faster language as opposed to what were good choices for the language you are replacing.

[pasky]

While simply rewriting the Python code into a different language might increase the speed (he gave an estimate of maybe 5x) that is not really the best way to go about it. You want to work from the algorithm in its abstract form, not the form where decisions about data representations, etc. have already been made to be reasonable for Python.

*The* advantage of Python is that it really reads much like just a pseudocode.

So my gut feeling would be not to worry about that too much. I can't think of much data representation changes I'd do because of rewriting in a different language. And when you finish the 1:1 translation, you might already get a good intuition of what's next to do to make things more efficient. (Do profile it first, though.)

(Of course, in general the most awful part of the code is the hack of finding liberties by using regexes, and possibly the board representation in general. But you would want to change that even in the original Python code!)

[Mike Novack]

And when you finish the 1:1 translation, you might already get a good intuition of what's next to do to make things more efficient. (Do profile it first, though.)

For the benefit of those who have never done "tuning", what Pasky is saying (and what I always had to keep telling my programmers) is don't waste your time looking for all the inefficiencies in a program. Instead you need to find out where the program is actually spending the bulk of its time and restrict yourself to there. It is normal for programs to spend a great deal of the time in a small percentage of the code and only a very small total amount of the time in the rest of it.

Understand? If the program is spending 90% of its time in 10% of the code and only 10% of the time in the remaining 90% just look at the critical 10% of the code. If you can save 50% there you have saved 45% of the total time. In the non-critical code, even if you saved all of the time, that's only 10%.

There are tools that can tell you this (where a program is spending its time), and Passky is referring to one of them, a "profiler"

[oren]

There are tools that can tell you this (where a program is spending its time), and Passky is referring to one of them, a "profiler"

And if you do want to do tuning... Python is really not the language to be doing it in...

[Mike Novack]

There are tools that can tell you this (where a program is spending its time), and Passky is referring to one of them, a "profiler"

And if you do want to do tuning... Python is really not the language to be doing it in...

Well, keep in mind that my professional experience is with much larger programs. The "program" (the run exec) might actually be several "objects" link edited together, other parts called dynamically, not all necessarily all written in the same language.

So no, it doesn't matter. My first step would be to profile the program as is, language not important. That will tell me where it is spending its time. May make it possible to determine what the problem is, and the real problem might not be the inefficiency of the language.

[oren]

Well, keep in mind that my professional experience is with much larger programs. The "program" (the run exec) might actually be several "objects" link edited together, other parts called dynamically, not all necessarily all written in the same language.

And my professional experience is with much much larger. Don't try to do analysis and tuning too much on python.