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.

Comments

Root Explorer for android download

Root Explorer is very trending nowadays since rooting is very necessary to enjoy any kinds of features for apps.Root Explorer Apk download

Normally every computer has

Normally every computer has an ip address 192.168.01 that is pretty useful to access internet from other devices.

Informative Blog

The part two for mvvm looks more interesting when compare to part one. In the blogs of essaytigers.com there are similar projects like this one. I would say you should also have a look on it for getting new ideas.

I have never thought about

I have never thought about the design details of the web games. It looks like you have done a wonderful job in setting up such an awesome board game for the users. I think there are not many companies showing the courage to share these details with the users. cheap ipad4 wholesale

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.
  • You can enable syntax highlighting of source code with the following tags: <asp>, <c>, <cpp>, <cs>, <css>, <drupal5>, <drupal6>, <html4strict>, <java>, <javascript>, <jquery>, <php>, <python>, <ruby>, <sql>, <xml>. The supported tag styles are: <foo>, [foo]. PHP source code can also be enclosed in <?php ... ?> or <% ... %>.

More information about formatting options

By submitting this form, you accept the Mollom privacy policy.