Four In A Row #2

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:  

  • To begin a game, click on one of the buttons in the Select Opponents box on the right side of the screen.  This option is reset after each game, so  just click to start again.  
  • The "IQ" level actually controls how many moves ahead the program searches when selecting the best move.  It is possible that you can set this number so high that you will not want to wait for the analysis to complete.   Click the Stop button at any time while the "Thinking.." caption is displayed will interrupt the search and play the best move found so far.   
  • You can control the board size using the  option in the lower right side of the screen.   The Alpha-Beta pruning checkbox causes the program to use a more efficient search algorithm, and should probably  be checked (unless you want to help  debug the program <g> ).
  • You can use the Retract Move and Suggest  buttons anytime that your opponent will allow it (or isn't looking).    The computer opponent generally will not let you interrupt until the game is over.  You can then backup and replay as many steps as you choose.  Just use the Suggest button to recreate the moves that the computer would have made.  

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 1020 and 1030 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

I'm sure that  the current scoring algorithm could be improved.   For example, two of tokens in line with an empty slot and another matching token should be worth more than two tokens followed by an opponent's token.   
Alpha-Beta efficiency depends to a large extent on picking the "most likely" high or low paths first.  Doing so eliminates more path searches.   Lots of room for speed improvement here. 
Somewhere in my travels through the web I ran across a description of a minimax implementation with search depth based on time rather than levels.  Shouldn't be too difficult to implement and would allow faster computers to search deeper with, say, a max "think" time of 5 or 10 seconds.
Computer play would look a little more "thoughtful" and less mechanical if we accumulated  best moves with equal scores and then randomly selected one of those.   Currently the first such  is always  chosen.  

 

Original:  May 25, 2002

Modified:  February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.