Sunday, August 30, 2009

Disco: an elegant Python Go player (update)

after receiving generous help from 'apt1002' in the datastructure department, I am happy to announce Disco 0.3 (see my previous posting about Disco).

the new version is about ten times faster than 0.2 (from around 600 games per second on my PC to about 6000). in addition it now checks for positional superko (repeated positions), so it can now play on CGOS without making illegal moves half of the games.

interestingly, using CPython there is not much difference in speed between 0.2 and 0.3, while the speedup from using Shedskin goes from about 6 to 75 times! this is probably mostly due to avoiding (re)allocations, which of course aren't much faster in C++ than in CPython.. but the new datastructures are also a bit smarter in maintaining only the most necessary information.

the sourcecode is still only about 400 lines, but now slightly less readable.. I hope to clean this up a bit over the next few months, but other than I will be too busy. in the long-term, it would be interesting to add shape analyses and additions to UCT such as RAVE/AMAF, and try to keep all of that in a pretty package of under 1,000 lines..

28 comments:

Bill Mill said...

Great work!

lonelypirate said...

very nice

Felipe said...

Hi, we are 2 University students of Artificial Intelligence and we would like to implement MiniMax algorithm using Disco as a base.

If our project were successful we could provide our code as enhancement to Disco, i.e. another possible player algorithm.

Do you think that would be interesting to the development of the software?

Regards!

srepmub said...

thanks for asking! go right ahead, the code is yours. please do let me know when you find any bugs in disco or shedskin. I'd appreciate it to hear what you come up with, especially if you manage to beat the original disco.. :)

Julian said...
This comment has been removed by the author.
Julian said...

This is a really dumb question, but I am new to Python and just installed PyScripter and Eric python IDEs (beyond just IDLE) to run your Disco GO program. I am going through your code, mostly "F7 step into" (im a novice), and was trying to re-write your version of the UCT cpu_player in C#. However, this is my dumb question: How do i actually play the game in the Python shell? It says "thinking.." then it spits out a move (2,6) WHITE: 7.5, BLACK: 1 ... I haven't stepped far enough into the code to know what method output the last two lines & exactly what they mean. I also don't know what to enter next, as a player, into the shell to make a move??? Can you tell me what to enter? (sorry, dumb question, but im under time-constraints to show your program to someone i work for--you get 110% credit/reference for your program of course, im just showing it to my boss & learning mobile Android SDK for gaming apps on the side as well)

srepmub said...

you can fill in two numbers (starting from 0), separated by a space, which are then interpreted as x and y coordinates on the board.

text = raw_input('?').strip()
x, y = [int(i) for i in text.split()]

Thomas Müntzer said...

Hello Mark,

Congrats to your go program and the development of shedskin. I try to write an own go program and in dealing with the speed problem i came to shedskin and disco. What i understand so far is, that the board is a list of instances, which contains the data of every point on the board.What i dont undestand, how you avoid memory reallocation of the present board position for every uct simulation? Collecting the changes of the board and after one simulation undo it? I hope i was able to point out, what i mean.
Nice Greetings from Germany
Stefan

srepmub said...

@thomas: thanks! the board is 'reset' after each simulation. there's no undo. that does mean a few things are reallocated and some old things have to be garbage collected.

nboard = Board()
GAMES = max(25000-(1000*len(board.history))/4, 4000)
for game in range(GAMES):
node = tree
nboard.reset()
nboard.replay(board.history)
node.play(nboard)

I should probably remove the 'amaf' crap from the code btw, and the 'check' function.. and probably document things a bit..

for example, it may not be clear I'm using this to maintain groups:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Thomas Müntzer said...

Thanks for the quick anwser and the link. It helped me a lot. To find the right datastructure for a go game with tons of simulation is a real challenge.:-)

srepmub said...

the really good go players do much better than 'random' simulations, so perhaps it's actually better to slow down a bit in this sense.. :P

I just cleaned up examples/go.py a bit in shedskin git, and added a few other comments.. just tried it again, and it beat me on 9x9 (using GAMES=500000, took 2.7 GB of RAM here).. that's always interesting.

