Markov chain GTP engine

[ethanb]

I had an amusing idea the other night about writing a GTP engine that would use statistics from a database of (preferably pro, but whatever) games and decide its next move by constructing a low-order (probably 2 or 3 would provide the most interesting results) Markov chain and always choosing the highest-probability move UNLESS it is an illegal move, in which case choose the next highest.

If we run out of legal moves that make legitimate chains (or have somehow strayed from a path ever trod before), I guess then we can use some sort of Monte Carlo search or just pick a spot in a random common shape from the last same color stone played (one-space jump, two-space extension, keima, ogeima...)

My goal is not to make a super-strong bot (although I wager the Markov chain method would at least play a halfway decent opening) but just to have fun making it, really.

[Li Kao]

It might have a decent opening, but the midgame would be horrible. Total lack of life and death handling doesn't work well.
One way even a total beginner would beat it is by playing in a different quadrant every move and only return to the original quadrant after 4 moves.

[ethanb]

Oh yeah, obviously tenuki would confuse the heck out of it, but I expect the human player might be surprised by some unexpected "tenuki" too, even in the late opening (why did he just attach to the top of my 10-3 stone? Answer: because it was a normal extension in the most common sequence after the last joseki was played)

Really, I was driving home a few nights ago listening to the System Shock 2 soundtrack and realized that the evil computer voice "speech" during the credits track, while probably an actual human speaking into a microphone and then distorted beyond intelligibility, could also be done by taking samples of phonemes and analyzing a few audiobooks to provide some good patterns of sequences that are possible to pronounce, then using a low-order Markov chain to construct your almost understandable gibberish.

From there it was a short jump (in my tired state) to say "hey, I wonder how a Markov-based Go bot would play?" and decide it might be amusing enough to pursue.

Like all Markov-based things, it's more amusing if you try to assume the naive mindset that there's actually some sort of intelligence making these bizarre decisions (which is easy to do - after all, they all look logical in isolation, right?)


Anyone who doesn't know what a Markov chain is, it's an algorithm that constructs the next step in a given sequence based on statistical analysis of past data. Garkov is a good example, where it replaces the speech bubbles in Garfield strips with words based on analyzing a database with the text of all the strips (and generally is way more amusing than the original comic.) One thing I always wonder about things like Garkov though - how does it choose the first word? Based on what the most likely starting words are? Or does it pick a word from the database at random?

[daniel_the_smith]

Interesting idea!

My initial thought is that Markov chains would not help much; it's necessary for the entire plan to cohere, and Markov chains would just make the bot change plans smoothly (and constantly). (And, of course, the bot wouldn't even have a concept of "plan"!) But I would be very happy to be proved wrong.

[hyperpape]

I'll probably put my foot in my mouth, since I only know the capsule version of what Markov chains are, but is switching plans so bad? Take the fuseki--there are a number of longish sequences that have been played many times by professionals--20 moves or so for the whole board. A human playing those needs a plan, because he doesn't have the whole tree of moves in front of him, so he needs some way to generate reasonable moves. A bot using that tree doesn't need a plan--he doesn't need to look ahead--he'll keep choosing from the tree, and end up at a reasonable position, even if it's not one he anticipated ahead of time.

After the fuseki things might be different, because there's issues of global balance. Also, maybe this whole post just indicates that I'm thinking of something different by plans. Hopefully it's still a reasonable question.

[jeff_elser]

I think this is an interesting idea. I've done some work using similar models for joseki and tesuji discovery.

You might consider dynamic Conditional Random Fields. They are a bit stronger than Markov models in that they are discriminative (as opposed to Markov models which are generative) which allows them to model conditional dependencies better (often resulting in better performance). Additionally CRFs would allow you to incorporate non-probabilistic measures like time left on clock, score, etc. The link below will get you started.

http://www.cs.umass.edu/~mccallum/paper ... torial.pdf

[ethanb]

I think this is an interesting idea. I've done some work using similar models for joseki and tesuji discovery.

You might consider dynamic Conditional Random Fields. They are a bit stronger than Markov models in that they are discriminative (as opposed to Markov models which are generative) which allows them to model conditional dependencies better (often resulting in better performance). Additionally CRFs would allow you to incorporate non-probabilistic measures like time left on clock, score, etc. The link below will get you started.

http://www.cs.umass.edu/~mccallum/paper ... torial.pdf

That does sound interesting! But I think it's better for somebody who genuinely wishes to advance the state of Go AI research. I just want to spend an hour or so with libkombilo and libshogun and throw together a Python script that'll play horrendously.

I started to look at libkombilo's API already. Doesn't seem too bad; the main problem is that I probably don't want to wait for a database search to return after every move, so if I actually want to turn this into something that's not painful to play I'll have to do my path finding beforehand, which is slightly annoying for a project I don't want to take seriously.

On the other hand, maybe the search is fast enough for the simple cases we're talking about (a 19x19 grid with 2-4 stones and the rest of the board filled with "I don't care") that it'll just work out. I'll try it and we'll see.