Teeko by Mihailo Despotovic, March 1999

The program of my master thesis, “Učenje u strateškim igrama” (Machine Learning in Strategic Games), at the University of Belgrade. It plays Teeko, the game John Scarne invented in 1937: two players with four pawns each, on a board of five by five. First they put their pawns down, one at a time; then they move them, one field in any direction. Whoever first has four in a row, across, down or diagonally, or four in a square, wins. The program plays you or itself, and learns as it plays: after each game it remembers every position of it, with whether X or O went on to win, and in later games it prefers the moves that led to wins. It runs here as it did in a Windows console, and its files are kept in your browser, so it goes on learning from the games you play.

For each move it asks three advisers: its heuristics (make four, stop a four, make a three that can't be stopped…), a minimax search two moves deep, and its memory. Then it plays the move its evaluation function likes best. In batch mode it plays itself as many games as you ask, each side with its own memory, and that is how the experiments of the thesis were run. The memories those left are on the thesis CD, and can be loaded here; the most experienced is the one after 10,000 games.

I wrote it from 1997 to 1999 in ANSI C, as portable as I could make it: it was built with Turbo C 2.0, Borland C++ 3.1, Visual C++ 4.1 to 6.0, CodeWarrior 3.0 and the cc of Solaris and AIX, and checked with lint. Its main() was begun on 14 November 1998 in Sunnyvale, California, five months after I moved to the USA. My advisors were Đorđe Dugošija and Vladimir Srdanović, and I defended the thesis on 13 May 2002, before a commission of Đorđe Dugošija, Srđan Stanković and Vera Vujičić-Kovačević. The idea went on into TeekoTeacher.

How it works

The opening, while the pawns are put down, has its own heuristics: the middle first, then the fields around it; later, four if it can make it, else stopping the opponent's four, else making three, else stopping the opponent's three. After that, for each move, the heuristics try in turn to make four, stop a four, make a three open at both ends, make a three that can't be stopped, and stop those of the opponent; failing all of those, a random move. Making or stopping four is played at once. Otherwise the search writes every move of the program to a file, level1.s, and every reply to each of them to level2.s, and takes the move whose worst reply is the best. The evaluation adds 1000 for four, 15 for a three and 6 for the middle field, 3 for each of the eight around it, less the opponent's.

The memory, memory.m, is plain text: each position is 25 digits, the board row by row, followed by how many games it was in that X won, and that O won, in four characters each. A position and the same with X and O swapped are one. When a game is won, every position of it (after the opening) is added, or its count is raised. To recall, the program looks for the positions its next move can reach, and takes the one with the most wins over losses. Drawn games teach nothing. stat.m keeps the score.

The bugs, and the fixes

• The search seldom plays the move it found. decide() works out each move's worst reply, and the best of those, as minimax should. But then it looks for that move by comparing the value with each move's own evaluation, a different number, and reads the file back one or two moves short of where it stopped. In 400 games against itself, the move it passed on was one of the best only 7.5% of the time (613 of 8,206 searches).
• Player O reads the memory backwards. A remembered position counts how often X won from it and how often O did. Recalling, the program takes wins minus losses from X's side whichever side it plays, so O picks the moves that went well for X. The thesis says the subtraction goes “depending on whether the computer is the first or the second player” (6.4.3); the code doesn't ask. In batch mode, where O is player 2, O with the memory after 10,000 games won 20.9% of 3,000 games, less than O with no memory at all, 24.8%. With that one sign changed, 34.0%. The experiments of chapter 6.9 ran on this code: the saved memories are from 29 to 31 October 2000, after teeko.exe was built from these sources on 12 October.
• When you move first, it learns the game the wrong way round. It tells who won by whether the game ended on an odd or an even move, which is right when its own pawns moved first. When yours did, every position is counted as a win for the loser: in six games it won against a player who began, all the positions it learned, 8 to 32 a game, went down as the player's wins.
• From move 25 on, it offers you a draw on every one of its turns. Against a person, game() looks for cycles of 2, 3 and 5 moves, but isdraw() knows only 2, 3 and 4; asked for 5, it compares a position with itself, and finds a draw. In 60 sessions of play, it offered a draw on all 1,134 of its turns past move 24, and the position was repeating in none of them.
• It can say it is making four, and not. The heuristics' patterns use −1 for “no field”, but test x>0, so a field in row 0 is never left out; and four of the patterns of make4 and avoid4 name a field off their line, 34 or 30 for 32. Either way it can play a “killer move” at once that isn't one: with its pawns on 00, 02 and 03 it moves 00 to 01, and with 10, 21 and 43 and a pawn next to 32, it goes to 34 instead of winning on 32. And avoid4 checks 00 where it means 04, so it doesn't stop that four when 00 is taken.
• It can hang in the opening. Some of its placements pick one of four fields at random until one is free, 11, 13, 31 and 33, or 12, 21, 23 and 32, and when all four are taken, it never stops. It happened 5 times in about 10,700 openings against a player putting pawns anywhere. To see it: move first, put pawns on 40 and 04, and if its second pawn goes to 13 or 31, put yours on 33, and then on 11.
• Your moves aren't checked. getmove() tests the third digit twice and the fourth never, and never asks whether the field is next to the pawn. So 1344 jumps from 13 to 44, a fourth digit over 4 runs on into the next row, and 4449, with your pawn on 44, can put it past the end of the board, into the program's other variables, and it is gone.
• Smaller ones. The statistics give the number of games it played second as those it played first. The square patterns of makenondefendable3 and avoidnondefendable3 are in loops that start from a variable left at 5, so they never run. makedouble3 asks about the field 5,4, past the board, where it means 4,j. omake3 puts a pawn on 12 where it means 22, which can't happen in play, as the middle is always taken by then. With searching off and learning on, learnplay() lists the moves from a board it hasn't filled in yet, so it finds nothing in its memory. And quitting a game with q leaves game.m open, so it stays behind when teeko ends.

Fixed does what was meant: the search plays its best move, each side reads the memory from its own side, a game you began is learned the right way round, a draw is offered only when the moves repeat, your pawns move only to a free field next to them, the patterns name the right fields and leave out the right ones, the square patterns run, the opening puts its pawn on a random free field when the four are taken, the statistics give the right number, and learning alone looks at the board it is on. The typos, such as “occured” and “positios”, are as they were.

The port was checked against the original C, compiled on a Mac with Microsoft's rand(), the clock given, and the typing read from a script. In 400 sessions of random typing and command lines, batch mode with the saved memories included, and 200 played by a program that reads the screen and answers as a person might, mistakes and all, the screens and the files left behind are the same, hangs included. Each heuristic was also run on 60,000 boards, reaching every line of them, with the same result every time. Where the C reads or writes past the end of the board, the page does what it would if the variables lay in memory in the order defs.c declares them, and the C was compiled so; the board learnplay() never fills in is empty here, as it was in that C. Visual C++ 6 rounded a percentage that ends in exactly a half up, 3.125 to 3.13, and the page does too.

The original C code

Seventeen files, which teeko.c puts together with #include.