Thomas Müntzer said...

Thanks for the cleaned up version, makes things easier to understand. You are totally right about strong go engines. It is considered, that pure Monte Carlo reach only 18k rank on 19*19 Board. And Zen, the strongest machine today, is 6D on KGS! So there is something between 18k and 6d ;-). With my old Datastructure, for example using rekursive flood fill algo for searching connected stones, i was only able to play on 5*5 board with good results. Iam using alpha-beta tree search, a special algo which transfer the present position to and endposition and then evaluate it with Monte Carlo. But my present Datastructure is not able to do the task in needed Time. So i am happy to found your version,which is the Datastructure i was looking for. Thanks a lot Mark ;-).

Thomas Müntzer said...

I found a excellent Lecture on the topic of Disjoint set Datastructure on youtube.
http://www.youtube.com/watch?v=wSPAjGfDl7Q

srepmub said...

in case you decide to keep your program in pure python (for example, by extending disco), I'd be very very interested in hearing how it goes. I'd love to see a ~1000 line python player play really well. btw I can heartily recommend using gogui and cgos to test your program.

Thomas Müntzer said...

I will tell you, if the things do what they should and how the performance is. It will take some time to rewrite my program. It is written in pure python and currently ca. 700 lines of inefficent code;-).

srepmub said...

have you tried shedskin on it yet..? I'm very interested in performance or other problems.. it would also be awesome to add another go player to shedskin/examples later on perhaps.. ;-)

Thomas Müntzer said...

I have tried shedskin and the current speed up is ~26 times faster than my python code. On a 5*5 board with two moves deep search, some modification of the position and 100 Monte carlo simulations;
Python needs: ~25s
Shedskin needs: ~0.9s

There is a lot to improve, but the results are promising. I will report if my ideas works really, but i need to write the whole program in this disjoint set datastructure for checking on at least 9*9 board, rather on a 19*19 board.

srepmub said...

thanks for measuring! that's a fine speedup.. was that with 'shedskin -b'? note that there some useful performance tips in the shedskin documentation, that may help squeeze out more performance later. you can always send me some code in private, and I'm happy to have a look.

Thomas Müntzer said...

I measured today with and without boundary checking.
This time with 300 simulations:
-b: needed 2.95s
+b: needed 3.19s
Thanks for your offering of helping, if i can not figure out somethings, i come back to it. My e-mail is:stotti69.@hotmail.net. Can i reach you under mark.duf...@gmail.com ?

srepmub said...

thanks! yep :) note that there is also a shedskin discussion group hidden on the googlecode main page.. via a link in the lower left corner.

Thomas Müntzer said...

I tried to send you an e-mail, but hotmail complain about the adress and said mark.duf...@gmail.com is not proper name for an adress. I sent it to mark.duf@gmail.com, hope it will be arrive.

srepmub said...

oh I see, sorry about that, duf should be dufour.. :P interestingly I was unable to send you a mail too..?

Thomas Müntzer said...

Because the correct one is stotti69@hotmail.de ;-)

Thomas Müntzer said...

I hope my email reached you.

srepmub said...

it did :-) I'm a bit behind on my mail, but will try to reply soon..

Thomas Müntzer said...

Hello Mark,

examples_go in combination with simple beat,atari and winrate heuristics defeat manyfaces of go.version 11 and Aya 634e (both on strongest level ca 7-8k) on 9*9 with 50000 games. Beside the fact, that it don`t recognize a ladder, it play very stringent on 9*9 and i am impressed. The strength depends strong on the number of simulated games. With 40000 games it losses against MfG and Aya.
But one big problem occurs, if i simulate with 50000 games on 9*9 board. Sometimes i get the message, Fatal error in gc: too many heap sections and the program crashes.
I figured out, it has to do with the boehm garbage collector, but i am unable to find out, how to configure boehm garbage collector in windows xp. It would be nice to test the program with 100000 or even more simulations.
Thx Stefan

Jack Ha said...

I had to puzzle a bit, but the code is still readable :-) It indeed looks a bit optimized for performance.

Jack Ha said...
This comment has been removed by the author.