Skip to main content

A board game in MVVM Part 2 - The AI

This is a continuation of my experience creating a quick board game in silverlight 5
Original Post
Part 1 - The Model
Play the Game

AI Thinking Image

The AI code was already included in the source supplied from the previous post in "The Model". The idea was to use minimax with alpha-beta pruning. This was pretty difficult for me because it'd been so long since I'd done any AI. I wanted to get at least 3 steps into a minimax tree. After completion, that's about all I could do. Any deeper took unreasonably long wait time especially if the AI is playing as the attacker (more moves to consider).

A big note on the AI: No, it's not perfect. Actually, it could use a lot of tweaking and improving. However, building the "Perfect AI" was never in the scope of the project. The minimax and alpha-pruning might be off and it definitely could use some speed-up. However, thinking 3 phases ahead in the game cycle is sufficient for a good challenge. You will notice several tendencies the AI does every time and if I pit the AI against itself it could very likely end up playing the same moves over and over again. However, against a human player it's good enough to play a decent game against.

I did a few minor tasks in speeding it up such as moving several functions to static and producing AI versions of the classes that don't fire extra events but this optimization wouldn't be a night and day difference anyway. Any suggestions for any of this is of course welcome.

As you can see in the code I used 2 enums to distinguish the players. Player and PlayerType:

  1. namespace Viking
  2. {
  3.     public enum Player
  4.     {
  5.         Attacker,
  6.  
  7.         Defender
  8.     }
  9.  
  10.     public enum PlayerType
  11.     {
  12.         Human,
  13.  
  14.         AI
  15.     }
  16. }

These are used in distinguishing which player's turn it is, and what type of player that is. Knowing what the current player is that the AI is evaluating is important in knowing how to treat the score. In the minimax implementation I use the following functions to decide the score of the various moves:
  1.         public static double DecideMove(DecisionBoard node, int depth, double alpha, double beta, Player player)
  2.         {
  3.             Player nextPlayer = player == Player.Attacker ? Player.Defender : Player.Attacker;
  4.             if (depth == 0)
  5.             {
  6.                 return node.Score();
  7.             }
  8.             else if (player == node.AIPlayer)
  9.             {
  10.                 List<Tuple<IPiece, ISquare>> validMoves = Board.ListValidMoves(Board.ListMoveablePieces(node, player));
  11.                 for (int i = 0; i < validMoves.Count; i++)
  12.                 {
  13.                     DecisionBoard child = new DecisionBoard(node, node.AIPlayer, player);
  14.                     Board.MakeMove(child, child.IndexedSquares[validMoves[i].Item1.Location.Coords].Occupant, child.IndexedSquares[validMoves[i].Item2.Coords]);
  15.                     if (!Board.CheckWin(child, player))
  16.                     {
  17.                         child.CurrentPlayer = nextPlayer;
  18.                         alpha = Math.Max(alpha, DecideMove(child, depth - 1, alpha, beta, child.CurrentPlayer));
  19.                         if (beta <= alpha)
  20.                         {
  21.                             break;
  22.                         }
  23.                     }
  24.                     else
  25.                     {
  26.                         alpha = double.PositiveInfinity;
  27.                         break;
  28.                     }
  29.                 }
  30.  
  31.                 return alpha;
  32.             }
  33.             else
  34.             {
  35.                 List<Tuple<IPiece, ISquare>> validMoves = Board.ListValidMoves(Board.ListMoveablePieces(node, player));
  36.                 foreach (Tuple<IPiece, ISquare> move in validMoves)
  37.                 {
  38.                     DecisionBoard child = new DecisionBoard(node, node.AIPlayer, player);
  39.                     Board.MakeMove(child, child.IndexedSquares[move.Item1.Location.Coords].Occupant, child.IndexedSquares[move.Item2.Coords]);
  40.                     if (!Board.CheckWin(child, player))
  41.                     {
  42.                         child.CurrentPlayer = nextPlayer;
  43.                         beta = Math.Min(beta, DecideMove(child, depth - 1, alpha, beta, child.CurrentPlayer));
  44.                         if (beta <= alpha)
  45.                         {
  46.                             break;
  47.                         }
  48.                     }
  49.                     else
  50.                     {
  51.                         beta = double.NegativeInfinity;
  52.                         break;
  53.                     }
  54.                 }
  55.  
  56.                 return beta;
  57.             }
  58.         }

  1.         public double Score()
  2.         {
  3.             double score = 0;
  4.             bool win = Board.CheckWin(this, CurrentPlayer);
  5.             if (win)
  6.             {
  7.                 score = CurrentPlayer == AIPlayer ? double.PositiveInfinity : double.NegativeInfinity;
  8.             }
  9.             else
  10.             {
  11.                 for (int i = 0; i < Pieces.Count; i++)
  12.                 {
  13.                     if (Pieces[i].Player == AIPlayer)
  14.                     {
  15.                         score += PieceScoreMultiplier;
  16.                     }
  17.                     else
  18.                     {
  19.                         score -= PieceScoreMultiplier;
  20.                     }
  21.                 }
  22.             }
  23.  
  24.             return score;
  25.         }

