I saw this checkers game and I wondered how the A.I. was implemented.
How should I implement an A.I. for checkers (draughts, dama, dame)? Are there any known algorithms?
Very thnaks full to all. I m very wonder to see this Tic Tac Toe game tutorial blog post.
So, i want dama game algorithm open source code and blog post.. Is there any helpful link or any doc file..? please let me know..
Answer
Oh I do love these games!
So first things first, in order for a computer to play a game, it needs:
- a structure to work with
- rules to play by
- a win condition to work towards
Let's tackle this one piece at a time.
Structure
Since the board is an 8x8 grid (but could easily scale), and each grid space may exist in only one of five states, let's define those states:
[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]
Respectively ENUM'd to:
[0, 1, 2, 3, 4]
Now that we know what each space can be we need some way to represent all the spaces, or the board if you will. Almost every strong language will support a multi-dimensional array (an array where each element is an array holding data). So take the following slack-code for defining our array:
BOARD_ARRAY = array(8, 8)
This will give us an 8 x 8 array in which we can store integers (our enums from before):
(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)
Now you can already see how that this is beginning to look like a board! I've never played the variant mentioned in the youtube video but it appears to start with 2 rows of white pieces one row from the bottom, and 2 rows of black pieces one row from the top. Which would mean when we start a game our array should look like this:
(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)
(Remember 2 represents 'BLACK_PIECE' and 1 represents 'WHITE_PIECE')
So now the computer has a structure to work with. Step 1 complete!
Rules
Let's imagine you had an actual board set up in front of you, playing against a master player. If you tried to move one of his pieces, you'd get your hand slapped. If you tried to move a piece in a way you couldn't, you'd get your hand slapped. If you tried to cheat well... you get the idea. But the problem is, computers don't. So it's our job to provide strict rules to play within.
We need to create a way to check if any given move is 'legal'. Which means we first need some way to represent a 'move'. One way would be to use array positions; For example to move a piece from [0, 0] to [0, 1], we could create a function that will update the board given that move. So back to slack:
MY_MOVE = array( [0, 0], [0, 1] )
The above represents one piece, moving one space down from the top corner of the board (assuming 0, 0 is the top left corner). You may also notice I chose to use a multidimensional array for the move. This is because pieces may theoretically move a great number of times in one turn (for 'jumping' other pieces). So let's pretend at 0, 1 there was an opponents piece, meaning we would land at 0, 2:
MY_MOVE = array( [0, 0], [0, 2] )
Pretty simple eh. The program should understand that if we skip a space we are jumping another piece (or else it's an illegal move, and should throw an error). Now let's jump two pieces:
MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )
This gives us a way to describe any move on the board. Yay! Now since I don't fully understand the rules of the exact game in question (although I've played a bit of Canadian checkers in my day) the exact move legality will need to be defined by you. A good flow up to this point would look like:
FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn
The above assumes you can cycle through each piece to find all it's legal moves, then given a collection of all the legal moves somehow choose the best one (strategy here). The move is then applied to the board, or throws an error. Then the next player takes their turn. So we have an AI that knows how to play! Joy! Moving on.
Winning
Simple games are wonderful, because winning is defined by a very simple state. Ain't no white pieces on the board? Well I guess you've won! This is implemented in step 2 when we choose the best move to take us closer to the winning condition.
To make some very intelligent AI you could keep a database that stored every possible board as a state, with every possible move from every possible state, to find chains towards winning.
You could also create strategies, like: if there is a piece that WILL be jumped, save that piece or if a piece is able to jump more than one other piece do that jump.
That should give you a good jumping off point, it is only one method of literally unlimited possibilities. You could theoretically build a giant robot to draw with crayons then conduct spectral analysis on the drawing to choose moves... but it wouldn't work very good, or fast. This way has worked in the past, and worked well (: Hope that helps!
A Few Words On Implementation
Checkers is what is referred to as a 'solved' game, in that we can calculate every move with no unknowns. But that's a whole whack of moves! So there is no way to do it all manually... if only there was some... oh right we're programmers. fist pump
SQL is a wonderful tool for storing all these seemingly endless moves. For those with no experience with SQL, mySQL is a free (fairly easy to use) and open source SQL server. SQL is used for managing databases, sorta like a spreadsheet on steroids. It is also able to hold seriously large amounts of data and work with it very quickly.
So how can we use this? Since we know that if the board is in an exact state (each piece in a certain position) we can calculate all the available moves, and save them. For example:
+Board State+ +All Possible Moves+ +Best Move+
([0,0,1,2,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([7,6],[7,7])
([0,0,2,2,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([5,5],[5,4])
([0,0,1,3,3],[3..) ([0,1],[0,2]), ([7,6],[7,7],[5..) ([4,4],[4,3])
etc...
So when the computer needs to make a move it simply looks up the board state (stored as the primary key) in the database, and can either choose the best move (should be unbeatable) or one of the other moves to make a more friendly AI.
Great now let's build this database. First we need to calculate every board state. Which can be done with a great big nasty loop, if someone wants to spend some time and work it out that would be awesome. Look at the array as one big number, then count upwards, except in base 5 (0, 1, 2, 3, 4), and condition that each player may only have 16 pieces.
At this point we should have every board state stored and can go through calculating all possible moves.
Once all possible moves are calculated comes the fun part of pathfinding the best possible moves. This is where my knowledge begins to fall short, and things like Minimax or A* start to come into play. Sorry I can't be of more help on that :/
No comments:
Post a Comment