Minimax.cs (4289B)
1 using System; 2 3 public class Minimax { 4 5 private class MinimaxTree { 6 Node _root; 7 8 public MinimaxTree( Board rootBoard, int depth ) { 9 _root = new Node( rootBoard, depth ); 10 } 11 12 public int BestMove() { 13 List< int > moves = _root.GameState.LegalMoves(); 14 int maxIndex = 0; 15 int minIndex= 0; 16 int maxScore= Int32.MinValue; 17 int minScore = Int32.MaxValue; 18 19 for ( int i = 0; i < moves.Count; i++ ) { 20 Console.WriteLine( _root.Children[i].Minimax() ); 21 int minimaxScore = _root.Children[i].Minimax(); 22 if ( minimaxScore > maxScore ) { 23 maxIndex = i; 24 } 25 if ( minimaxScore < minScore ) { 26 minIndex = i; 27 } 28 } 29 return ( _root.GameState.GetNext() == Board.Cell.PlayerX ) ? maxIndex : minIndex; 30 } 31 32 private class Node { 33 public Board GameState; 34 public Node[] Children; 35 36 public Node( Board board, int depth ) { 37 GameState = board; 38 List< int > legalMoves = GameState.LegalMoves(); 39 if ( depth == 0 ) { 40 Children = new Node[0]; 41 } else { // depth > 0 42 Children = new Node[ legalMoves.Count ]; 43 for ( int i = 0; i < Children.Length; i++ ) { 44 Board child = new Board( board ); 45 46 child.Play( legalMoves[i] ); 47 48 Node childNode = new Node( child, depth - 1 ); 49 /* 50 child.PrettyPrint(); 51 Console.Write( $"score: { childNode.HeuristicScore() } " ); 52 Console.Write( $"move: { i } " ); 53 Console.Write( $"depth: { depth }" ); 54 Console.Write( "\n" ); 55 Console.WriteLine( "-----" ); 56 */ 57 Children[i] = childNode; 58 } 59 } 60 } 61 62 public int Minimax() { 63 if ( Children.Length == 0 ) { // leaf node 64 return HeuristicScore(); 65 } else { 66 int[] scores = new int[ Children.Length ]; 67 for ( int i = 0; i < Children.Length; i++ ) { 68 scores[i] = Children[i].Minimax(); 69 } 70 return ( GameState.GetNext() == Board.Cell.PlayerX ) ? scores.Max() : scores.Min(); 71 } 72 } 73 74 /* 75 * Computes a simple heuristic rating for the given board. 76 * The rating is given by: 77 * ( X_2 * w_1 + X_3 * w_2 + X_3 * X_4 ) - 78 * ( O_2 * w_1 + O_3 * w_2 + O_3 * O_4 ) 79 * where X_k is the number of X k in a row 80 * w_3 obviously has to be infty 81 * X is maximizer 82 * O is minimizer 83 */ 84 private int HeuristicScore() { 85 Board.Status status = GameState.GetStatus(); 86 if ( status != Board.Status.InProgress ) { 87 if ( status == Board.Status.Draw ) { 88 return 0; 89 } else if ( status == Board.Status.PlayerXWon ) { 90 return Int32.MaxValue; 91 } else { // status == Board.Status.PlayerOWon 92 return Int32.MinValue; 93 } 94 } 95 96 int score = 0; 97 int[] weight = new int[] { 0, 1, 4, 8 }; 98 99 for ( int r = 2; r < 4; r++ ) { 100 score += weight[r] * ( 101 GameState.NumberQInRow( r, Board.Cell.PlayerX ) - 102 GameState.NumberQInRow( r, Board.Cell.PlayerO ) 103 ); 104 } 105 106 return score; 107 } 108 } 109 } 110 111 /* 112 * Returns the best move for the next player's turn on the given board. 113 */ 114 public static int BestMove( Board board, int depth ) { 115 MinimaxTree tree = new MinimaxTree( board, depth ); 116 return tree.BestMove(); 117 } 118 }