I just found a classic reference by Hans Berliner, who wrote one of the earliest backgammon bots, BKG.
The paper is called "BKG - A Program that Plays Backgammon", published in 1976 by Carnegie Mellon's Computer Science Department. It describes the approach he took to building his bot, which in a later version went on to beat a world champion human player in a 5-game match.
There's a version available online, but it's fairly truncated and doesn't give all the detail of the original article, which isn't as easy to find.
The original version is what some people refer to as "Berliner". For example, you see it referred to in the GnuBG codebase, and by other experts.
The bot described here is more primitive than neural network-based bots and to perform even at something like an intermediate level it needed a lot of hand-coded intelligence about backgammon strategy.
But that makes it pretty interesting from the perspective of adding new inputs.
For example: counting primes. In Berliner's article he notes that doing what I tried to do with Player 2.2 (just counting the maximum consecutive points) isn't a particularly effective tool in the game, because the position relative to the opponent's blots matters, and a fairly effective blockade can sometimes be made without consecutive points.
His approach: count ways that checkers can escape the blockade. He constructs a set of twelve points in front of a checker, and arranges up to seven covered points around them. For each layout he calculates the number of rolls (out of 36) that can escape.
For a given player checker on point n he defines a function Escape(n) that returns the number of escaping rolls. Then he defines an input (which he calls AContain) that is the minimum value of Escape for n running from the opponent's 1-point to 9-point.
That basically measures how hard it is for a player with checkers in or near the opponent's home board to escape a blockade.
He adds another input that measures the difficulty of running from the opponent's 9-point to the player's home - so he looks at the minimum value of Escape for n=opponent's 9-point to the player's 2-point. That lives in a separate input called Contain.
One complication: the calculation of number of escaping rolls when facing one of the board layouts is a somewhat complex calculation. So instead of redoing that calculation over and over, he builds something like a bearoff database that tracks the results. It's quite a small one: you can represent all board layouts with 12 bits. One for each point in front of a checker from 1->12 away; value is 0 if the point has less than two checkers covering it, and 1 if it has at least two checkers covering it. 2^12 is 4,096, but to represent up to seven covered points requires only 3,301 elements.
I'm going to try to implement this.
The paper is called "BKG - A Program that Plays Backgammon", published in 1976 by Carnegie Mellon's Computer Science Department. It describes the approach he took to building his bot, which in a later version went on to beat a world champion human player in a 5-game match.
There's a version available online, but it's fairly truncated and doesn't give all the detail of the original article, which isn't as easy to find.
The original version is what some people refer to as "Berliner". For example, you see it referred to in the GnuBG codebase, and by other experts.
The bot described here is more primitive than neural network-based bots and to perform even at something like an intermediate level it needed a lot of hand-coded intelligence about backgammon strategy.
But that makes it pretty interesting from the perspective of adding new inputs.
For example: counting primes. In Berliner's article he notes that doing what I tried to do with Player 2.2 (just counting the maximum consecutive points) isn't a particularly effective tool in the game, because the position relative to the opponent's blots matters, and a fairly effective blockade can sometimes be made without consecutive points.
His approach: count ways that checkers can escape the blockade. He constructs a set of twelve points in front of a checker, and arranges up to seven covered points around them. For each layout he calculates the number of rolls (out of 36) that can escape.
For a given player checker on point n he defines a function Escape(n) that returns the number of escaping rolls. Then he defines an input (which he calls AContain) that is the minimum value of Escape for n running from the opponent's 1-point to 9-point.
That basically measures how hard it is for a player with checkers in or near the opponent's home board to escape a blockade.
He adds another input that measures the difficulty of running from the opponent's 9-point to the player's home - so he looks at the minimum value of Escape for n=opponent's 9-point to the player's 2-point. That lives in a separate input called Contain.
One complication: the calculation of number of escaping rolls when facing one of the board layouts is a somewhat complex calculation. So instead of redoing that calculation over and over, he builds something like a bearoff database that tracks the results. It's quite a small one: you can represent all board layouts with 12 bits. One for each point in front of a checker from 1->12 away; value is 0 if the point has less than two checkers covering it, and 1 if it has at least two checkers covering it. 2^12 is 4,096, but to represent up to seven covered points requires only 3,301 elements.
I'm going to try to implement this.
No comments:
Post a Comment