Draughts

[tomcant]

I have written a draughts game where the user plays the computer. For the comps AI, I have developed an algorithm that runs through each of the of the comps pieces and gives each one a rating based on how good it's best move is. It kinda works well, but I want something better. I want the computer to play an intelligent game, ie. 2 or 3 moves ahead. I was thinking about brute forcing it by finding every move available to the comp for the next couple of turns, but that would be a bit hectic.

Does anyone have any better ideas?

[Alvaro]

Hey! I started a Spanish checkers program 13 years ago, and I have lots of experience, so I can help!

I will call the players white and black, although I'm not sure what colors are actually used in your game.

Start programming a minimax function. You need:
- An evaluation function (given a board, do some magic and come up with a number that is positive when white is winning and negative when black is winning).
- A move generating function.

Let's use ints for scores and ints for depths too for now (I have complicated explanations on why you may want to use doubles instead, but let's keep this basic).

We will adopt the convention that in our search function, positive scores mean "good for the side to move".

This is more or less what you need to do:
[syntax="cpp"]int minimax(Position const &P, int depth, bool wtm){ // wtm == "white to move"
if(depth<=0)
return wtm?static_evaluation(P):-static_evaluation(P);
Move m[256];
int n_moves = generate_moves(P,m,wtm);
int best_score=INT_MIN;
for(int i=0;i<n_moves;++i){
Position Child = make_move(P,m[i]);
int score = -minimax(Child, depth-1,!wtm);
if(best_score<score)
best_score=score;
}
return best_score;
}
[/syntax]

Now make a function that considers each move and calls minimax for each one of them, picking the best. The function is going to be similar to minimax, but I recommend that you keep it separate to keep this clean. This function should actually try a search of depht 1 first, then depth 2, etc. until it runs out of time.

Once you have done this, you can work on your evaluation function, you can improve the quality of the search by not stopping in positions where the side to move is about to capture something, etc. Then I'll teach you about alpha-beta, which will double the depth that your program can see in a given time.

Good luck, and post back with your progress!

EDIT: I forgot to pass m to generate_moves.

[Dante Shamest]

I'm very interested to see this Draughts game of yours tomcant. When you're done, do post the binaries and source.

[tomcant]

Excellent post, Alvaro! Thanks. I'll get back to you as soon as I'v implemented that much.

Dante: Currently, it's in C#. If you still want to see it, sure

[tomcant]

Ok, looking at the minimax function, I don't understand what the use of the Position object is. Could you explain?

[Alvaro]

Ok, looking at the minimax function, I don't understand what the use of the Position object is. Could you explain?

`Position' is a class that represents a position of the board. For instance:

Code: Select all

class Position{
  char t[32]; // Store the contents of each square.
  ...
};


... or...

Code: Select all

class Position{
  // We represent each square with one bit in a 32-bit integer. We describe the contents of a square with these 3 properties
  unsigned white_pieces;
  unsigned black_pieces;
  unsigned kings;
};


Then `make_move(Position const &p, Move const &m)' makes the move m on position p and then returns the resulting position.

Ooops! I made a mistake in the original post! The third argument `,!wtm' was for minimax, not make_move. I'll fix it right now.

[tomcant]

Ok, I must admit, I'm very confused by this. Am I just implementing this:

1. Compute all possible moves for the computer
2. From each of these moves, compute the human's possible moves
3. From each of these, compute again the computer's moves
4. Repeat steps 2 and 3 depending on the depth specified

Thanks for the help Alvaro!

[Alvaro]

Yes, that's basically what you are doing. But the tricky part is what to do with the scores.

At depth 0: We just call our static evaluation function.

At depth 1: We generate all possible moves. For each move, we evaluate the resulting board to depth 0. If it's white's turn, we would pick the maximum of the values, so that's the value that we return. If it's black's turn, we return the minimum of the values.

At depth 2: We generate all possible moves. For each move, we evaluate the resulting board to depth 1...

In order to simplify things a little, we always consider scores from the point of view of the player to move, that's why we reverse the sign after each call to minimax. OOOPS!! I forgot to put the `-' symbol before `minimax'. Fixed. And sorry again. Damn! I should only post working code.

[tomcant]

Ok, thanks Alvaro. I'll try implementing that first.

[tomcant]

Well, once again, I'm lost.

Would it be too much to ask for some more code? Maybe just some psuedo code or something. I'm all confused.

[Alvaro]

Let's do it the other way around. You post part of your code, so I know how you are describing the board and how you describe moves, etc. Also, please post a simple evaluation function (counting material and giving 100 points for each pawn and 140 points for each king is a good beginning).

[tomcant]

