Computers playing Go
http://www.cs.unimaas.nl/~vanderwerf/5x5/5x5solved.html

This is actually pretty old news, but it was slashdotted today. Just goes to show that while information may be available instantly via the Internet, sifting through it all to find noteworthy items can take forever. Anyway - Go for a 5x5 board with an opening move in the center was "solved" by a computer program. Even knowing what I know, it hardly seems noteworthy.

When I was in college, a huge part of the grade for my second-semester AI class was Go. We had to learn the game well enough to play a competent game (I think that was worth 5% of our grade). Then we had to write a program to play Go.

The cool thing about the game of Go - which is to Asia as Chess is to the Western world - is that it is not reducable to the kind of "brute force" solution that Chess is. A pure search-tree (even with Alpha-Beta pruning and other optimizations) just won't work. At least not until we have quantum computers that are billions of times more powerful than our current machines. In Chess, you have a very limited number of moves at each turn. And many of those potential moves can be easily ignored because they'd clearly lead to very poor results (though how clearly is a good question for a chess program --- to a beginner, what seems like a bad move might actually be a great way to allow a game-winning opening). For the mid-game, Chess programs can just use a brute-force search to see many moves ahead and choose what seems to be the optimal result.

The opening game has a lot of move possibilities. All your pawns and knights have two possible moves each, for a total of 20 possible moves, which is fairly broad. Your opponent also has around 20 possible moves, and in all likelihood you'll have a similar number of potential moves for the first six moves or so. That's 20 x 20 x 20 x 20 x 20 moves to examine (before optimizations) to look just six moves ahead... that's 3,200,000 possibilities to explore. While that's doable (especially with optimizations) on modern machines, it doesn't begin to take the search to an interesting depth. So most chess programs use a library of "openings" rather than searching. They frequently also draw from a library of end-game situations to bring the match to a close.

Go, on the other hand, has an unbelievably broad range of potential moves for every turn. It's generally very difficult to determine if the move is 'good' or 'poor' in the short-term, so it's hard to weight the search tree for optimization. The first move has 361 possibilities... the second 360 possibilities... the third 359, the fourth 358, the fifth 357, the sixth 356 (the number goes down for a while, though in mid-game you'll start clearing out some stones and the number may spike up a little). So that same six-move-search is 2,122,781,978,399,040 moves. Way out of scope for modern machines, and it also doesn't begin to take things to an interesting depth. So it becomes more of a "real" AI problem, and you have to try more interesting approaches.

The really cool thing about this program we had to do for class was that our programs had to play each other. A big chunk of the mid-term grade was based on a tournament between our programs. The board was presented graphically on-screen on these creaky old HP-9000 minicomputers (these things were ancient even when I was in school). As spectators, we got to watch our games play each other - a real gut-wrenching experience when you realize that your grade depends heavily upon how much better you've taught your baby to play than everyone else.

This tournament was held twice - once around mid-term time, and once just before finals. My program dominated the first tournament, but it was also ridiculously slow - my moves were taking anywhere from 20 seconds to 4 minutes (!!!) to process. For the second tournament, the rules were changed (thanks to my program) to allow no more than 30 seconds per move.

Unfortunately, I ended up spending much of my time optimizing what I already had --- when I should have just started over from scratch. Besides optimizing, I basically put my entire program on a timer - I kept a record of the "best move so far", and when I ran out of time, I just returned that move. The end result, when all was said and done, is that the new version of my program was actually marginally less effective than the first one.

I got clobbered in the second tournament. Well, not totally clobbered - I did better than a couple of students if I recall correctly. But not only had I been forced to adapt my program to meet the new rules, but my program had turned out to be "The Program to Beat" during the first tournament - so everyone had optimized THEIR programs to beat mine. I'd become the target.

Ah, well. I still did well enough in the class to get hired on as a Teaching Assistant the following year --- and thereby meet people who were closely associated with group of people in a company-to-be that was eventually known as SingleTrac. That got me "in" to an interview (as soon as they had funding), and so that's how I got my first job in the videogame industry.

My take-aways from this experience:

• If you lead the race leader, remember everyone behind you has one thing on their mind... to beat YOU.
• Sometimes, it's much better to start over again in a project, salvaging usable bits rather than trying to get the clunky old beast to ride in a different direction.
• Having your program battle someone else's program is an amazing thrill that I suppose only geeks like me can appreciate.
• I found I could get pretty obsessive about AI - I was starting to dream of weight-tables and influence maps.
• Play Go - you never know where it can lead you.

Labels: programming

- posted by The Rampant Coyote @ 7:37 AM (Permalink)