PhiAI 1.0.0-alpha

PhiAI

Implement AI for you games with PhiAI! Currently under development, PhiAI's v1 will feature the Monte Carlo Tree Search Algorithm.

Algorithms

Currently, PhiAI offers one algorithm, the Monte Carlo Tree Search algorithm.

Monte Carlo Tree Search (MCTS)

MCTS Overview

Monte Carlo Tree Search is an algorithm best suited for finite, two-person, zero-sum, perfect-information, sequential games. It is the algorithm between the highly successful and well-known AlphaGo and AlphaZero. It utilizes a game state tree. Each node in the tree represent a game state. The root node is the starting state. Edges between nodes represent an action, a transition from one state to the next. As an example, let's use a simple game we'll call Two-in-a-Row. Two-in-a-Row features 4 boxes that start off empty. Two players take turns marking an empty box with their color (black or white). Black goes first. The first player to mark adjacent boxes wins. If neither player has adjacent boxes, the game is a draw. While a simple and incredibly boring game, it makes a good example. Here is a visualization of the game state tree.

The Monte Carlo Tree Search Algorithm will automatically search this tree, exploring paths with potential and exploiting rewarding ones.

MCTS Usage

We will implement the Monte Carlo Tree Search Algorithm for Two-in-a-Row.

PhiAI exposes the MonteCarloTreeSearchAlgorithm class. Before instantiating, a domain must be defined. Our domain is Two-in-a-Row. We'll first create a representation of Two-in-a-row state by implementing the IState interface.

public class TwoInARowState: IState
{
    public string[] Boxes { get; set; } = { string.Empty, string.Empty, string.Empty, string.Empty };
    public string Agent { get; set; } = TwoInARowDomain.Black;
    public bool IsTerminal { get; set; } = false;

    public bool Equals(IState state)
    {
        TwoInARowState twoInARowState = (TwoInARowState) state;
        for (int box = 0; box < TwoInARowDomain.NumBoxes; box++)
        {
            if (Boxes[box] != twoInARowState.Boxes[box])
            {
                return false;
            }
        }

        return true;
    }
}

We've added four members to this class:

Next, we'll create a representation of a Two-in-a-Row action (transition between two state) by implementing IAction.

public class TwoInARowAction: IAction
{
    public int Box { get; set; }

    public TwoInARowAction(int box)
    {
        Box = box;
    }

    public bool Equals(IAction action)
    {
        return Box == ((TwoInARowAction) action).Box;
    }
}

A Two-in-a-row action is simple. It only requires an integer to represent which box is being marked. IState.Equals must also be implemented and should return true when two actions represent the same action (from the same state).

Finally, we finish the Two-in-a-Row domain by implementation IDomain<TState, TAction>.

public class TwoInARowDomain : IDomain<TwoInARowState, TwoInARowAction>
{
    public IEnumerable<TwoInARowAction> GetActionsFromState(TwoInARowState state)
    {
        var actions = new List<TwoInARowAction>();

        for (int box = 0; box < TwoInARowState.NumBoxes; box++)
        {
            if (state.Boxes[box] == string.Empty)
            {
                actions.Add(new TwoInARowAction(box));
            }
        }

        return actions;
    }

    public TwoInARowState GetStateFromStateAndAction(TwoInARowState state, TwoInARowAction action)
    {
        var newBoxes = new string[TwoInARowState.NumBoxes];
        for (int box = 0; box < TwoInARowState.NumBoxes; box++)
        {
            newBoxes[box] = state.Boxes[box];
        }

        newBoxes[action.Box] = state.Agent;

        var newState= new TwoInARowState()
        {
            Boxes = newBoxes,
            Agent = state.Agent == "black" ? "white" : "black",
        };

        return newState;
    }

    public bool IsStateTerminal(TwoInARowState state) => GetTerminalStateAndValue(state).Item1;

    public double GetTerminalStateValue(TwoInARowState state) => GetTerminalStateAndValue(state).Item2;

    private (bool, double) GetTerminalStateAndValue(TwoInARowState state)
    {
        bool draw = true;
        string previousPlayer = string.Empty;
        for (int box = 0; box < TwoInARowState.NumBoxes; box++)
        {
            string player = state.Boxes[box];
            if (player == string.Empty)
            {
                draw = false;
            }
            if (player == previousPlayer)
            {
                switch (player)
                {
                    case "black":
                        return (true, 1);
                    case "white":
                        return (true, -1);
                    default:
                        continue;
                }
            }
        }
        return (draw, 0);
    }

    public TwoInARowState GetInitialState() => new TwoInARowState();
}

We've implemented all 5 methods of IDomain and one helper function. Let's go over each one.

Now that we've created a domain for Two-in-a-Row, all we need to do is plug it into the Monte Carlo Tree Search Algorithm and we can use it however we want

// Instantiate the algorithm
var twoInARowMcts = new MonteCarloTreeSearchAlgorithm<TwoInARowDomain, TwoInARowState, TwoInARowAction>();

// Let the algorithm do some searching. More iterations means better results.
twoInARowMcts.SearchForIterations(1000);

// Get all the actions we can take from the current state. They are sorted by best move to worst.
List<TwoInARowAction> actions = twoInARowMcts.GetActions().ToList();
if (actions.Count() == 0)
{
    // game over (terminal state reached if there are no actions)
}

// actions are sorted by probability of resulting in a win for the current agent/player (black in this case)
var bestAction = actions[0];
var worstAction = actions[actions.Count()-1];

// Decided on an action? Let black take it and update current state
twoInARowMcts.TakeAction(bestAction);

// Monte Carlo Tree Search works for both agents. It's now white's turn, but we can still use the algorithm
twoInARowMcts.SearchForIterations(1000);
var bestActionForWhite = twoInARowMcts.GetActions().First();
twoInARowMcts.TakeAction(bestActionForWhite);

// Is a human playing?
int boxToPlayIn;
if (int.TryParse(Console.ReadLine(), out boxToPlayIn))
{
    var humanAction = new TwoInARowAction(boxToPlayIn);
    try
    {
        twoInARowMcts.TakeAction(humanAction);
    }
    catch (Exception e)
    {
        // action was not possible from current state
    }
}

// Need to get the current state?
TwoInARowState state = twoInARowMcts.CurrentState;

For more examples on implementing IDomain, IState, and IAction please see PhiAi/examples/

Versioning

See CHANGELOG.md