commit c10d83b7227cde70faaeb948068a9393cdb52fce
parent 4527dd1499f5e38288558417a817418cdd5dad94
Author: sej <sej@sejdt.localhost>
Date: Thu, 24 Oct 2024 16:24:01 +0200
Minimax hopefully works
Diffstat:
| M | Minimax.cs | | | 95 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------- |
1 file changed, 68 insertions(+), 27 deletions(-)
diff --git a/Minimax.cs b/Minimax.cs
@@ -3,52 +3,93 @@ using System;
public class Minimax {
private class MinimaxTree {
+ Node _root;
+
public MinimaxTree( Board rootBoard, int depth ) {
- Node root = new Node( rootBoard, depth );
+ _root = new Node( rootBoard, depth );
}
- public int Minimax() {
- return 0;
+ public int BestMove() {
+ List< int > moves = _root.Board.LegalMoves();
+ int bestIndex = 0;
+ int bestScore = Int32.MinValue;
+ for ( int i = 0; i < moves.Count; i++ ) {
+ if ( _root.Children[i].Minimax( true ) > bestScore ) {
+ bestIndex = i;
+ }
+ }
+ return moves[ bestIndex ];
}
private class Node {
- private Board _board;
- private List< Node > _children;
+ public Board Board;
+ public Node[] Children;
public Node( Board board, int depth ) {
- _board = board;
- _children = new List< Node >();
+ Board = board;
+ List< int > legalMoves = Board.LegalMoves();
+ Children = new Node[ legalMoves.Count ];
if ( depth > 0 ) {
- foreach ( int move in board.LegalMoves() ) {
+ for ( int i = 0; i < Children.Length; i++ ) {
Board child = new Board( board );
- child.Play( move );
- // child.PrettyPrint();
- _children.Add( new Node( child, depth - 1 ) );
+ child.Play( legalMoves[i] );
+ child.PrettyPrint();
+ Children[i] = new Node( child, depth - 1 );
}
}
}
- }
- /*
- * Computes a simple heuristic rating for the given board.
- * The rating is given by:
- * n_2 * w_1 + n_3 * w_2 + w_3 * n_4
- * where n_k is the number of k in a row that has the potential to become 4 in a row (ie. not blocked).
- * n_4 obviously has to be infty
- * n_2 and n_3 are set to 1, and 2, respectively.
- */
- private static int HeuristicScore( Board board ) {
- // TODO
- return 0;
+ public int Minimax( bool isMax ) {
+ 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 );
+ }
+ return isMax ? 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
+ * w_3 obviously has to be infty
+ */
+ private int HeuristicScore() {
+ Board.Status status = Board.GetStatus();
+ if ( status != Board.Status.InProgress ) {
+ if ( status == Board.Status.Draw ) {
+ return 0;
+ } else { // status == Board.Status.PlayerXWon || status == Board.Status.PlayerOWon
+ return Int32.MaxValue;
+ }
+ }
+
+ 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++ ) {
+ score += weight[r] * (
+ Board.NumberQInRow( r, previous ) -
+ Board.NumberQInRow( r, next )
+ );
+ }
+
+ return score;
+ }
}
}
/*
* Returns the best move for the next player's turn on the given board.
*/
- public static int NextMove( Board board, int depth ) {
- MinimaxTree tree = new MinimaxTree( board, depth );
- int bestMove = tree.Minimax();
- return bestMove;
+ public static int BestMove( Board board, int depth ) {
+ return 0;
}
}
