Click here to Skip to main content
14,977,259 members
Articles / Artificial Intelligence / Machine Learning
Article
Posted 22 Apr 2021

Stats

10.8K views
373 downloads
35 bookmarked

Backgammon Artificial Intelligence

Rate me:
Please Sign up or sign in to vote.
5.00/5 (11 votes)
27 Jun 2021CPOL6 min read
How to build an AI which plays Backgammon
This article demonstrates how you can build an AI which plays Backgammon. You can also compete against it online.

Table of Contents

Introduction

This article demonstrates how you can build an AI which plays backgammon.
You can also compete against it online here.

Image 1

This is the second article I've posted on the subject Online Backgammon.
If you want to know more about the online application, read the first post here.
In this, I focus on the AI algorithms.

The AI in this first version is quite simple. To summarize, from a given board state, and a given dice roll, all possible move decisions are generated and a score is calculated from each choice.
The best score decides what the best move for the AI is.

But maybe, I should write a little bit more on the details or this article will be very short.

The Data Model

The selection of a data model is very important and the ground on which you build everything else.
Since this is my first backgammon application, I felt I had to go with C# and an object oriented model. It is the programming language I'm most fluent in.

A few years ago, I wrote chess engines in both C# and C, and when it comes to performance and calculation speed, you of course get a much more potent machinery choosing C. It simply runs faster by magnitudes.

These are the classes and the most important properties:

class Game
     Player Black
     Player White
     List<Point> Points
     List<Move> ValidMoves
        
class Point
     List<Check> Checkers
        
class Checker
     PlayerColor Color
        
enum PlayerColor 
     Black
     White

If you’ve ever played Backgammon, I think you know that there are two players. I call them Black and White. Each player has 15 checkers each. They are initially placed on the board Points. There are 24 points on the board.

There's also one Home for each player, which is Point 25, and the Bars which has the number 0. The points are numbered in reversed order for White. So Point 1 for White is Point 24 for Black and so on. That makes sense, since players move their checkers in opposite directions.

I made a mistake in this design though. The Home Point (25) for one player will also be the Bar(0) for the other. It would have been better not to include Home Points in the Points array, but it takes a big effort to change it now. If I ever implement the program in C for performance reasons, this is one of the things I learned and will change.

Move Generation

A move is just a Checker being placed on a new Point.
Since one roll of the dice generates several moves each turn, it's not only one move that needs to be evaluated but a sequence of moves.
So the move generation function generates a list of all possible moves sequences.

C#
public static List<Move[]> GenerateMovesSequence(Game game)
{
    var sequences = new List<Move[]>();
    var moves = new Move[game.Roll.Count];
    sequences.Add(moves);
    GenerateMovesSequence(sequences, moves, 0, game);
... and so on
    return sequences;
}

private static void GenerateMovesSequence(List<Move[]> sequences, 
        Move[] moves, int diceIndex, Game game)
{
    var current = game.CurrentPlayer;
    var bar = game.Bars[(int)current];
    var barHasCheckers = bar.Checkers.Any(c => c.Color == current);
    var dice = game.Roll[diceIndex];
    var points = barHasCheckers ? new[] { bar } :
        game.Points.Where(p => p.Checkers.Any(c => c.Color == current))
        .ToArray();

    // There seems to be a big advantage to evaluate points from lowest number.
    // If not reversing here, black will win 60 to 40 with same config.
    if (game.CurrentPlayer == Player.Color.White)
        Array.Reverse(points);

    foreach (var fromPoint in points)
    {
        var fromPointNo = fromPoint.GetNumber(game.CurrentPlayer);
        if (fromPointNo == 25)
            continue;
        var toPoint = game.Points.SingleOrDefault
        (p => p.GetNumber(game.CurrentPlayer) == dice.Value + fromPointNo);
        if (toPoint != null && toPoint.IsOpen(game.CurrentPlayer)
            && !toPoint.IsHome(game.CurrentPlayer)) // no creation of bearing off moves here.
                                                    // See next block.
        {
            var move = new Move 
            { Color = game.CurrentPlayer, From = fromPoint, To = toPoint };
            //copy and make a new list for first dice
            if (moves[diceIndex] == null)
                moves[diceIndex] = move;
            else // a move is already generated for this dice in this sequence. 
                 // branch off a new.
            {
                var newMoves = new Move[game.Roll.Count];
                Array.Copy(moves, newMoves, diceIndex);
                newMoves[diceIndex] = move;
                // For last checker identical sequences are omitted.
                if (diceIndex < game.Roll.Count - 1 || 
                    !sequences.ContainsEntryWithAll(newMoves))
                {
                    moves = newMoves;
                    sequences.Add(moves);
                }
            }
            if (diceIndex < game.Roll.Count - 1) // Do the created move 
                                                 // and recurse to next dice
            {
                var hit = game.MakeMove(move);
                GenerateMovesSequence(sequences, moves, diceIndex + 1, game);
                game.UndoMove(move, hit);
            }
        }
    }
}

