Game Theory

Another installment from the amazing file:  an iPhone app that looks at and then solves Sudoku.

http://www.cnet.com/how-to/how-to-beat-sudoku-puzzles-using-google-goggles/

Image recognition software aside, the interesting mathematical idea here is how one would create a computer program that can solve an arbitrary Sudoku puzzle.  It doesn’t seem like a particularly challenging task, but finding an efficient method may be a challenging problem.  After all, I imagine some strategies are better than others.

Experienced Sudoku solvers probably have a general algorithm they follow, but I imagine that intuition (guessing?) plays a role at some point.  Can you program that in somehow?

In the past we tested the prowess of our supercomputers by teaching them to play chess and pitting them against humanity’s greatest players.  Today we test our supercomputers by filling them up with trivia, arming them with a quick trigger finger, and pitting them against America’s greatest Jeopardy! contestants.

On February 14th, 15th, and 16th, IBM’s Watson will compete against Jeopardy! superstars Ken Jennings and Brad Rutter.

This should be a lot of fun.  I can’t wait to see what Watson’s Daily Double strategy is!

In 2007 Jon McLoone used Mathematica to create a Hangman game pitting the computer guesser against the human word-selector.  As his daughter became old enough to play against the demonstration, and old enough to get frustrated with the computer guesser always winning, she asked her dad the obvious question:  to beat the computer, what are the best words to choose?

Surprised that he had not considered such a good question himself, McLoone set about playing 15 million games of Hangman (automated, I imagine) using every word in the dictionary and arming the computer with a number of different letter-guessing-strategies.  The word that the computer failed to guess the most often was somewhat surprising.

So what kinds of strategies make the best guesser?  And to counter that, what kinds of strategies should the word-selector employ?