Tuesday, March 16, 2010

Poker and AI: I'll See Your Turing Test and Raise You an Algorithm

Alan Turing came up with the first standard criterion for artificial intelligence. According to the Turing test, if you were to interact with the computer and not know it was a computer, say by asking it questions and having it answer, then we could say that we had achieved artificial intelligence as conversational interactivity is a hallmark of intelligence.

This started a long and intricate discussion among philosophers, cognitive scientists, computer scientists, and whoever else cared to weigh in. Other criteria were floated as lines in the sand to differentiate thinking from mere calculating and among those was strategic planning. Consider games in which one could outwit one's opponent, surely if we could get a computer to do that, it would be significant. And so chess was taken as the quintessential strategic game and Grandmaster Garry Kasparov was taken as the pinnacle of human achievement against which to pit our best computer.

In a recent edition of The New York Review of Books, Kasparov muses about the meaning (or lack thereof) of his much heralded match with the IBM computer Deep Blue. Chess, he contends, is a different case than checkers. In checkers, the number of possible games (each game is a string of moves) is small enough that someone has developed a program that has solved it. That is, it knows every possible game and will always makes moves so that it never loses. For a simpler example, think of tic-tac-toe, a game that becomes boring quickly because we learn the secret to never losing. A computer can play checkers in that way.

But chess is much more complex. The number of games is so large that this cannot at present be done. But what can be done -- and this is how chess programs work -- is that you can translate the chess board into scores, with more advantageous positions given higher scores and less advantageous positions given lower scores. One can then make sure that one's program always maximizes the the score, making it more likely to win. The better this algorithm, the better the program and it can be developed to compete with the best rained human players. that this is possible, Kasparov argues, is interesting, but not THAT interesting. The ability to translate chess into a number crunching exercise turns it from a strategic enterprise into something less "human."

The real place to put the line we thought was drawn with chess, he argues, is poker. Poker, Kasparov contends, is different from chess in two key ways: (1) in chess there is no chance, all the pieces are on the board, but in poker you are operating with only partial information, and (2) the most rational move is not always the best move. It would be easy enough to develop an effective poker playing program in terms of hands won, but the goal in poker is not to maximize your wins, but rather to maximize your winnings. If one always made the maximally logical move, one could be easily read and when you do win, you don't win much.

So, could we see a similar event to the one in the 90s with Kasparov and Deep Blue? Could we design a new IBM machine across the table from Daniel Negreanu that would consistently take all his money?