Each roll of the two dice generates two or four moves. (When the dice show the same value, you use them twice.)
A Players Checkers can be in the Bearing off mode, that is when all Checkers have reached Point 19 or beyond and you are allowed to move them to the Home Point.

There are special rules for move generation in this state.

C#
if (game.IsBearingOff(game.CurrentPlayer))
{
    // The furthest away checker can be moved beyond home.
    var minPoint = game.Points.Where(p => p.Checkers.Any
                   (c => c.Color == game.CurrentPlayer)).OrderBy
                   (p => p.GetNumber(game.CurrentPlayer)).
                   First().GetNumber(game.CurrentPlayer);
    var toPointNo = fromPointNo == minPoint ? Math.Min(25, fromPointNo + dice.Value) : 
                    fromPointNo + dice.Value;
    toPoint = game.Points.SingleOrDefault(p => p.GetNumber(game.CurrentPlayer) == toPointNo);
    if (toPoint != null && toPoint.IsOpen(game.CurrentPlayer))
    {
        var move = new Move { Color = game.CurrentPlayer, From = fromPoint, To = toPoint };
        if (moves[diceIndex] == null)
            moves[diceIndex] = move;
        else
        {
            var newMoves = new Move[game.Roll.Count];
            Array.Copy(moves, newMoves, diceIndex);
            newMoves[diceIndex] = move;
            // For last checker identical sequences are omitted.
            if (diceIndex < game.Roll.Count - 1 || !sequences.ContainsEntryWithAll(newMoves))
            {
                moves = newMoves;
                sequences.Add(moves);
            }
        }
        if (diceIndex < game.Roll.Count - 1)
        {
            var hit = game.MakeMove(move);
            GenerateMovesSequence(sequences, moves, diceIndex + 1, game);
            game.UndoMove(move, hit);
        }
    }
}

In some board positions, making a move will prevent the other dice being moved but in Backgammon, all dice have to be used if possible. Move sequences with fewer moves are disregarded after move generation.

C#
if (sequences.Any(moves => moves.All(m => m != null)))
                  sequences = sequences.Where
                 (moves => moves.All(m => m != null)).Select(s => s).ToList();

Evaluation

Points

Obviously, move sequences are scored higher when the opponent has many points left and when the AI has fewer points left.

C#
private static double EvaluatePoints(Player.Color myColor, Game game)
{
    if (myColor == Player.Color.White)
        return game.BlackPlayer.PointsLeft - game.WhitePlayer.PointsLeft;
    else
        return game.WhitePlayer.PointsLeft - game.BlackPlayer.PointsLeft;
}

Connected Blocks (cb)

When there are two or more checkers on a Point, it is blocked and the opponent can't move there. It's a good idea to try to make blocks next to each other to prevent opponents from moving their checkers at all. The number of consecutive blocks times a constant (cb) gets an increase in score.

Blot Factor (bf) and Blot Factor Passed (bfp)

When you leave a single Checker on a Point (a blot), it can be hit by the opponent and will be moved to the Bar, starting all over. Leaving a blot will decrease score times a factor (bf) multiplied by the blots point number.

But if all opponents checker has bassed the blot i might not be as bad leaving a blot there. So another smaller factor (bfp) is used in stead.

Blots Threshold (bt)

Very often, there is no other option than to leave blots. It is better to leave blots with low point numbers, and it might not be an disadvantage to leave a blot at low Points. Because it is very likely that the opponent will have to leave a blot with a high point number hitting it. Blots below this threshold (bt) will not affect score negatively.

Run or Block (rb)

