Archive

Archive for the ‘Toy Problems’ Category

Toy Problem Games

September 4, 2010 Leave a comment
First two ply of a game tree for tic-tac-toe

Image via Wikipedia

Tic-Tac-Toe

Tic-Tac-Toe is one of the simplest yet most-challenging games to be invented. With just a choice of nine locations, two players can pit their wits and very quickly work out who is superior. Even though the game is very simple, it has an enormous fascination. It is possible to produce a program capable of playing the game and have a high degree of “computer win.”

Tic-tac-toe, also spelled tick tack toe, and alternatively called noughts and crosses, X’s and O’s, and many other names, is a pencil-and-paper game for two players, O and X, who take turns marking the spaces in a 3×3 grid, usually X going first. The player who succeeds in placing three respective marks in a horizontal, vertical or diagonal row wins the game.

Strategy:

A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table.

1.   Win: If you have two in a row, play the third to get three in a row.

2.   Block: If the opponent has two in a row, play the third to block them.

3.   Fork: Create an opportunity where you can win in two ways.

4.   Block Opponent’s Fork:

Option 1: Create two in a row to force the opponent into defending, as long as it does not result in them creating a fork or winning. For example, if “X” has a corner, “O” has the center, and “X” has the opposite corner as well, “O” must not play a corner in order to win. (Playing a corner in this scenario creates a fork for “X” to win.)

Option 2: If there is a configuration where the opponent can fork, block that fork.

5.   Center: Play the center.

6.   Opposite Corner: If the opponent is in the corner, play the opposite corner.

7.   Empty Corner: Play in a corner square.

8.   Empty Side: Play in a middle square on any of the 4 sides.

The first player, whom we shall designate “X,” has 3 possible positions to mark during the first turn. Superficially, it might seem that there are 9 possible positions, corresponding to the 9 squares in the grid. However, by rotating the board, we will find that in the first turn, every corner mark is strategically equivalent to every other corner mark. The same is true of every edge mark. For strategy purposes, there are therefore only three possible first marks: corner, edge, or center. Player X can win or force a draw from any of these starting marks; however, playing the corner gives the opponent the smallest choice of squares which must be played to avoid losing.

The second player, whom we shall designate “O,” must respond to X’s opening mark in such a way as to avoid the forced win. Player O must always respond to a corner opening with a center mark, and to a center opening with a corner mark. An edge opening must be answered either with a center mark, a corner mark next to the X, or with an edge mark opposite the X. Any other responses will allow X to force the win. Once the opening is completed, O’s task is to follow the above list of priorities in order to force the draw, or else to gain a win if X makes a weak play.

Checkers Game

Checkers is one of the oldest and simplest of board games. Known as draughts in Britain, the game’s history goes back approximately 3,000 years. An early version was discovered in an archeological dig in the city of Ur, in what is now Iraq, but it was much later, in the 12th century, that the game was played on a chessboard with 12 pieces per player.

Rules

The game is played on a square board divided into 64 smaller squares, colored alternately in two colors. Traditionally the colors are red and black, but any combination of light and dark will do. The pieces are also often red and black, but can be any two colors. They’re designated “black and white” in instruction books in any case, so the players sometimes arbitrarily assign light and dark values to the colors at hand. The pieces are placed on the dark squares at both ends of the board. As in chess, the “white” player goes first. A single checker can only move forward one square diagonally and only into an empty space. A piece that has been “kinged” can move backward, also one square diagonally.

To “king” a piece, that piece must land on one of the four dark squares at the far end of the board. Then a spare or captured checker is placed on top of the kinged piece and it can move in any direction on the board.

To capture your opponent’s piece, you jump it. The jumped piece must be diagonally adjacent to your piece and there must be an open space on the other side. You jump to the open space, and remove the captured piece from the board. You can make multiple jumps if landing in the open space places you in position to jump another piece. If you can jump, you must.

The player who captures all of his opponent’s pieces wins the game.

Strategy

  1. Think ahead. Set up jumping moves, even if it means sacrificing one of your own pieces.
  2. Block your king’s row as long as you can.
  3. Do not let your pieces get bunched up in the center of the board.
  4. Near the end of the game, keep your kings in the center of the board. Pieces in the center have more movement options.

Dining Philosophers

Five philosophers are sitting around a circular table. On the table is a bowl of noodles. Between each pair of philosophers is a chopstick laid out on the table such that the first philosopher’s right chopstick is the left chopstick of the second philosopher, whose right chopstick is the left chopstick of the third philosopher and so forth. Hence, there are five chopsticks available in total.

Each philosopher thinks for a while, then gets hungry and decides to eat. In order to eat, a philosopher has to have a pair of chopsticks. He picks up the chopsticks on either side of him to grab some noodles from the bowl and then eats. If one of the chopsticks is already being used, the philosopher must wait for it to become available.

