Inside Technique : IE DHTML Connect Four
By Erik Arvidsson

Brought to you from our friends at WebFX

This is one of the more classic "board" games. Connect Four is traditionally for two players. The goal is to get four tokens of your own color in a row. Once a player gets four tokens in a row they wins. If the board is completely filled before anyone gets four in a row, the game ends in a draw. In the non-virtual game, the board is standing up so all the tokens fall down as far as possible.

Playing the Game

Our DHTML version is played against a computer player. To place your token on the board, you click on a column. When you start the game, you can change the level of the computer skill. Selecting a higher value makes the computer much smarter but leads to a really long wait. (More about this in the algorithm explanation.)

Play the game (IE4+ Only)

The Interface

The interface is made without any images. Instead the circle symbol from the Webdings font has been heavily used. While our version requires Internet Explorer 4.0 or later, by rebuilding the interface with images you should be able to create a cross-browser version that runs on Netscape Navigator 3.x or later. The dialogue window is just a basic positioned element. The border is once again made with the circle symbol of the webdings font.

The Computer Algorithm

The algorithm used to calculate the moves of the computer is called the minimax method and it is one of the most used algorithms for board games. The basic idea is to calculate a value of the current game state. During the computer's turn the computer tries to maximize this value. To prevent the computer from performing a bad move the computer must also see a few steps ahead. For example in chess the player might think that it is good to take a pawn, but in the next move he might loose his queen, which might be exactly the right thing to do if it leads to victory. The algorithm creates (implicitly) a game tree where it alternates between selecting the largest respectively the smallest value (representing the computer and human doing the best possible moves) at each level.

Below is some pseudo code to show you how it works. The computer is playing black and thus tries to maximize its value while minimizing the white's values. One thing to notice is that an actual value of how good the sequence of moves are is only calculated a leaf node.

value = -Infinity

for each position pos that is a successor of currentPlayState do
   b = black(pos, depth)
   if b >= value then
      value = b
      bestMove = pos

Where the functions black and white are defined as follows:

	  
function black(pos, depth)
   if depth == 0 or pos has no successor then
      return eval(pos)
   else
      return min{white(x, depth-1) | x is a successor of pos}
	  
function white(pos, depth)
   if depth == 0 or pos has no successor then
      return eval(pos)
   else
      return max{black(x, depth-1) | x is a successor of pos}

These function can be combined to one and there is also a need to check whether there is a winner (or draw) before reaching a leaf.

Improving the Performance

While the performance of this game is fairly poor (it is due the slowness of JScript) there are some tricks performed that slightly improves the performance. The main improvement is made with Alpha- Beta pruning. The basic idea is to eliminate subtrees that can't improve the result. For example if you want the max value at a level and you get a value that is smaller than the previous max you are sure that you can't get anything better because the level below is taking the min value. This is much easier understood with an example.

        --------------A--------------       max
       /              |              \
      B               C               D     min
   /  |  \          /   \           /   \
 E    F   G       H      I         J     K  max
/ \  / \ / \     / \    / \       / \   / \
L M  N O P Q     R S    T U       V W   X Y min
7 6  8 5 2 3     0 -2   6 2       5 8   9 2

Start to reduce this tree from the left

        --------------A--------------       max
       /              |              \
      B               C               D     min
   /  |  \          /   \           /   \
 E    F   G       H      I         J     K  max
 6    5   2      / \    / \       / \   / \
                 R S    T U       V W   X Y min
                 0 -2   6 2       5 8   9 2


        --------------A--------------       max
       /              |              \
      B               C               D     min
      6               2             /   \
                                   J     K  max
                                   5    / \
                                        X Y min
                                        9 2

Now there is no need to calculate the value from the tree K because A will get the value 2 whatever value K returns (try for yourself).

© 1997-2000 InsideDHTML.com, LLC. All rights reserved.