I've been playing Final Fantasy 8's Triple Triad and figured it's a simple enough game I could write a quick script to solve for the best move in any given position. I quickly realized a brute-force solution actually took too long given the surprising number of game states such a simple game could have, and did some research to find alpha-beta pruning as a way to effectively solve such a game efficiently.
For those not familiar with the game it's quite simple.
Setup:
- Start with a 3x3 grid
- You and your opponent are both dealt 5 cards, each card has a number on it's north south east and west
Rules:
- First player is determined randomly (for my code I let the AI always go first)
- Players take turns placing a cards in the 3x3 grid
- When placing a card adjacent to another card, compare the two facing values (ie: you place a card on the west side of a card, compare your east facing number to it's west one). If your card is higher you take control of that card
- Play until the entire grid is filled, the person with the most cards in their control wins the game (note since it's a 3x3 grid with 10 cards, 1 card is always controlled by the player that went second safely in his hand)
The algorithm described below seems to play coherently, but in my testing of trying to play against it, it's definitely not playing optimally, I'm trying to figure out why. This is my first attempt at an alpha-beta pruning algorithm so I may have made some false assumptions.
The code:
Game.cs: this is a class I made to model a game, and many of the functions I would run on it.
Notes:
- There's some oddities I wrote simply because I was serializing this object down to an angular app to play through the game visually to understand the algorithm, most of them stem from the fact that 2-d arrays in c# serialize strangely
- I hold both the 2-D array of cards and a 2-D array of bools to hold the state of the board, true meaning the alpha player is control of that square.
- I feel like LINQ just doesn't work for jagged arrays in c#, but they have to be declared that way because that's how json gets deserialized, I will accept any random tips here though as the number of old school for loops felt dated.
- I tried to add comments to help explain my thought process
--
public class Game
{
public Card[][] board { get; set; }
public bool?[][] boardOwnership { get; set; }
public Move LastMove { get; set; }
public Game()
{
//Ignore how ridiculous these declarations are, I was fighting with a serializer to send the whole game state to an angular app
//I wrote to visual the results
board = new Card[3][];
board[0] = new Card[3];
board[1] = new Card[3];
board[2] = new Card[3];
boardOwnership = new bool?[3][];
boardOwnership[0] = new bool?[3];
boardOwnership[1] = new bool?[3];
boardOwnership[2] = new bool?[3];
}
//Used as a short-cut in the recursion to realize we're at a terminal state
public bool isLastMove()
{
int retVal = 0;
for (int xPos = 0; xPos < 3; xPos++)
{
for (int yPos = 0; yPos < 3; yPos++)
{
if (board[xPos][yPos] != null)
{
retVal += 1;
}
}
}
return retVal >= 8;
}
public Move makeLastMove(Card card, bool isAlpha)
{
int lastX = -1;
int lastY = -1;
for (int xPos = 0; xPos < 3; xPos++)
{
for (int yPos = 0; yPos < 3; yPos++)
{
if (board[xPos][yPos] == null)
{
lastX = xPos;
lastY = yPos;
break;
}
}
}
return addCard(card, lastX, lastY, isAlpha);
}
//Simply checks if it's possible to play a card in a square
public bool canPlay(int x, int y)
{
return board[x][y] == null;
}
//While traversing the recursive tree it becomes necessary to make moves on a cloned board to ensure each branch has it's own reference
public Game clone()
{
Game clone = new Game();
clone.board = board.Select(s => s.ToArray()).ToArray();
clone.boardOwnership = boardOwnership.Select(s => s.ToArray()).ToArray();
return clone;
}
//A simple function to convert the A to '10', cards in Triple Triad go from 1-A, A being worth 10
public int getVal(char num)
{
if (num == 'A')
{
return 10;
}
return int.Parse(num.ToString());
}
//Adds the card and captures any cards possible. Returns a score equal to the number of alpha cards on the board
//(and the move that produced it).
public Move addCard(Card card, int x, int y, bool isAlpha)
{
board[x][y] = card;
boardOwnership[x][y] = isAlpha;
Card westCard = x > 0 ? board[x - 1][y] : null;
Card eastCard = x < 2 ? board[x + 1][y] : null;
Card southCard = y < 2 ? board[x][y + 1] : null;
Card northCard = y > 0 ? board[x][y - 1] : null;
if (eastCard != null && getVal(eastCard.W) < getVal(card.E))
{
boardOwnership[x + 1][y] = isAlpha;
}
if (westCard != null && getVal(westCard.E) < getVal(card.W))
{
boardOwnership[x - 1][y] = isAlpha;
}
if (southCard != null && getVal(southCard.N) < getVal(card.S))
{
boardOwnership[x][y + 1] = isAlpha;
}
if (northCard != null && getVal(northCard.S) < getVal(card.N))
{
boardOwnership[x][y - 1] = isAlpha;
}
int score = boardOwnership.SelectMany(o => o).Where(o => o.HasValue && o.Value).Count();
LastMove = new Move() { X = x, Y = y, Card = card, Score = score };
return LastMove;
}
}
Some other helper classes:
public class Card
{
public int Id { get; set; }
public String Name { get; set; }
public char N { get; set; }
public char S { get; set; }
public char E { get; set; }
public char W { get; set; }
}
public class Move
{
public int X { get; set; }
public int Y { get; set; }
public Card Card { get; set; }
public int Score { get; set; }
}
And lastly the solver class. More notes here:
- I followed a simple algorithm for alpha-beta pruning I found here.
- I struggled a bit to come up with a way to save what initial move got me to where I was calculating a score for. The code basically holds a stack of how it gets there and grabs the bottom of that stack when evaluating a final score, because ultimately we're evaluating the first move.
- I'm certain this can be optimized, however I am confused why it doesn't seem to actually play the best move. However, optimization thoughts are also accepted once I identify the bugs.
--
public class GameSolver
{
public static Move Solve(List<Card> alphaCards, List<Card> betaCards, Game g, bool isAlpha, Move alpha, Move beta)
{
return Solve(alphaCards, betaCards, g, isAlpha, alpha, beta, new Stack<Move>());
}
public static Move Solve(List<Card> alphaCards, List<Card> betaCards, Game g, bool isAlpha, Move alpha, Move beta, Stack<Move> moves)
{
if (g.isLastMove())
{
Card lastCard = isAlpha ? alphaCards[0] : betaCards[0];
Game cloneGame = g.clone();
Move m = cloneGame.makeLastMove(lastCard, isAlpha);
int value = m.Score;
//Grabs the bottom of the stack, effectively the first move that resulted in this score
Move firstMove = moves.ToArray().Last();
//the score of the terminal state that resulted
firstMove.Score = value;
return firstMove;
}
List<Card> currentPlayerHand = isAlpha ? alphaCards : betaCards;
if (isAlpha)
{
Move bestVal = new Move() { Score = int.MinValue };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (!g.canPlay(i, j))
{
continue;
}
for (int k = 0; k < currentPlayerHand.Count; k++)
{
//Clone the list as to not interfere with other trees references
List<Card> newHand = new List<Card>(currentPlayerHand);
Card playedCard = newHand[k];
newHand.RemoveAt(k);
//Clone the game to not interfere with other tree's reference to the game
Game cloneGame = g.clone();
cloneGame.addCard(playedCard, i, j, isAlpha);
Move move = new Move() { Card = playedCard, X = i, Y = j };
//Record the move as we go down the stack, so the terminal states know how we got here
moves.Push(move);
Move value = Solve(isAlpha ? newHand : alphaCards, isAlpha ? betaCards : newHand, cloneGame, !isAlpha, alpha, beta, moves);
//Pop off the stack as we come back up
moves.Pop();
//Based on my understanding of the algorithm, take the max between the value and bestVal, and the max between bestVal and alpha
bestVal = bestVal.Score > value.Score ? bestVal : value;
alpha = bestVal.Score > alpha.Score ? bestVal : alpha;
if (beta.Score <= alpha.Score)
{
goto breakAlpha;
}
}
}
}
breakAlpha:
return bestVal;
}
else
{
Move bestVal = new Move() { Score = int.MaxValue };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (!g.canPlay(i, j))
{
continue;
}
for (int k = 0; k < currentPlayerHand.Count; k++)
{
//Clone the list as to not interfere with other trees references
List<Card> newHand = new List<Card>(currentPlayerHand);
Card playedCard = newHand[k];
newHand.RemoveAt(k);
//Clone the game to not interfere with other tree's reference to the game
Game cloneGame = g.clone();
cloneGame.addCard(playedCard, i, j, isAlpha);
Move move = new Move() { Card = playedCard, X = i, Y = j };
//Record the move as we go down the stack, so the terminal states know how we got here
moves.Push(move);
Move value = Solve(isAlpha ? newHand : alphaCards, isAlpha ? betaCards : newHand, cloneGame, !isAlpha, alpha, beta, moves);
//Pop off the stack as we come back up
moves.Pop();
//Based on my understanding of the algorithm, take the min between the value and bestVal, and the min between bestVal and beta
bestVal = bestVal.Score < value.Score ? bestVal : value;
beta = bestVal.Score < beta.Score ? bestVal : beta;
if (beta.Score <= alpha.Score)
{
goto breakBeta;
}
}
}
}
breakBeta:
return bestVal;
}
}
}
Again there's no errors. I wrote a front end to play against the AI using this and it doesn't play bad, but it certainly doesn't play optimally. I would expect if this algorithm were working as expected I would have a very hard time beating such an AI unless my cards were very strong. Let me know if anyone requires more information on the code, I can provide it.