I have this structure which represents a single chip.
[syntax="cpp"]struct chip_info{int color, move, x_f, y_f, x_t, y_t;}[/syntax]
`x_f' and `y_f' are x-from and y-from. `x_t' and `y_t' are x-to and y-to. (x_t and y_t will only hold values if were moving that particular chip). `move' holds the score for each chip (don't know why I called it move). `color' will hold a value of 1 if its red (computer), a value of 0 if its black (human) and a value of 2 if its a blank square.

Then, I have the following array to represent each square on the 8x8 board.
[syntax="cpp"]chip_info board[8][8];[/syntax]
When the user clicks a square, x_f and y_f are given the x/y values of the chip they clicked on, then when the user selects another square, x_t and y_t are given values corresponding to the new square.

Heres what happens when the user has made a move, ie. heres the comps AI:
[syntax="cpp"]bool comp_turn() {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(board[i,j].color==1){
if(i<7&&j<7&&board[i+1,j+1].color==2)
board[i,j].move=0;//forward right
if(i<7&&j>0&&board[i+1,j-1].color==2)
board[i,j].move=1;//forward left
if(i<5&&j>0&&j<7&&board[i+2,j].color==0)
board[i,j].move=2;//to a taking position left/right
if(i<5&&j>2&&board[i+2,j-2].color==0)
board[i,j].move=3;//to a taking position left
if(i<5&&j<5&&board[i+2,j+2].color==0)
board[i,j].move=4;//to a taking position right
if(i<5&&j<6&&j>0&&board[i+1,j+1].color==2&&board[i,j+2].color==1&&board[i+3,j-1].color==2)
board[i,j].move=5;//logical-move to take right
if(i<5&&j<7&&j>1&&board[i+1,j-1].color==2&&board[i,j-2].color==1&&board[i+2,j].color==0&&board[i+3,j+1].color==2)
board[i,j].move=6;//logical-move to take left
if(i==6&&j>0&&board[i+1,j-1].color==2)
board[i,j].move=7;//to king left
if(i==6&&j<7&&board[i+1,j+1].color==2)
board[i,j].move=8;//to king right
if(i<6&&j<6&&board[i+1,j+1].color==0&&board[i+2,j+2].color==2)
board[i,j].move=9;//can take right
if(i<6&&j>1&&board[i+1,j-1].color==0&&board[i+2,j-2].color==2)
board[i,j].move=10;//can take left
}
}
}
hi_chip.move=0;
for(int k=0;k<8;k++){
for(int l=0;l<8;l++){
if(board[k,l].move>hi_chip.move){
hi_chip.move=board[k,l].move;
hi_chip.x_f=k;hi_chip.y_f=l;
}
}
}
switch(hi_chip.move){
case 0://forward right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f+1;
break;
case 1://forward right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f-1;
break;
case 2://to a taking position left/right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f+1;
break;
case 3://to a taking position left
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f-1;
break;
case 4://to a taking position right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f+1;
break;
case 5://logical-move to take right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f+1;
break;
case 6://logical-move to take left
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f-1;
break;
case 7://to king left
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f-1;
break;
case 8://to king right
hi_chip.x_t=hi_chip.x_f+1;
hi_chip.y_t=hi_chip.y_f+1;
break;
case 9://can take right
hi_chip.x_t=hi_chip.x_f+2;
hi_chip.y_t=hi_chip.y_f+2;
board[hi_chip.x_f+1,hi_chip.y_f+1].color=2;
break;
case 10://can take left
hi_chip.x_t=hi_chip.x_f+2;
hi_chip.y_t=hi_chip.y_f-2;
board[hi_chip.x_f+1,hi_chip.y_f-1].color=2;
break;
}
move_chip(ref hi_chip,3);
for(int m=0;m<8;m++)
for(int n=0;n<8;n++)
board[m,n].move=0;
return false;
}
}[/syntax]


[edit]: Hmm, that wasn't very well explained. But basically, the nested for loop gives each chip a score based on what it can do, then the next for loop finds the chip with the greatest score. Then I move that chip according to it's score.

[tomcant]

I found this link that explains minimax very nicely. And I'm pretty sure I understand the alpha-beta pruning thing now. Thanks for pushing me in the right direction Alvaro. I think I'v suddenly taken a liking to how AI is implemented.

[tomcant]

In my evaluation function, should I just count the number of pieces each side has, and then return positive if the computer has more and negative if the player has more... ?

Also, in your minimax() example above, why did you decide that 256 would be the greatest number of moves possible in a single turn? Surely it would be far less.

[Alvaro]

In my evaluation function, should I just count the number of pieces each side has, and then return positive if the computer has more and negative if the player has more... ?

Something like that. Start with a simple evaluation function that returns 100*(num_white_pawns-num_black_pawns)+140*(num_white_kings-num_black_kings). You can add other small terms for center control, mobility, passed pawns, keeping the pawns in the first row... You have to learn the game, play against a stronger opponent, understand why your program lost and often you will find a problem with your evaluation function. Rinse. Repeat.

Also, in your minimax() example above, why did you decide that 256 would be the greatest number of moves possible in a single turn? Surely it would be far less.

It's just an example. If you can prove that a smaller number will do, go ahead. You can also just have one big array of moves and use in each call only the portion that you need. This is a little harder to describe and that's why I didn't use it in my function; I was trying to make the code easy to read.