[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

Version 2 of Four-In-A-Row adds a couple of significant enhancements to the previously published Version 1. The objective is the same, the winner being the first player to get a specified number of tokens in line, horizontally, vertically, or diagonally, filling each column from the bottom.    In this version however, the user specifies how many tokens are required to win.  Board size is also user controlled from 3X3 to 8X8 columns and rows. 

We've also added computer play.  The computer will play Red (first move) or Yellow (second move), or both.  "IQ" can be set to control the how smart the players are.  Well, for the human player, all we can do is control the program's smartness level when the human asks the program to suggest a move.   

Background & Techniques

A couple of notes for non-programmers:  

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

Programmers may want to review the Version 1 page for some of the mechanics of the program graphics and token manipulation.  Most of that code remains intact in this version .  

Dynamic Board Size

The Board array, and a few others that depend on column and row counts are now dynamic arrays.  This required all row and column indexing  be changed to zero based.   The FourInARow  function now checks for the current Winnbr variable value, not necessarily 4. 

Minimax

Minimax is a clever. but non-trivial technique,  for searching for good moves by looking ahead at all possibilities.   In non-trivial games, the number of possibilities is too large to allow checking all possibilities, so we limit the search to some maximum number of levels to search.   There are probably between 10²⁰ and 10³⁰ move possibilities to check in our game on a 6X7 board.  The "IQ" level fields correspond to look-ahead levels of 3 to 10 with  more levels equating to higher "IQ".    The Score procedure determines the score at that level by counting how many  tokens we have in a row minus the number that our opponent has.   The idea is that any move the maximizes that difference is probably a good move.   There are many discussions of Minimax available in textbooks and on the web, so I won't go into great detail here.  Briefly, we use procedure MiniMax to recursively search LookAhead levels  down the game tree  and evaluate those positions.  At any level, If the  level number is odd (our move), we can assume that the previous level player (our opponent)  will pick the one that is best for him, worst for for us, i.e. the minimum of the possible scores.  Working back up the line, from all the possible scores thus derived for our opponent , we'll pick the one that is best for us  (the maximum), etc.  until we get back to the top level.  At each level we alternate choosing minimum and maximum scores of the children (next possible moves)  thus the name minimax.     

Alpha-Beta Search Pruning

Alpha-Beta pruning is an efficiency enhancement that can eliminate searching many children of our game tree.   Suppose we have searched one path down  LookAhead levels, say the one where we move to column 4 and have a value of 10 for that path.  We're going to select the maximum of all of the path values we receive, so we know that our final score will be 10 or more.   Now we start checking, say a move to column 3.  To do that we'll be looking down to level 2 at our opponent's move, who will in turn be selecting the minimum of all of our possible move scores at level 3.  Suppose he checks the first level 3  path which returns a score of 5.  Since he will be selecting the minimum of all of the choices, he certainly won't be selecting anything larger that 5.  And since at level 1, we'll be taking the maximum of all of the level 2 choices,  we won't be using that score of 5 or less,( remember we already have a 10 from our first search).   So we can prune the level 2 search once we have any value less than 10,  and not even bother to check the other level 3 children.  This can eliminate 50% or even 90% of the path searches required while producing results  identical to the original procedure.  The MinimaxAB procedure implements Alpha-Beta pruning in this program.. 

NegMax

NegMax is the name applied to a minimax implementation developed by Donald Knuth which realizes that rather than alternate taking maximum child scores for odd levels and minimum child scores for even levels, we can take the maximum of the negatives of our child scores at each level.  (For even levels, when we want the minimum of the children's scores,  take the maximum if the negatives of the set of choices.  For odd levels, where we want the maximum,  we'll take the maximum of the negatives of the  values provided to us by the children.  Since these values have already had their values reversed once, this second reversal puts us back to the original, non-negative numbers.)    I used the NegMax technique, but  can't say that I fully understand it, and kind of wish that I hadn't   It does seem to work though, and probably saved a few lines of code at the expense of making the code harder to understand and debug.   If I were to rewrite the minimax procedures, I believe that I would stick to original minimax algorithm.   

Debugging

Implementing the above was difficult, mainly because of the number of values generated at each step.  I finally implemented a dialog containing a Treeview with  values at each level as  the Minimax and MinimaxAB procedures run.  To avoid the overhead when not debugging, I used Conditional defines to generate the debug code  when parameter DEBUG was defined or to omit the code when DEBUG was not defined.    Even with the Treeview, following the code was not easy.  I did most of the debugging with a 3X3 game board requiring 3 in a row to win.  

Addendum: October 21, 2003:  A viewer recently requested a 3 human player version of the game and a larger board size.  It was posted today - It seems that  the MiniMax procedure used to compute moves and give suggestions is not applicable to 3 person games, although there may be adaptations for more than two players.  I haven't researched it (yet).    Maximum board size has been increased to 10 x 10.   I added a "think time" limit for computer move searches, since  I suspect that search space size and search time  increases exponentially with  IQ and board size.

As usual,  I added a couple of other enhancements - games between computers were always identical.    I added a few random moves at the beginning of each game to change that.   Lower IQ's make more random moves. 

Addendum: January 3, 2010:  Playing the "Wii Play" version of this game with a grandson over the holidays, I used this program to advise me on which moves to make.  I was embarrassed to find that the initial random moves "enhancement" sometimes allowed him an easy win by placing 4 adjacent token in his first 4 moves - the random moves assumed that there would be no winner that soon.  Version 2.2 posted today fixes the problem by limiting initial random moves to 2 or 3 turns.  

February 20, 2013:  It took a while, but a user finally found a bug with the 3-player option;  retracting (undoing) a move switches forward to the next rather than back to the previous player.  In the 2-player options it didn't matter of course but, with 3-players, "Retracting" = "Reset" time!  Version 2.3 posted today fixes the problem.       

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.