When you are behind in points, it is a good idea to leave some checkers early on the board and not move all your checkers past the opponents. (And when you have a big lead, you'd want to run for home). Then you will still have a chance to hit the opponent if she leaves blots. If all your checkers have passed the opponents, your score will be affected by the difference in points times a factor (rb).

C#
var allPassed = true;
for (int i = 1; i < 25; i++)
{
    var point = game.Points[i];
    // Found that it's important to reverse looping for white. 
    // These conditions affect score for some configurations greatly.
    // But I haven't figured out why.
    if (myColor == Player.Color.White)
        point = game.Points[25 - i];
    // If all opponents checkers have passed this block or blot, it is not interesting.
    if (point.GetNumber(myColor) > opponentMax)
        break;
    allPassed = false;
    if (point.MyBlock(myColor))
    {
        if (inBlock)
            counter++;
        else
            counter = 1;
        inBlock = true;
    }
    else
    {
        if (inBlock)
        {
            score += Math.Pow(counter * cbp, cb);
            counter = 0;
        }
        inBlock = false;
        if (point.Blot(myColor) && point.GetNumber(myColor) > bt)
           score -= point.GetNumber(myColor) / ( allPassed ? bfp : bf);
    }
}

if (inBlock)
    score += Math.Pow(counter, 2);

if (allPassed)
    score += EvaluatePoints(myColor, game) * rb;

Training

All these constants mentioned above are the engine's configuration.
It's not obvious what their values should be so it's the Trainers job to optimize them.
The Trainer plays two AI engines against each other 3000 times. If the AI being optimized wins more than 51% of the games, its configuration change is stored. And the training starts over.
So after several hours and about a million games played, the best configuration is found and the AI is finished.

Probability Score

The probability score calculates the average score for the current player rolling all possible combinations. So instead of selecting the move sequence with the highest evaluation, the AI makes a move and calculates the probability score for the opponent, selecting the move with the opponent's lowest average score. This is similar to Minimax algorithm at depth 1.

Since the layers of probability score adds a lot of computing time, it was not possible to train the AI with this function enabled, but I think that will be possible in coming C implementations.

But when comparing two engines with and without Probability Score enabled, they played at equal strength. I think the reason for that is that the training was done without Probability Score being enabled. So it is disabled for performance reasons.

C#
private double ProbabilityScore(Player.Color myColor, Game game)
{
    var allDiceRoll = AllRolls();
    var scores = new List<double>();
    var oponent = myColor == Player.Color.Black ? Player.Color.White : Player.Color.Black;
    foreach (var roll in allDiceRoll)
    {
        game.FakeRoll(roll.dice1, roll.dice2);
        var bestScore = double.MinValue;
        var seqs = GenerateMovesSequence(game);
        foreach (var s in seqs)
        {
            var hits = DoSequence(s, game);
            var score = EvaluatePoints(myColor, game) + EvaluateCheckers(myColor, game);
            score -= EvaluateCheckers(oponent, game);
            if (score > bestScore)
                bestScore = score;
            UndoSequence(s, hits, game);
        }
        int m = roll.dice1 == roll.dice2 ? 1 : 2; // dice roll with not same value 
                            // on dices are twice as probable. 2 / 36, vs 1 / 36
        if (seqs.Any())
            scores.Add(bestScore * m);
    }
    if (!scores.Any())
        return -100000; // If player can't move, she's blocked. That's bad.
    return scores.Average();
}

Change the Rules of Backgammon

It should be said that chance is a huge factor in Backgammon. The untrained AI with the configuration factors set to zero still manages to win 19.3% of the games against a trained AI.
Many times when I´ve played Backgammon Online, and being behind, I felt that if I only threw double fives or double sixes, I'd still have a chance to catch up. So I decided to investigate what happens if you disable the rule: If you throw doubles, you move four times. The result was that using these rules, an untrained AI vs a trained AI only wins 7% of the games. My conclusion is that if you change the rules, as described above, the outcome will depend much more on skill. And that perhaps will be a more fun game. Let me know what you think in the comments.

Links

History

  • 22nd April, 2021: Version 1.0
  • 5th May, 2021: Version 1.1
    • Added a second top list for last weeks games
  • 21st June: Version 3.1
    • Improved AI with Blots Factor Passed
  • 26th June: Version 3.1.1
    • Login feature using name and password

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

KristianEkman
Software Developer (Senior)
Sweden Sweden
No Biography provided

Comments and Discussions

 
QuestionTerminology and possible enhancements Pin
Greg Utas24-Jun-21 1:34
mvaGreg Utas24-Jun-21 1:34 
AnswerRe: Terminology and possible enhancements Pin
KristianEkman24-Jun-21 7:40
MemberKristianEkman24-Jun-21 7:40 
GeneralProject Implementation Pin
Marvin Neves8-Jun-21 7:46
MemberMarvin Neves8-Jun-21 7:46 
GeneralRe: Project Implementation Pin
KristianEkman8-Jun-21 7:59
MemberKristianEkman8-Jun-21 7:59 
GeneralRe: Project Implementation Pin
Marvin Neves10-Jun-21 0:59
MemberMarvin Neves10-Jun-21 0:59 
Questionchance has its virtues Pin
Emile van Gerwen7-May-21 1:52
MemberEmile van Gerwen7-May-21 1:52 
AnswerRe: chance has its virtues Pin
KristianEkman8-May-21 4:35
MemberKristianEkman8-May-21 4:35 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.