These functions handle the scoring of the move possibilities, assuming that the opponent will make the best possible move he can. The master controller that sets off the whole process is this:
  1.         public static Tuple<IPiece, ISquare, double> DecideMove(DecisionBoard node, int depth, Player player)
  2.         {
  3.             List<Tuple<IPiece, ISquare>> validMoves = Board.ListValidMoves(Board.ListMoveablePieces(node, player));
  4.             Tuple<IPiece, ISquare, double> bestMove = null;
  5.             double alpha = double.NegativeInfinity;
  6.             double beta = double.PositiveInfinity;
  7.             Player nextPlayer = player == Player.Attacker ? Player.Defender : Player.Attacker;
  8.             foreach (Tuple<IPiece, ISquare> move in validMoves)
  9.             {
  10.                 DecisionBoard child = new DecisionBoard(node, node.AIPlayer, player);
  11.                 Board.MakeMove(child, child.IndexedSquares[move.Item1.Location.Coords].Occupant, child.IndexedSquares[move.Item2.Coords]);
  12.                 if (Board.CheckWin(child, player))
  13.                 {
  14.                     bestMove = new Tuple<IPiece, ISquare, double>(move.Item1, move.Item2, double.PositiveInfinity);
  15.                     break;
  16.                 }
  17.                 else
  18.                 {
  19.                     child.CurrentPlayer = nextPlayer;
  20.                     double moveScore = DecideMove(child, depth - 1, alpha, beta, child.CurrentPlayer);
  21.                     if (bestMove == null || moveScore > bestMove.Item3)
  22.                     {
  23.                         bestMove = new Tuple<IPiece, ISquare, double>(move.Item1, move.Item2, moveScore);
  24.                     }
  25.                 }
  26.             }
  27.  
  28.             return bestMove;
  29.         }

It'll take an immediate win if it sees it, and otherwise will defer to the move with the best probably outcome assuming both players are playing at their best.

However, one of the most important things in a game nowadays is responsiveness. The player needs to know that things haven't just crashed while the AI is thinking. That's where the code in "Game" comes in. It runs the entire UI in a BackgroundWorker. This allows the UI to continue updating, even though the AI is cranking away at a solution.

Every time players in the game switch, be sure to check AI:

  1.         private void SwitchPlayers()
  2.         {
  3.             CurrentPlayer = CurrentPlayer == Player.Attacker ? Player.Defender : Player.Attacker;
  4.             Board.ActivePiece = null;
  5.             Board.ResetValidMoves();
  6.             Board.SetMoveablePieces(CurrentPlayer);
  7.             CheckAI();
  8.         }
  9.  
  10.         private void CheckAI()
  11.         {
  12.             if ((CurrentPlayer == Player.Attacker && Attacker == PlayerType.AI)
  13.                     || (CurrentPlayer == Player.Defender && Defender == PlayerType.AI))
  14.             {
  15.                 CurrentAIWorker = new BackgroundWorker();
  16.  
  17.                 CurrentAIWorker.RunWorkerCompleted += new RunWorkerCompletedEventHandler(AI_RunWorkerCompleted);
  18.                 CurrentAIWorker.DoWork += new DoWorkEventHandler(AI_DoWork);
  19.  
  20.                 DecisionBoard decisions = new DecisionBoard(Board, CurrentPlayer, CurrentPlayer);
  21.                 IsBusy = true;
  22.                 IsActive = false;
  23.                 CurrentAIWorker.RunWorkerAsync(decisions);
  24.             }
  25.         }

CheckAI started up a BackgroundWorker. This is what the BackgroundWorker is doing:
  1.         private void AI_DoWork(object sender, DoWorkEventArgs e)
  2.         {
  3.             DecisionBoard decisions = e.Argument as DecisionBoard;
  4.             Tuple<IPiece, ISquare, double> move = DecisionBoard.DecideMove(decisions, 3, CurrentPlayer);
  5.             e.Result = move;
  6.         }

And when it's done:
  1.         private void AI_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
  2.         {
  3.             BackgroundWorker worker = sender as BackgroundWorker;
  4.             worker.RunWorkerCompleted -= AI_RunWorkerCompleted;
  5.             IsBusy = false;
  6.             IsActive = true;
  7.             if (e.Error == null)
  8.             {
  9.                 Tuple<IPiece, ISquare, double> move = e.Result as Tuple<IPiece, ISquare, double>;
  10.                 Board.ActivePiece = Board.IndexedSquares[move.Item1.Location.Coords].Occupant;
  11.                 (Board.ActivePiece as Piece).IsActive = true;
  12.                 MovePiece(Board.IndexedSquares[new Point(move.Item2.Row, move.Item2.Col)]);
  13.             }
  14.             else
  15.             {                
  16.                 throw e.Error;
  17.             }
  18.  
  19.             CurrentAIWorker = null;
  20.         }

Setting the game to Inactive tells the ViewModel not to pass around any user interaction into the actual game (making moves and such - since it's not the human player's turn). Setting IsBusy tells the View to display a BusyIndicator. Note that these will only really take any visible effect if we do our logic on a thread OTHER than the UI thread. Otherwise, the whole UI will freeze while our AI is thinking and we don't want that.