Tip:
Highlight text to annotate it
X
You will see us playing in summer with friends at home or even at the beach or at cafes,
in winter if we stay home to have more fun or even the elder people at coffeshops, playing
all day. You will see us playing anytime, and anywhere. You will see people getting
mad because they lose, but anytime in the friendly, warm and beautiful surrounding of
people we love to be with, with our favorite people… with people who love us.
You may have seen tournaments of this sport. To win the tournament people playing with
passion. People from all countries, contest each other. … But to be honest… behind
all this is having fun.
But… we are talking for time what? We are talking of course about maybe our, Greeks,
national game.
Backgammon!! Anyone has a backgammon board at home.
But before we continue, we would like to tell some things about it, for which even we, didn’t
know before.
According to Wikipedia “Backgammon is one of the oldest board games for two players.
The playing pieces are moved according to the roll of dice, and players win by removing
all of their pieces from the board. There are many variants of backgammon”
Despite the fact that luck is actively involved while playing, strategy plays an important
role for the sequence of the game. With each roll of the dice, players must choose from
a numerous options for moving their own checkers, and anticipate possible counter-moves by the
opponent. Each player has his own tactic, and that’s the reason for having excellent
backgammon players. Different characters, knowledge, ages, experience,
different game play!!
Backgammon, in the same way like chess, has been studied with great interests by computer
scientists. There is a huge research behind these games, which gives the ability to computers
to compete anyone, with a positive possibility of winning. Owing to this research, backgammon
software has been developed, capable of beating world-class human players.
According to Wikipedia “Artificial intelligence (AI) is the intelligence
of machines and the branch of computer science that aims to create it.
John McCarthy, who coined the term in 1956, defines it as "the science and engineering
of making intelligent machines.”
Nominated actor Keira Knightley who is famous as a protagonist in Pirates of the Caribbean
is a fun of the game
Backgammon is a really old game which we not knowing its real origin or its age. It is
found that a similar game existed in Iran at 3000BC. It is also played since the ancient
years in many countries and towns.
Backgammon is maybe…. Our national board game. It’s a very popular game among Greeks
in all countries including Cyprus. It is played by young and old people in coffee shops. While
playing the game, Greeks usually tease their opponent and a lively atmosphere is created.
It has the name “Tavli” which means board in Greek. The most common variations of “Tavli”
in Greece are: Portes, Plakoto and Fevga
These games are played one after another, usually in matches of three, five, or seven
points
The game is conducted in a board containing 24 points divided in four quandrants of 6
points each. Each pleyer starts the game with 15 checkers placed in fixed starting positions
like here. The players take turns playing their checkers, using an element of chence
in the form of two, wix sided dice, according to the game rules. When all the checkers of
a player are inside his last quandrand of the board, (called the home board) he can
start removing them. The player that remoces all his checkers first if the winner of the
game.
There are tactics, a player can follow in order to win.
These tactics include simple rules like avoiding to being hit or trapped, or more complex rules.
A tactic is also the placing the checkers in points, where there are more possibilities
at the next rolls, to come the desired numbers. Many times before to play a roll, the player
measures the owns position in the game. The minimum total of dice rolls needed to move
a player’s checkers around and off the board is called the “pip count”. The difference
between the two player’s pip counts is frequently used as a measure of the leader’s racing
advantage. Players often use some mental calculation techniques to determine pip counts in live
play.
AI in Backgammon
Backgammon software is created for many reasons, and is really impressive. First it can be
used to play with a person, or analyze games. It can also be used to facilitate play between
humans over the internet.
Backgammon has been studied in deep by computer scientists. They use techniques like neural
networks, and other approaches, and these approaches offer rich advances to software
for game analysis, and game play
BKG 9.8 was the first strong computer opponent. Hans Berliner wrote the code in the late 1970s
as an experiment in evaluating board game positions.
After many improvements BKG 9.8 was very strong in game play. It could play very well against
the king of Backgammon of that period, and world champion Luigi Villa. Not only he played
with the championship, but he also defeated him. More precisely it won the match with
score 7-1, and the program became the first computer program to defeat a world champion
in any board game. After the victory Berliner stated that the computers win was in a great
degree a matter of luck, as the program received better dice rolls than the championship.
A decade later, computer scientists who worked in this field used an approach based on artificial
neural networks, and found more success. Gerald Tesauro of IBM has developed TD-Gammon. TD-Gammon
was the first of these programs to play near the expert level and the level of the top
human players. The neural network of the application was trained using temporal difference learning
applied to data generated from self-play.
In the latest years the efforts of neural network research gave birth to five modern
programs. We are talking about Snowie, JellyFish and eXtreme Gammon, three proprietary programs,
the Shareware program BGBlitz, and the famous free software GNU Backgammon. Using these
programs you can have not only a great game, but you can also analyze your game, and take
a detailed comparison of individual move too! The above programs are very strong. Their
strength lays in their neural network’s weights table, and at the huge time of training.
The tables and their excellent training are the key to their success. For the bearoff
phase, the software usually uses a database which contains precomputed equities for all
possible bearoff positions.
We will now explain the basic ideas behind the algorithms these programs use.
Reinforcement Learning
A technique which is takes place in backgammon algorithms is reinforcement learning.
Algorithms learn a policy that maximizes the agent’s long term return from the performance
of a task
It explores through all the possible different situations. When it reaches the target (for
example a win) it takes a reward. The reward can be positive or negative. If
it’s negative the move was probably wrong, and the algorithm learns from his mistakes,
so the next time will be better. It’s analogous to the child’s behavior example. If he makes
something wrong, he gets some kind of punishment, like being in his room for two hours. If he
makes something good he takes a reward like a walk at the zoo.
Reinforcement learning is used in problems where it is not easy to teach an evaluation
function from examples for each situation. It is also used in problems where it is not
easy to find general good rules.
Here we see an example of reinforcement learning
Temporal Difference (TD) Learning is a prediction method. It has been mostly used for solving
the reinforcement learning problem. TD learning is a combination of Monte Carlo ideas and
dynamic programming ideas. TD resembles a Monte Carlo method because it learns by sampling
the environment according to some policy. TD is related to dynamic programming techniques
because it approximates its current estimate based on previously learned estimates.
Minimax Algorithm
Given a situation it tries to decide the next move against the opponent. It is not possible
to search the whole search tree. It is wanted the tree to be built until some height, and
to find the best move while being at the current situation... In order to find which situation
is better than other you have to use an evaluation function, whitch is applied at the leaves
of the tree. The first player is called max and the second
min.
Minimax Psevdocode
Apply the evaluation function to all the tree leaves and other vertices
While there is a node of the tree which has not a value repeat:
Starting from the leaves of the tree and towards the root of the tree, transfer the values
to the intermediate vertices as follows: The value of each node MAX is the maximum
value of the node’s children The value of each node Min is the minimum
value of the node’s children The best movement is the movement that leads
to the node that has the most advantageous price to the root. (The maximum for max, the
minimum for min)
Neural Networks
Artificial neural network is inspired by the structure of biological neutral networks and
is used in artificial intelligence. A neural network consists of an interconnected group
of artificial neurons. It has always an input layer of neurons, and produces an output at
the output layer of neurons. There are hidden level of neurons. A neuron at each level is
connected with every neuron at the previous level. Each neuron is a function which takes
as input the weighted sum of the outputs of the previous level. Each line has a weight.
These weights define how important is each result of a neuron as an input at each neuron
at the next level.
We have to train the network before we use it. By this we mean that we have a set of
training data (for example previous backgammon games), and their expected output. We pass
as an input these data at the neural network. Each time the network makes a mistake, we
say to the network that it has done a mistake. Then the network automatically adjusts all
the weights of the edges of the network. Because of that the network learns by itself, and
it continuously improves itself. It stimulates the way of human thinking and brain.
We stop training when the differences of weights are tiny, or when we believe that our algorithm
has pretty good results, or after some number of times we tried.
Modeling an instance in backgammon
Darwen’s experiment – Board representation
Representation: 122 inputs:
How many pieces are off the board? How many pieces are on the bar?
For each of the board’s 24 positions: One input to indicate if the position is occupied
by only one of the opponent’s pieces. For each of the board’s 24 positions:
Four inputs to counting one’s own pieces
Output: the sum of products of each input and its corresponding weight. (No sigmoid
function).
We should also mention in our presentation Palamedes. Palamedes (formerly known as TavliGUI)
is a computer program, and the Olympiad’s of Computer’s games champion in Backgammon
in 2011. It was created by researchers in University of Macedonia and it uses reinforcement
learning.
It is a freeware program that can play the Greek backgammon variants Plakoto, Portes
and Fevga. Its evaluation engine is based on artificial neural Networks that were trained
using reinforcement learning.
Here we can see a photo from the contest. Palamedes against BGBliz. The score was 2-0
Here we can see the creator of Palamedes winning the first place
It can also be used to analyze positions. The supervisor of the program associate professor
John Refanides said “The Palamides program has played millions of times against itself,
and each time he was improving his own performance, because of his artificial neural network.
This gives the ability to the system to utilize every possible move from each roll, predicts
the possible next rolls and the next possible opponent’s moves, while evaluating the possible
moves and chooses the best move each time, the move which will give the opportunity to
Palamedes to make a successful step to the win”
Olympiad takes place every year since 1989 and aims to the growth of research at the
field of Artificial Intelligence in games. Palamedes is the first Greek participation
at the International contest. So if you think you play very well backgammon,
you can play against Palamedes. I believe that each dislike at the bottom of this video
is because you have played with Palamedes and you maybe, maybe you didn’t like the
result. If you want to download it, it is available
for download at the page http://ai.uom.gr/nikpapa/software.html .
This presentation has shown the power of Artificial Intelligence and more specifically the fields
of Reinforcement Learning, and artificial neural networks. We showed that AI is capable
of producing high performance game playing programs in Backgammon.