connect4

commit 35bb10a39a08c9720a438a23ad6791a1f6019d6e
parent a551afc5bdfc6b7045365fac8b37c49bdd103ce1
Author: sej <sej@sejdt.localhost>
Date:   Tue, 29 Oct 2024 13:42:44 +0100

Minimax fix, including slight change to the heuristic

Diffstat:
M
Minimax.cs
 | 
72
+++++++++++++++++++++++++++++++++++++++++++++++-------------------------

1 file changed, 47 insertions(+), 25 deletions(-)
diff --git a/Minimax.cs b/Minimax.cs
@@ -10,74 +10,96 @@ public class Minimax {
         }
 
         public int BestMove() {
-            List< int > moves = _root.Board.LegalMoves();
-            int bestIndex = 0;
-            int bestScore = Int32.MinValue;
+            List< int > moves = _root.GameState.LegalMoves();
+            int maxIndex = 0;
+            int minIndex= 0;
+            int maxScore= Int32.MinValue;
+            int minScore = Int32.MaxValue;
+
             for ( int i = 0; i < moves.Count; i++ ) {
-                if ( _root.Children[i].Minimax( true ) > bestScore ) {
-                    bestIndex = i;
+                Console.WriteLine( _root.Children[i].Minimax() );
+                int minimaxScore = _root.Children[i].Minimax();
+                if ( minimaxScore > maxScore ) {
+                    maxIndex = i;
+                }
+                if ( minimaxScore < minScore ) {
+                    minIndex = i;
                 }
             }
-            return moves[ bestIndex ];
+            return ( _root.GameState.GetNext() == Board.Cell.PlayerX ) ? maxIndex : minIndex;
         }
 
         private class Node {
-            public Board Board;
+            public Board GameState;
             public Node[] Children;
             
             public Node( Board board, int depth ) {
-                Board = board;
-                List< int > legalMoves = Board.LegalMoves();
-                Children = new Node[ legalMoves.Count ];
-                if ( depth > 0 ) {
+                GameState = board;
+                List< int > legalMoves = GameState.LegalMoves();
+                if ( depth == 0 ) {
+                    Children = new Node[0];
+                } else { // depth > 0
+                    Children = new Node[ legalMoves.Count ];
                     for ( int i = 0; i < Children.Length; i++ ) {
                         Board child = new Board( board );
+
                         child.Play( legalMoves[i] );
+
+                        Node childNode = new Node( child, depth - 1 );
+                        /*
                         child.PrettyPrint();
-                        Children[i] = new Node( child, depth - 1 );
+                        Console.Write( $"score: { childNode.HeuristicScore() } " );
+                        Console.Write( $"move: { i } " );
+                        Console.Write( $"depth: { depth }" );
+                        Console.Write( "\n" );
+                        Console.WriteLine( "-----" );
+                        */
+                        Children[i] = childNode;
                     }
                 }
             }
 
-            public int Minimax( bool isMax ) {
+            public int Minimax() {
                 if ( Children.Length == 0 ) { // leaf node 
                     return HeuristicScore();
                 } else {
                     int[] scores = new int[ Children.Length ];
                     for ( int i = 0; i < Children.Length; i++ ) {
-                        scores[i] = Children[i].Minimax( !isMax );
+                        scores[i] = Children[i].Minimax();
                     }
-                    return isMax ? scores.Max() : scores.Min();
+                    return ( GameState.GetNext() == Board.Cell.PlayerX ) ? scores.Max() : scores.Min();
                 }
             }
 
             /*
              * Computes a simple heuristic rating for the given board.
              * The rating is given by:
-             * l_2 * w_1 + l_3 * w_2 + w_3 * l_4
-             * where l_k is the number of k in a row
+             * ( X_2 * w_1 + X_3 * w_2 + X_3 * X_4 ) -
+             * ( O_2 * w_1 + O_3 * w_2 + O_3 * O_4 )
+             * where X_k is the number of X k in a row
              * w_3 obviously has to be infty
+             * X is maximizer
+             * O is minimizer
              */
             private int HeuristicScore() {
-                Board.Status status = Board.GetStatus();
+                Board.Status status = GameState.GetStatus();
                 if ( status != Board.Status.InProgress ) {
                     if ( status == Board.Status.Draw ) {
                         return 0;
-                    } else { // status == Board.Status.PlayerXWon || status == Board.Status.PlayerOWon
+                    } else if ( status == Board.Status.PlayerXWon ) {
                         return Int32.MaxValue;
+                    } else { // status == Board.Status.PlayerOWon
+                        return Int32.MinValue;
                     }
                 }
 
                 int score = 0;
                 int[] weight = new int[] { 0, 1, 4, 8 };
 
-                Board.Cell previous = Board.GetPrevious();
-                Board.Cell next = Board.GetNext();
-
-                for ( int r = 0; r < 4; r++ ) {
+                for ( int r = 2; r < 4; r++ ) {
                     score += weight[r] * ( 
-                        Board.NumberQInRow( r, previous ) - 
-                        Board.NumberQInRow( r, next ) 
+                        GameState.NumberQInRow( r, Board.Cell.PlayerX ) -
+                        GameState.NumberQInRow( r, Board.Cell.PlayerO )
                     );
                 }