It was reported today that Jonathan Schaeffer and his Games Group team at University of Alberta have solved checkers. Assuming perfect play, the game is a draw. (The result is actually a few months old, but American news media were busy reporting about freeway chases and other important events and didn’t notice until the result was published in Science.) Additional information is available from the University of Alberta website.
I haven’t read the Science article, but as far as I understand, this isn’t “solving” checkers in the strong sense, only in a weak sense. So, yeah, it’s a draw assuming perfect play, and it took several computers brute-forcing through large portions of the game tree for 18 years to show it’s a draw. From the outside looking in, that just isn’t terribly exciting. To me, it would have been way more interesting had they actually generated a program that can play the game optimally (without searching).
Anyway, reading about this result made me think of formulas that can play games such as checkers and chess (or really any type of game) or that can solve puzzles optimally, and how such formulas could be generated. For example, for both games and puzzles we could have formulas that take the (encoded) game or puzzle state as input and result in a value that corresponds to the best possible gameplay move or change to the puzzle state. (These formulas would be very complicated, but they do exist nevertheless.)
To illustrate what such a formula would look like, I’ll turn to a class of puzzles that’s often used in introductory AI classes to illustrate search algorithms like A*, namely the sliding-block puzzle family that contains the 8-puzzle and the 15-puzzle. In fact, I’ll use the simplest possible such puzzle, the 3-puzzle. (Admittedly, the 3-puzzle isn’t much of a puzzle as you only have two move choices at any given time—do a new forced move, or undo the previous move—but it is small enough for me to obtain a formula with little search effort, without loss of generality.)
The 3-puzzle board can be encoded as a base-4 number, where the tiles 1 through 3 are represented by the corresponding numbers and the empty space by the number zero. For example, I will represent the goal configuration
by the number (1230)4 = 1*43+2*42+3*41+0*40 = 108. All in all, the 3-puzzle has 4!/2 = 12 different board states, which in this representation encode to the numbers 30, 39, 57, 78, 99, 108, 135, 177, 180, 201, 210, and 216.
I decided the formula should return as output a number 0-3, representing moving the empty square down, left, up, and right, respectively. After setting up a table of desired input and output pairs, { 30→3, 39→0, 57→0, 78→0, 99→3, 108→any, 135→1, 177→3, 180→2, 201→0, 210→2, and 216→1 }, I wrote a little loop to search for a function that would return the desired outputs for the given inputs. After a few minutes or searching this is what I came up with:
int SolveThreePuzzle(int n) {
int b0 = 33 * (n + 1) >> 7;
int b1 = 2945 * (n + 1) >> 13;
int move = 2 * (b1 & 1) + (b0 & 1);
return move;
}
(OK, so this is a C++ function and not a formula, but it should be obvious that it can be written as a formula by turning the shifts into integer divisions and the bitwise ands into modulos.)
To see an example of how this function works, let’s arbitrarily start in the state (2013)4 = 135. We evaluate the function getting F(135) = 1, meaning we move the empty space left (or, if you prefer, sliding a tile right into the empty space). We are now in state (0213)4 = 39. F(39) = 0, so we move the empty space down. The new state is (1203)4 = 99 and F(99) = 3 which is right. After moving the empty space to the right, the new state is (1230)4 = 108 and we are done. This process is illustrated in the figure below.
If you wanted to be a little more fancy, you could have the function return the new state of the puzzle instead of the move, but it is harder to find a (simple) function for more complex output.
Also, of course, a function like the one I defined here is only really interesting if it is smaller than the table we’re encoding—that is, if it has a low Kolmogorov complexity—otherwise you might as well just keep the table.
So, back to the checkers result. If the 18-years of searching had produced a function (of low-ish Kolmogorov complexity), which for each valid input state would return the move that was the optimal move in that state, now that would be solving checkers!
BTW, I’ll leave it to some enterprising soul to develop and post a closed formula for the 8-puzzle. This would force AI teachers all around the world to change their tired old 8-puzzle assignments for something fresh and new! Bonus points are awarded to those who develop a formula for perfectly playing tic-tac-toe. (Actually attempting a formula for checkers or chess may be a tad overambitious!)
All this stuff about shoving the board state and moves into integers is really a red herring — you could do that sort of thing inside the function if you wanted to, but there’s probably no particular gain from it. What you’re talking about is just compression of a complete move database. There’s no particular reason to believe it can be done to an extent you desire, but I’m sure the literature has explored such ideas extensively because the prohibitive size of the game tree was almost certainly one of their main concerns.
Your aversion to any search (did just you mean full tree search?) seems rather arbitrary, as does your desire to express your function as an algorithm (C++ function) instead of a “formula” (there’s not really a difference, except that C++ code compiles?).
First, there is a huge difference between a mathematical formula and a function written in a programming language. For example, the latter (in stark contrast to the former) may depend on memory, may have side effects, and may not terminate. Second, a function is not an algorithm is not a function. Also,I’m not sure why you felt I expressed desire towards algorithms over formulas, when—contrariwise—I was only ever searching for a formula and never even talked about algorithms (other than an irrelevant mentioning of A* in passing).
That said, of course this is a compression problem in the abstract (thus, for example, my reference to Kolmogorov complexity; the better the compression, the lower the Kolmogorov complexity).
The compression/representation problem I talked about didn’t really have anything in particular to do with the checkers result, other than the one made me think of the other, as an interesting problem. And of course it is entirely unfeasible to expect you could generate a formula to play checkers or chess optimally: the search would have exponential complexity over some insanely large number of states! That doesn’t mean it’s not fun to generate a formula for small problems like tic-tac-toe or the 8-puzzle, both of which are easily doable! (And both would make excellent entries for the IOCCC. Perhaps not good enough to tattoo though.)
Can you post the code that searched for SolveThreePuzzle? I’m reminded of manually finding the logic gates to perform arbitrary boolean functions back in school.
I’d be interested in seeing what a similar ‘minimal’ chess-playing program is. It’s pretty trivial to write simple functions that optimally plays a game (just doing the enormous bruteforce searching) – it’s not much more complex than the rules of the game itself. That’s not really interesting. So are we looking for the time-optimal solution? It probably wouldn’t be simple and closed-form, like yours was, because it would be at least as kolmogorov-complex as the simpest solution (which is likely to be bruteforcing for complex, deeply branching games).
For the SolveThreePuzzle() function all I did was to decide, manually, on the format of the function that you see. Then I just had a bunch of nested loops to search for the constants of the two b0 and b1 expressions, plus an additional loop to loop over all pairs of input and output states. (Needless to say, I solved for b0 and b1 independently.) I tried a few different versions of functions (involving multiplies, modulos, etc) before I arrived at the multiply-add-shift version I finally used. All in all, I probably spent an hour tinkering before I came up with that code snippet.
So, in other words, I didn’t blindly search for a function. I opted for something I figured had a large chance of success, and then I just searched the parameter space of that particular solution. The same approach would probably work well for smaller problems like tic-tac-toe and the 8-puzzle, but probably not for anything much larger.
For something like chess (or checkers) you’d have to adopt a different approach because you’d be hard-pressed to enumerate all input-output pairs, let alone all possible inputs!
This is a solution for a tic-tac-toe variation with no diagonals. Diagonals should be easy enough to add. I didn’t test it thoroughly, though.
The board state is a binary number split in two 9-bit parts. The lower part are the player’s pieces and the upper part are the computer’s pieces. A bit is set for each piece. The bit indices on the board are:
0 1 2
3 4 5
6 7 8
Add 9 to the bit indices for the computer’s pieces.
For example: Two player pieces in the first two places of the first row is 3. The same places occupied by computer pieces is 3 * 2^9 = 1536. The same bit cannot be set both on the player side and on the computer side.
The return value is a binary value with one bit set which represents where the computer wants to put the next piece (always on the lower 9 bits). For example, if the computer figures it should play on the center position, the return value is 16.
Here’s the Python code:
# solve for one line
def f(a):
b = a – a/2 – a/4
p = b/2 * (1 – b & 1)
m = (~a & 7) * p
return m
# is zero
def z(a):
return (a – 1 & 262143) / 262143
# solve for one column
def fc(a):
s = f((a&1) + 2 * (a>>3 & 1) + 4 * (a>>6 & 1))
return (s&1) + 4 * (s&2) + 16 * (s&4)
# play defensive
def g(a):
f1 = f(a & 7)
f2 = f(a>>3 & 7)
f3 = f(a>>6 & 7)
fa = f1 + (f2>9)
c = a | a>>9
fav = ~c & (c+1)
return o + d * z(o) + fav * z(o) * z(d)
Sorry, scratch the last code. Here’s the correct one. Something went wrong with my copy&paste.
# solve for one line
def f(a):
b = a – a/2 – a/4
p = b/2 * (1 – b & 1)
m = (~a & 7) * p
return m
# is zero
def z(a):
return (a – 1 & 262143) / 262143
# solve for one column
def fc(a):
s = f((a&1) + 2 * (a>>3 & 1) + 4 * (a>>6 & 1))
return (s&1) + 4 * (s&2) + 16 * (s&4)
# play defensive
def g(a):
f1 = f(a & 7)
f2 = f(a>>3 & 7)
f3 = f(a>>6 & 7)
fa = f1 + (f2>9)
c = a | a>>9
fav = ~c & (c+1)
return o + d * z(o) + fav * z(o) * z(d)
Aha, it’s the shift-left operation that is messing up the HTML. Here’s a version without shift-lefts.
# solve for one line
def f(a):
b = a – a/2 – a/4
p = b/2 * (1 – b & 1)
m = (~a & 7) * p
return m
# is zero
def z(a):
return (a – 1 & 262143) / 262143
# solve for one column
def fc(a):
s = f((a&1) + 2 * (a>>3 & 1) + 4 * (a>>6 & 1))
return (s&1) + 4 * (s&2) + 16 * (s&4)
# play defensive
def g(a):
f1 = f(a & 7)
f2 = f(a>>3 & 7)
f3 = f(a>>6 & 7)
fa = f1 + 8 * f2 * z(f1) + 64 * f3 * z(f1) * z(f2)
f4 = fc(a)
f5 = fc(a/2)
f6 = fc(a/4)
fb = f4 + 2 * f5 * z(f4) + 4 * f6 * z(f4) * z(f5)
return fa + fb * z(fa)
# play offensive, then defensive, then first available
def h(a):
d = g(a & 511)
o = g(a>>9)
c = a | a>>9
fav = ~c & (c+1)
return o + d * z(o) + fav * z(o) * z(d)