0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Try stepping through your code for a simple scenario — say placing the last card in a corner, to minimize the unknowns. Try to identify a step where your code takes a different path than the correct algorithm would predict when you work through it on paper. That will help you narrow down the bug and focus your question, so you get answers faster. \$\endgroup\$ – DMGregory Mar 10 at 13:33
  • \$\begingroup\$ It could also help to do some unit testing. Define a couple test cases, feed them into your methods and see if they come up with the expected moves. That way you can see if the rating function gives you the results you expect and/or if the pruning function prunes the branches you expect it to prune. \$\endgroup\$ – Philipp Mar 10 at 14:27
  • \$\begingroup\$ Yeah my testing involved making a whole front-end to visualize the moves the AI makes since it isn't necessarily obvious what the best move is, but I could probably contrive a board that is more obvious and see what it does. I'll keep trying to debug myself, but so far it looks like it's working, but it's hard to totally understand how it chose each move since the recursive tree is very deep, and I am still winning more often than not. \$\endgroup\$ – Kevin DiTraglia Mar 10 at 19:09
1
\$\begingroup\$

I figured out the issue, following another great article I found on the same site here. The link solves a tic-tac-toe game, and looks very similar to my code, except it pulled the first move out of the recursive tree, scored every first move, and pulled the highest. That seemed way more sane than what I was doing, and almost certainly was the cause of my bugs. Final game solver changed to this:

public class GameSolver
{
    public static Move BestMove(List<Card> alphaCards, List<Card> betaCards, Game g)
    {
        List<Move> possibleMoves = new List<Move>();
        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 < alphaCards.Count; k++)
                {
                    //Clone the list as to not interfere with other trees references
                    List<Card> newHand = new List<Card>(alphaCards);
                    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, true);

                    int value = Solve(newHand, betaCards, cloneGame, false, int.MinValue, int.MaxValue);
                    Move m = new Move() { X = i, Y = j, Card = playedCard, Score = value };

                    possibleMoves.Add(m);
                }
            }
        }

        return possibleMoves.Where(m => m.Score == possibleMoves.Max(m => m.Score)).First();
    }


    public static int Solve(List<Card> alphaCards, List<Card> betaCards, Game g, bool isAlpha, int alpha, int beta)
    {
        if (g.isLastMove())
        {
            Card lastCard = isAlpha ? alphaCards[0] : betaCards[0];

            Game cloneGame = g.clone();
            Move m = cloneGame.makeLastMove(lastCard, isAlpha);

            return m.Score;
        }

        List<Card> currentPlayerHand = isAlpha ? alphaCards : betaCards;

        if (isAlpha)
        {
            int bestVal = 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);

                        int value = Solve(isAlpha ? newHand : alphaCards, isAlpha ? betaCards : newHand, cloneGame, !isAlpha, alpha, beta);

                        bestVal = bestVal > value ? bestVal : value;
                        alpha = bestVal > alpha ? bestVal : alpha;
                        if (beta <= alpha)
                        {
                            goto breakAlpha;
                        }

                    }
                }
            }

            breakAlpha:
            return bestVal;
        }
        else
        {
            int bestVal = 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);

                        int value = Solve(isAlpha ? newHand : alphaCards, isAlpha ? betaCards : newHand, cloneGame, !isAlpha, alpha, beta);

                        bestVal = bestVal < value ? bestVal : value;
                        beta = bestVal < beta ? bestVal : beta;
                        if (beta <= alpha)
                        {
                            goto breakBeta;
                        }

                    }
                }
            }

            breakBeta:
            return bestVal;
        }
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.