Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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..

share|improve this question
    
What exactly do you want to know? How to implement the A.I. for checkers (or Draughts/Dame/Dama)? –  bummzack Aug 18 '11 at 9:32
    
ya, Exactly.. I need to implement A.I for Dama.. How to start..? Can you please help me.. I have a experience in only physics base game.. Thanks.. –  Jagdish Aug 18 '11 at 9:38
    
Just searching the net for open source checkers gave me several results. Here's one in python and one in Java... shouldn't be too hard to get something working based on that? –  bummzack Aug 28 '11 at 21:39
    
Thanks tetrad.. I forgot the rule of it and post this as a answer.. Thanks.. –  Jagdish Aug 29 '11 at 4:49
add comment

3 Answers 3

up vote 13 down vote accepted

Oh I do love these games!

So first things first, in order for a computer to play a game, it needs:

  1. a structure to work with
  2. rules to play by
  3. 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 :/

share|improve this answer
2  
You put a lot of effort into that post which is admirable. However you're not answering the question about how to implement the A.I.. If you could elaborate a bit on that (or provide appropriate links) your answer would deserve some upvotes :) –  bummzack Aug 18 '11 at 12:41
    
Elaborate in what way? (I'd be more than happy too) Just want to make sure I'm on the same page. Implementing it into an MVC model, or ? in what context? Good with concepts, not so good with the words for them. –  Adrian Seeley Aug 18 '11 at 15:22
    
What I meant is something along the lines of what CiscoIPPhone posted... how to actually implement the A.I. so that it actually play against you :) –  bummzack Aug 18 '11 at 15:25
    
+1 for your effort. Yes. I would be very interested in having the actual AI logic as well especially from an implementation standpoint. –  Legend Aug 18 '11 at 18:17
    
Ahh, gotchya, I'll write that out now, the only way I've done it, is with an SQL database... so we'll see how this turns out... –  Adrian Seeley Aug 18 '11 at 21:13
show 4 more comments

At any point in the game the amount of possible moves for a player is quite low* (around 5) this means that thinking a few moves ahead, evaluating every possible move and selecting the best move is doable.

This approach is called minimax (wikipedia).

To implement minimax you'll need a evaluation function that returns a score for a given board layout and player. For draughts a naive implementation would be a function that returns one point for every piece the player has alive.

minimax decision tree

A visualisation of a minimax decision tree (from the wikipedia article). Down the left hand side is the turn number. The leaf nodes each have an evaluated score which is fed back up the tree to make a decision.

* however draughts is the game with the highest branching factor that has been completely solved.

share|improve this answer
1  
This is why I love the stack, you posted the theory needed, and I posted application with a big hole for any theory to be plopped in. <3 Stack –  Adrian Seeley Aug 18 '11 at 12:38
add comment

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

share|improve this answer
1  
Incomplete, but clear, useful and true. –  Anko Feb 23 '13 at 3:13
    
Thanks for your time, and good answer. –  Jagdish Feb 25 '13 at 17:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.