In a concurrent system, each philosopher is implemented as a thread and each chopstick is a shared resource. The intuitive approach to solving this problem is to have each philosopher first pick up his left chopstick then his right. However, this will lead to deadlock as all four of the necessary and sufficient conditions for deadlock come into play: blocking shared resources (chopsticks), no pre-emption (one philosopher cannot ask his adjacent to drop their chopsticks), holding while acquiring (a philosopher holds his left chopstick before trying to pick up his right) and circular waiting (each philosopher shares chopsticks).

Clearly, our naive scheme does not quite work as planned. However, as all conditions for deadlock are both necessary and sufficient, we should be able to prevent the deadlock by breaking any one of the conditions above. An obvious way around this is that philosophers who can’t get both chopsticks should put them down, go back to thinking and try again later. This is trying to break the third deadlock property above: ‘holding while acquiring’. However, if the philosophers are unlucky and keep doing this all in synchrony, none of them will actually get to eat! Each will drop a chopstick only to try and grab it once more. This solution breaks the problem of deadlock but in doing so, we have introduced another potential problem – that of livelock. The philosophers will not slowly stop but instead can just go round in circles trying to decide who should have the chopsticks but never getting anywhere. The philosophers will not eat and will starve (quite literally!). This solution isn’t much good either. There are several possible viable solutions that solve both the issue of deadlock and ensure liveness, four of which are presented here:

• Order the chopsticks, so that the philosopher has to pick up chopstick N, then chopstick N+1. This means that one of the philosophers will pick up his right chopstick first, while all of the others are picking up the left chopstick first. This is the same as having odd numbered philosophers pick up their chopsticks left/right, and even numbered philosophers pick up theirs right/left. This solution relies on breaking the circular wait. In addition, every philosopher will get to eat at some point.

• A philosopher who wants to eat first picks up the sole saltshaker on the table, then picks up his chopsticks, eats and then puts the saltshaker back. This solution while viable is not great, as it means that only one philosopher can eat at any one time. This solution breaks the ‘holding while acquiring’ deadlock condition and if we further stipulate that the philosophers agree to go around the table and pick up the salt shaker in turn, this solution is also fair and ensures no philosopher starves.

• Each philosopher flips a coin. Heads, he picks up the right chopstick first, tails, the left. If the second chopstick is busy, he puts down the first and tries again. With probability 1, he will eventually eat. Again, this solution relies on defeating circular waiting whenever possible and then resorts to breaking ‘acquiring while holding’ as assurance for the case when two adjacent philosophers’ coins both come up the same. Again, this solution is fair and ensures all philosophers can eat eventually.

• The chef sees the philosopher’s predicament; a scorn the philosopher for letting his fine meal of noodles go cold and agrees with the philosophers that he will dictate who should eat and when to prevent any confusion. This breaks the ‘blocking shared resources’ condition. The chef assures all philosophers that when they try to pick up their chopsticks, they will be free. Effectively the chef enforces a fair, serialized schedule of chopstick use over the philosophers. This is the most efficient solution (no shared resources/locking involved) but is in practice the hardest to achieve (the chef must know how to instruct the philosophers to eat in a fair, interference-free fashion). [Aside: For the curious, if we number the philosophers 1 to 5, one such schedule would be (3, 5)->(1, 4)->(2, 4)->(1, 3)->(5, 2) or any permutation thereof. This always ensures each philosopher can pick up both chopsticks in turn, is fair - each philosopher gets to eat twice during the schedule - and will neither deadlock nor starve.]

•  The philosophers use a pre-emption scheme based on hunger. As a philosopher nears starvation, his hunger index rises above the “acquire while holding” value of one or both of his neighbors; at that point, they must relinquish the use of their chopsticks and allow the starving philosopher to eat. Once the hungry philosopher is satiated, his hunger index drops below the value of another starving philosopher’s index and he has to give up his chopsticks.

The 8 Puzzle

The 8-puzzle also known as the sliding-block/tile-puzzle is one of the most popular instruments in the artificial intelligence studies. It belongs to AI exercises commonly referred as toy-problems.

Arrange the tiles so that all the tiles are in the correct positions. You do this by moving tiles.  You can move a tile up, down, left, or right, so long as the following conditions are met:

  1. There’s no other tile blocking you in the direction of the movement;
  2. You are not trying to move outside of the boundaries/edges.

Toy Problems

September 4, 2010 Leave a comment
a tic tac toe game

Image via Wikipedia

In mathematics and information science, a toy problem is a problem that is not of immediate scientific interest, yet is used as an expository device to illustrate a trait that may be shared by other, more complicated, instances of the problem, or as a way to explain a particular, more general, problem solving technique.

Why is games fun? In part, because they challenge our ability to think. Even simple games like Tic-Tac-Toe, Nim and Kalah, or puzzles like the Eights Puzzle, are challenging to children. More complex games like checkers, chess, bridge, and Go are difficult enough that it takes years for gifted adults to master them. Nearly all games require seeing patterns, making plans, searching combinations, judging alternative moves, and learning from experience, all being skills which are also involved in many daily tasks.

It’s no surprise that Alan Turing proposed chess playing as a good project for studying computers’ ability to reason. In many ways, games have provided simple proving grounds for many of AI’s powerful ideas.

Follow

Get every new post delivered to your Inbox.