Tag Archives: game

Solved games

,

It might seem odd to describe a game like Draughts (US: Checkers) as being solved, but mathematically and scientifically it makes perfect sense.

A screenshot showing the Thinking Machine 4 chess engine deciding on a move.

A game is described as solved if it is possible for a player with knowledge of the solution to play a perfect game – to win (or at least draw) every time, no matter what moves their opponent makes. Theorists describe a game as being solved in two ways: a weak solution provides a fail-safe method from the game’s standard starting positions (e.g. in chess with all pieces on their “home” squares) and a strong solution provides a fail-safe method given any starting point.

The largest game solved so far is Draughts. It was weakly solved in April 2007 by a team led by Jonathan Schaeffer*, and their solution was implemented in a computer Draughts program called Chinook. It is mathematically impossible to play Chinook at Draughts and win – the only possible options are to lose or draw (if you don’t believe me, you can play against Chinook online).

Not all solved games result in a draw. In Connect Four the first player can force a win, whereas the second player will always win if playing Sim/Hexi or Chopsticks.

There are many important games that remain unsolved. Chess is only partially solved (for three to six piece endgames) and Go, perhaps one of the most computationally complex games, is only solved for board sizes up to five-by-five (standard games take place on a nineteen-by-nineteen board). It is estimated that with current technology it is impossible to solve either of these games.

This post was inspired by the excellent Relatively Prime podcast’s episode about Chinook.

* Jonathan Schaeffer et al, “Checkers is Solved,” Science 317 (2007): 1518-1522. DOI: 10.1126/science.1144079.

The physics of the Kinect

, , ,

The Microsoft Kinect is a peripheral for the Xbox 360 that does away with the need for a conventional controller – instead the player’s body and voice become the controller.

The Kinect sensor consists of:

  • 640×480 pixel visible light camera
  • 640×480 pixel infrared camera
  • Four-microphone sound sensing array
  • Class I infrared (780nm) laser diode

iFixit teardown of Kinect

The major advantage of the Kinect is that it works in 3D. Previous console vision systems (such as the PlayStation’s structured light” created by a beam of infrared laser light passing through a diffraction grating. This projects a grid of 50000 infrared dots across the playing area. These infrared dots are visible on many cameras with a “night vision” mode.

By comparing how the dot pattern looks, and how it should look, the Kinect can measure the distance between the sensor and the player – producing a “depth map” in the process.

Images from Matthew Fisher. Objects in red are closest to the screen; colours then move through the spectrum to purple objects that are furthest away.

Unlike Sony, who have cracked down on anyone trying to hack the PlayStation; Microsoft have been very open to Kinect hackers; including the team from Cox Lab at Harvard who have developed a portable Kinect-based 3D camera.

* It has been shown that the depth resolution is non-linear and that the further an object is from the sensor the less information is available about its true distance.