This is in part a continuation of last week’s discussion about artificial intelligence. But mostly it is an excuse to wax nostalgic about some of my early experiences with computers.
I recently made some final tweaks to a program I wrote to play the board game Pente. You can download it here. Instructions, source code, and executables for Windows are included, but it should compile on any platform supported by FreeGLUT/OpenGL. I really enjoyed writing it, and I hope you may get some enjoyment out of playing it.
This project was motivated by several factors. The idea most recently recurred to me during a classroom discussion about computer programming. We had been exploring simple graphics, drawing grids representing various game boards as an example. That led to a discussion of artificial intelligence: not just playing a board game on the computer, but having the computer act as one or even both players. In response to this discussion, I put together a simple example of a Java applet that would play Tic Tac Toe against a human opponent. This involved implementing some very generic game-playing AI framework, including move generation and ordering, board evaluation, negamax search with alpha-beta pruning, etc.
Meanwhile, my wife and I enjoy playing board games, and I had recently introduced her to Pente. I had the classic red roll-up tube version of the game when I was a kid, and I loved its combination of simplicity of rules yet complexity of play and strategy. Playing the game again after so many years, I thought it would be fun to try to implement a computer opponent that could play reasonably well– at least well enough to beat me, which shouldn’t be difficult, since I am definitely a novice player.
Finally, I wasn’t starting completely from scratch: this was not a new idea, but one that had been brewing for nearly 25 years, ever since I read the 1986 February issue of Nibble magazine (“The Reference for Apple Computing”). There was an article by James R. Geschwender about his program that he called Quintic, which allowed any combination of two human or computer players to play Pente. But the computer opponent was particularly intriguing in two respects. First, it did not involve any tree search at all, but was essentially just a single-ply lookahead, evaluating all possible moves according to a weighted sum of table lookup values based on the pattern of empty/black/white stones in a line surrounding each possible move. The result was an AI opponent that didn’t play terribly well, but was very fast, particularly on the 1 MHz Apple //.
Second– and this was the feature that really fascinated me as a kid– the lookup table that defined the move evaluation function was not fixed. There was an accompanying “coaching” program that let you tweak the values corresponding to different patterns on the board. But even more interesting was the ability of a computer player to “learn” on its own as it played, modifying its own lookup table by comparing its predictions with your actual moves, and making adjustments accordingly if it lost.
My program merely extends this basic idea of a simple board evaluation algorithm, with the complexity “hidden” in the pre-computed values of a lookup table. It uses straightforward fixed-depth negamax tree search with alpha-beta pruning. No transposition tables, no opening book; nothing really sophisticated at all. But the board evaluation function is at once detailed yet simple to implement… and thus relatively fast. It is detailed in that it uses a lookup table indexed by line patterns that extend four points in both directions from a candidate move (Quintic had two similar but separate and much smaller tables, one for “center moves” and one for “end moves”). It is simple in that there is no game-specific knowledge at all implemented in the board evaluation algorithm itself; everything from captures to open threes to potential wins, etc., are represented solely by appropriately scaled values in the lookup table.
What was really interesting, and frankly surprising, was that my first draft of lookup table values resulted in a computer opponent that plays pretty well. It holds its own against other AI opponents with the same search depth, including Mark Mammel’s excellent WPente. More importantly, I cannot consistently beat the computer even with only 4-ply looakahead. So by “plays pretty well” I suppose I mean that it at least regularly beats me… which was the whole point of this project.