Game Trees


Trees can be useful when it comes to the analysis of games such as tic-tac-toe, chess, and checkers. In order to explain the concept of a game tree, we will focusing on tic-tac-toe and develop game-playing strategies. The game trees are applied in the same way for chess and checkers; but because those games have game trees so large that it is not feasible to generate the entire tree here.

The beginning of a tic-tac-toe game tree with symmetric positions omitted will look like this:

When we use a game tree, we should use a depth-first search. A partial game tree for tic-tac-toe is shown below. Each node represents a move by a player. Taking a quick glance at the first node, a person can easily identify that the X player is winning if O player allows him to complete a vertical line on the left-most column. A person will not hesitate a second to put a circle between two X on the left-most column. But a computer must go through the entire game tree in order to come up with a best move. This is a difference between human mind and machine that uses game tree algorithm. This might be seen awkward and unintelligent for simple game like tic-tac-toe which an experienced person can almost foresees the result by the first 3 moves, but for more complicated game like chess, a search of the entire tree for the best move is indeed very important and is even capable of beating a human player. In the following diagram, both best move and worst moves are shown in the 2nd level of tree.

Tic-tac-toe is a fun but relatively easy game. The result is always a tie if both players are to play to the best moves. In general, the best move for the first player is the one at the middle. If the 2nd player doesn't follow up with a move at one of the corner, he can said to be lost as there is a winning strategy that follows.

When humans play humans it happens that they beat each others. The reason for this has to do with how humans think. It is reasonable to assume that your opponent will do a best possible move. However a player might do one irrational move and with that generate a double threat and thus winning. This is because the non-irrational player does not see the possibility of the double threat.

A tic-tac-toe algorithm without thorough implementation can also be beaten by human.

Binary Search Trees - Vertex Coloring - Mapping - File Compression - Electronic Circuits