Numb3rs 410: Chinese Box

While leaving FBI headquarters, David Sinclair is taken hostage by a former surveillance subcontractor for the FBI (Ben Blakley, played by Erico Coliani) in an elevator in their headquarters, and the team must find a way to end the standoff with as little bloodshed as possible. All the while, their video surveillance in the elevator has been cut by the paranoid ex-contractor - so the team must operate with no eyes on an increasingly tense hostage situation.

Charlie compares the elevator to a "Chinese Box" - a thought experiment asking whether there is a difference between a computer algorithmically responding to sentances typed it in Chinese or a person who doesn't speak Chinese following the same algorithms as the computer. So long as we know the input and output of this "Chinese Box", arguably there is no real difference between an automated response and a human powered response. The box in this case is the elevator holding Ben and David, both only possessing limited possible communcations and choices determined largely by the FBI's actions to end the standoff.

Charlie also compares the actions that Ben and David are taking to a classic 2-person competitive game, called Chomp. Let's look a little bit at this game, then examine some other games.

Chomp and Game Theory

Competitive game theory has been widely studied across various disiplines - economics, biology, political science, sociology, mathematics, etc. Sample common games will involve placing bets, making deals, reproductive behavior, voting coalitions, splitting pots, etc.

Let's look at Charlie's game, "Chomp". Given a pair of numbers a and b, we build a board of axb dots (Charlie uses cookies to illustrate his point, but just for ease, we're gonna call them dots) arranged in a rows and b columns. Two players take turns "eating" our dots. The first player takes a dot somewhere on the board, and all dots to the right and below it. The player who has to eat the last dot loses. Here's an example, where a=5, b=6:

Chomp Starting Board Chomp 1 Chomp 2 Chomp 3 Chomp 4 Chomp 5 Chomp 6 Chomp Final Board

Activity 1: Chomp, chomp, chomp!

  1. Looking at the game above, you can see that Player A made a mistake on his third move. What SHOULD he have done?
  2. Play a few rounds of this game yourselves. Try it with the following a,b pairs:
    1. a=1,b=10
    2. a=2,b=5
    3. a=3,b=4
    4. a=7,b=8
  3. Does it look like Player A can always win?

Strategy for Chomp

Looking at this game a little more closely, we can see that Player A can always play in a way that will let them win. How do we see this? Well, let's say that Player B has a strategy to guarantee a win. However, whatever the first move Player B will make to guarantee themselves a win, Player A can play that move instead, thus guaranteeing himself the win. This is called a "strategy stealing argument", and is often used to show that a given game has a winning strategy. In the episode, Charlie realizes that in the hostage "game", David has made the first move - and although whether or not the move was right was unforseable at the beginning, if David can somehow get himself back to being "Player 1" (in a sense,) he'll be able to make it out of there alright.

Chomp is also what is known as a "perfect information" game - which means that both players can see all moves the other player has played. Games of this type include go, chess, backgammon, and a number of others. Let's look at another perfect information game that's fun to play, and see if you can develop a winning strategy for it.

Activity 2: Amazons

This game is played on a 10x10 chess board, using eight "queens" (four per player) and a bag of markers (chips, stones, pennies, etc.) Each player starts with four of his queens on the board (one player at A4,D1,G1, and J4, the other player on A7,D10,G10,and J7.)

Player A selects one of his queens and moves it anywhere a queen could normally move on a chessboard (although we no longer "capture" other pieces as a regular queen would.) After the queen has moved, she can then shoot an arrow, which moves as another queen from her current location on the board - and whatever space the arrow lands on is labeled with a marker.

The queens cannot travel to or through any of these marked squares, and arrows cannot travel to or through marked squares or any space where a queen (of either color) stands. Also, unlike chess, there is no "capturing" other pieces - the goal is to trap them until they can't move, while remaining free yourself.

Here's a sample opening move:

Like Chomp, the player who is able to make the last move wins. Pick a parner and play a round of the game, and see if there are any overall "good strategies" that you can come up with.

A Most Ancient Game...

It is estimated that Go was played as early as 4000 years ago, making it one of the oldest board games still in existence - second perhaps only behind backgammon and mancala. The game originated in China and was there as highly esteemed as caligraphy, music, and painting among the aristocratic arts.

It was after its transmission to Japan that the development of Go as a discipline exploded. Among other things, this development included the establishment of both Go ranking systems and schools to train and house players, along with the dissemination of the game from outward from the Imperial court to many of the general public. Although it is thought now that Korea and China have largely re-taken dominance internationally at the game of Go, for many hundred years Japan was the center of study and practice of Go.

Even today, Go is incredibly popular - rating television airings of major games, the publication of weekly Go magazines in China, Japan, and Korea, and with a whole system set in place to train Go students from childhood to full professional level. To read more about the history and current state of affairs of Go, check out either the or this introduction to the history of Go, parts 1, 2, and 3.

The Game of Go

One of the oldest perfect information games is the game of Go, known in China as Weichi and Japan as Igo. Like chess and unlike backgammon, this is a game with no "luck" but only strategy. Although the theory and practice of Go is far beyond the scope of a class period, it is well worth explaining the basic rules and worth giving a try! Although traditionally, Go is played on a 19x19 board with players taking turns placing pieces on the intersection points of lines on a grid, the game can be played on a smaller scale on any nxn board. The most typical other sizes are 9x9 and 13x13.

The goal is to surround as much territory on the board as possible and to "capture" your opponents stones. To capture stones, they must be entirely surrounded on all of their horizontal and vertical "liberties" - adjacent empty spaces - by stones of the opposite color. Here's a few sample captures:

There are a few additional rules - namely, the ko rule and information on how to score - but that's essentially the whole rule set. The ko rule just says that the last move in this sequence is illegal:

The reasoning behind this rule is that, were it allowed, two players could just go back and forth taking the other person's stone with no end. To get around this, you can't play that second move - although if you play a different move the next turn, on your turn after that you can take back to ko with that other move.

Finally, in terms of scoring, when both players have surrounded as much territory as they can and cannot place any more stones, they both pass. To score, they count up the total number of empty squares that their pieces surround, then add the number of captured pieces.

Activity 3: Game Time!

Try playing a quick game on a 5x5 or 9x9 board yourself! The KGS Go server has the option to play 9x9 games, and there's a whole room of beginners looking for good games if you want to try doing this a couple of times.

For more of a challenge, try some Go problems. Both the Sensei's Library and GoBase have a good selection of problems ranging from easy beginner to incredibly difficult.

The rules of Go are easy, but the strategy and tactics required to play Go well is considered the study of a lifetime. To read more about the rules of Go and to see lots and lots of Go problems and exercises, check out the Sensei's Library. Even if there aren't many people around you who play Go, you can easily meet hundreds of people to play Go with on either KGS or IGS.