This article demonstrates how you can build an AI which plays Backgammon. You can also compete against it online.
Table of Contents
This article demonstrates how you can build an AI which plays backgammon.
You can also compete against it online here.
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 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.
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.
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();
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))
{
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;
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);
}
}
}
}
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.
if (game.IsBearingOff(game.CurrentPlayer))
{
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;
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.
if (sequences.Any(moves => moves.Any(m => m != null)))
sequences = sequences.Where
(moves => moves.All(m => m != null)).Select(s => s).ToList();
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.
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).
var allPassed = true;
for (int i = 1; i < 25; i++)
{
var point = game.Points[i];
if (myColor == Player.Color.White)
point = game.Points[25 - i];
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.
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.
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.
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;
if (seqs.Any())
scores.Add(bestScore * m);
}
if (!scores.Any())
return -100000;
return scores.Average();
}
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.
- 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
