Click here to Skip to main content
16,019,435 members
Articles / Artificial Intelligence / Machine Learning

Backgammon Artificial Intelligence

Rate me:
Please Sign up or sign in to vote.
5.00/5 (20 votes)
2 May 2022CPOL7 min read 46.4K   796   52   11
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. C# 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. 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.Any(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. Btw, points left are called pips in Backgammon lingo.

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 passed the blot it 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;

The end game

When the last checker of one player has passed the last checker of the other evaluation becomes much simpler.
The AI first tries to move all checkers inside the Home. And then move the checkers off the board.
No score is given for blocks or blots.

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
  • 25th April, 2022. Version 3.6
    • Improved endgame
    • Bugfixed move generation

License

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


Written By
Software Developer (Senior)
Sweden Sweden
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
Question"Feedback" does not send. Pin
Member 1632411531-Jul-24 19:12
Member 1632411531-Jul-24 19:12 
AnswerRe: "Feedback" does not send. Pin
KristianEkman31-Jul-24 22:13
KristianEkman31-Jul-24 22:13 
Questionorder of moves Pin
Member 1632411531-Jul-24 18:11
Member 1632411531-Jul-24 18:11 
AnswerRe: order of moves Pin
KristianEkman31-Jul-24 22:12
KristianEkman31-Jul-24 22:12 
QuestionTerminology and possible enhancements Pin
Greg Utas24-Jun-21 1:34
professionalGreg Utas24-Jun-21 1:34 
AnswerRe: Terminology and possible enhancements Pin
KristianEkman24-Jun-21 7:40
KristianEkman24-Jun-21 7:40 
GeneralProject Implementation Pin
Marvin Neves8-Jun-21 7:46
Marvin Neves8-Jun-21 7:46 
Good afternoon
My name is Marvin Neves, 2nd year student of the Computer Engineering and Computational Systems course, University of Mindelo (Cape Verde).
Motivated by a work in the Introduction Artificial Intelligence discipline, I am trying to implement your Backgammon Artificial Intelligence project for experiments.
But because I still don't have much knowledge in some areas of Artificial Intelligence, I'm having some difficulties in implementing the project.
I would like to know if you could help me in the implementation, specifically in the database part.
I'm really excited about this work because it triggered me more interest in this area.

Carefully,
Marvin Neves.
Thanks.
GeneralRe: Project Implementation Pin
KristianEkman8-Jun-21 7:59
KristianEkman8-Jun-21 7:59 
GeneralRe: Project Implementation Pin
Marvin Neves10-Jun-21 0:59
Marvin Neves10-Jun-21 0:59 
Questionchance has its virtues Pin
Emile van Gerwen7-May-21 1:52
Emile van Gerwen7-May-21 1:52 
AnswerRe: chance has its virtues Pin
KristianEkman8-May-21 4:35
KristianEkman8-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.