Solving Checkers, Agency, and Foreknowledge
Posted on September 30th, 2005 by Bryce Inouye
This summer I attended one of the major international artificial intelligence conferences, where one of the best paper awards went to Jonathan Schaeffer for his paper “Solving Checkers.” Schaeffer has spent the past 17 years trying to create an unbeatable checkers playing program (For our overseas readers, checkers = draughts played on an 8×8 board). The result, Chinook, is a formidable player indeed: the project’s website notes that it has been certified by the Guinness Book of World Records as “the first computer program to win a human world championship”.
Schaeffer’s goal when he set out was to create a program that could beat any human player at checkers. In practice, this meant creating a machine that could defeat Marion Tinsley, the undisputed greatest checkers player in recorded history (he lost 7 games (not matches) in his entire career, including causal and exhibition speed games). Chinook and Tinsley did have a match which Tinsley won in August 1992 in London (4 wins, 2 losses, 33 draws). Schaeffer and company set out to improve their program for a rematch in 1994. Six games into the match, Tinsley withdrew, citing health reasons. Seven months later, Tinsley died of pancreatic cancer.
Chinook went on to become the Man-Machine champion by defeating Don Lafferty, who stepped in for Tinsley at the 1994 match. Still, the checkers community would not accept that a machine could be the best checkers player of all time. The shadow of the great Tinsley loomed over Schaeffer. He would be forever answering the critics who claimed (with no little justification) that Chinook would never have been able to defeat a healthy Tinsley.
So Schaeffer set out to silence his critics once and for all: he set out to solve the game of checkers. To solve a game means to calculate all possible positions and their potential outcomes so that a player with such knowledge can play perfectly (wikipedia article here). Tic-tac-toe is a simple example of a game that is solved. Players playing perfectly can always force a draw, whether they play first or second. The game of Nim is also solved; under the variant most people are familiar with, the game is a win for the first player, meaning that if the first player plays optimally, he or she is assured of a win. Connect Four is a known win for the first player as well. More complex games have too many possibilities to calculate, even for the fastest computers. Chess is not completely solved, and Go seems completely intractable.
Solving checkers is hard. Although the rules are simpler than chess, and the number of possible moves from any given position are less than chess, the number of possible positions to consider is still mind-bogglingly large, on the order of 5×10^20. The Chinook team has compiled an end-game database for all possible positions with 10 pieces on the board (you can download up through the 8-piece databases here). This means (as I understand it) that the entire game tree for these positions has been computed and stored in an accessible form. If the computer reaches one of these positions, game over.
Up until the proof process reaches that point however, for many positions Chinook is still guessing (albeit very well). However, it can and does produce weak solutions for various positions with more than 10 pieces on the board, meaning that it can tell you that a give position is a win, loss, or draw, but it can’t tell you how to produce that outcome — the game trees themselves aren’t stored, only the results. The ultimate goal is to produce a weak solution for the opening position, saying whether the first player is guaranteed to win, lose, or draw if it plays optimally.
In high-level tournament checkers, to make things interesting, the first three moves are assigned to the players, in order to force different lines of play. Positions are chosen at random from a set of approved openings, and two games are played using the position, with each player taking a turn playing first, so as to negate any advantage that might thereby be gained. Schaeffer’s paper at the conference I attended announced that they had weakly solved checkers for one of those openings. With the appropriate resources, he claimed that the entire game could be solved in about one year.
What does this have to do with us here at M*? Not a whole lot actually — it’s a noteworthy achievement, and the history is pretty interesting, if you’re into that kind of stuff. As I listened to the conference talk, a metaphor for getting at the question of agency and foreknowledge occured to me. I missed the furor last winter in the bloggernacle on this subject (here’s a link to get you started), and frankly, it doesn’t keep me up nights, and to further undermine my credibility (stop reading at any time now), I’m no philosopher. But here’s the thought: Since Chinook is after a weak solution, at any node in the game tree that it has solved it can tell what the outcome of the game will be. For the purposes of actual game play, Chinook could calculate optimal moves down any particular line of play that it deems necessary, but the result is not pre-computed until it reaches the ten-piece endgame databases, it cannot tell how to produce that outcome. Furthermore, even within the endgame databases, the opponent is free to make any legal move — the outcome is still determined.
So for checkers, at least, once a complete weak solution is obtained, Chinook will have complete foreknowledge (after a fashion), and yet the details of each game will be undetermined until they are played out, and the opponent will always be free to act as he or she deems fit.
Checkers, anyone?
Links:
The Chinook homepage.
Play against a crippled version of Chinook here.
A terrific (and long) account of the Chinook-Tinsley matches (well worth reading).
» Filed Under Any
Comments
15 Responses to “Solving Checkers, Agency, and Foreknowledge”
Leave a Reply
Very interesting. Some of the best papers I’ve read on agency were done by Lynn England and were centered around artificial intelligence.
Yes, this is very interesting. But I disagree that the computer has complete foreknowledge, even after a fashion. The computer simply knows which moves are possible and the best response to any given move. As long as there is more than one move possible, the computer does not know which move the player is going to make.
As such, I think the analogy between the computer and God is very appropriate. That lack of knowledge of what will happen, both on God’s part and the computer’s part, is what makes agency possible.
Interesting. I knew the history of man-machine checkers but I did not know that so much progress had been made. Moviegoers will remember that in War Games the computer (Joshua) was told to solve checkers which then prompted it to solve global thermal nuclear war. The funny thing about nuclear war is that the more peices you start with the easier it is to solve.
The interesting note about foreknowledge, God, AI and everything in between is actually a little different. The AI may know every possible outcome for any given play, but it is programed to play a perfect game. It lacks the agency to choose which play. It will go for either the most efficient win, or the first win scenario it sees.
Freud challenged this himself as he was a proponent of predestination. We will all act however we have been programed to act in a given instance. If we could understand every possible variable our actions would be predictable.
I think God is somehow outside of this mix in a time space manner. Perhaps he does not exist linearly, which would account for how he knows things to come, but we still have our agency. Maybe God has simply solved the game of life and every possible outcome.
Either way what makes us unique is that our agency allows us to choose which of our many options there are. Part of this is choosing what our goal is; pleasure, money, happiness, family etc. AI is only looking for an efficient win, but we all choose to define “win” differently.
I typically don’t do this, but this is especially applicable.
J. Stapley, don’t apologize.
I’ve got some comments on your post that I’ll leave there later this weekend.
Nice post, Bryce.
I think Eric got it right in his comment. The computer simply knows how to win the game — it has zero foreknowledge of what free-willed humans will actually choose to do as they play. The analogy is a good one to illustrate the value of seeking God’s advice on how to play (and win) the game of life but does nothing to support the idea that God exhaustively knows the future of of his freely choosing children.
Eric and Geoff J. –
Good point. When I said “complete foreknowledge (after a fashion)”, I was referring to foreknowledge of the outcome of interest, namely who would win the game, not the sequence of moves that lead there.
Strangely this thread may help explain how God can know our actions ahead of time while we exercise our free-agency simultaneously; expanding on the concept that when a certain point is reached the computer knows exactly who will win. If the computer was playing a perfect player, the computer would know exactly what moves the player would make while exerting not one iota of control on the player. The player would make the moves that the computer knows she would make, but she would still be chosing to make those moves. The player would chose the best moves that are already know to the both sides buy would still be doing so by choice.
This analogy may help some understand how two seemingly conflicting ideas are really in harmony. We are free to act despite our Heavenly Father’s knowledge of our future actions.
I don’t think so Heli. The computer would always know how to react in order to win, but would never know what its free-willed opponent was actually going to do before the opponent did it. That is not foreknowledge of the actions of the free-willed person at all.
Geoff,
I was trying to explain a concept that people who don’t believe God is omniscient don’t seem to grasp.
I was originally thinking of chess where at a certain point both sides know what the best move is. The opposing player knows exactly what move will be made. Lets even say the move places the defender in checkmate. Both sides know which move will be made, yet this knowledge does not remove the free-agency from the instant player. He or she will exercise his or her will and “mate” their opponent. Don’t worry about the players ability to chose another move, its immaterial for the purpose of understanding this concept.
Don’t tell me Jesus wasn’t free to perform the atonement because prophets throughout time had already seen him atone for the sins of the world. He still had agency and the fact that God the Father knew he would do it didn’t remove his agency. Jesus chose to save us because he loved us like any righteous older brother loves his siblings.
My post was only designed to explain the concept, and I guess the checkers game is not a good mechanism for doing so.
Sorry for the abrupt sounding nature of my last comment, Heli.
I actually agree that the chess analogy is a very good one. However, it seems to be an excellent argument against exhaustive foreknowledge rather than for it. If God was playing chess with me he would always win. He would also know what I am most likely to choose in any situation — but that is not the same as knowing what I will do perfectly via seeing a fixed and unchangeable future. That is because the future is open, not fixed; and because I have real free will, not hypothetical free will. (But again this is ground that we covered in the monster thread already linked to in this post).
You were right, that the Chinook computer program was not a good analogy. I was thinking more of the analogy you raise in post 12 of God playing Chess. Imagine God the Father playing Jesus Christ in a game of chess. I’m assuming it would be like wargames where every match would end in a draw or whoever played white would win (effectively the game would be solved because there are a limited number of combinations). From any position both players would know exactly what moves the other would make because there is only one best move at a time (again based on the premis that chess would be solved by two perfect being playing the game, not much fun, but informative).
I’m getting back to the same argument though. The nature of the relationship between perfect foreknowledge and true free-agency. I understand that you think if what you will be doing tomorrow at this time is already pre-determined that you are not the one making the determination. I just don’t understand how you can believe this. Who is making the determination?
For the sake of argument, assume that the future is fixed and in one week you will be writing a response to a blog, trying to explain to someone how free-agency is not effected by perfect foreknowledge. Considering that the future is fixed, who is making the decision to write that response? Why isn’t it you deciding to write the response? How does the fixed nature of the future even remove your ability to chose?
Heli,
I responded to your question about why I believe a fixed future obliterates true free will in our other conversation here.