Sign in to follow this  
ashish123

Programing basic Chess AI

Recommended Posts

ashish123    166
Hello every one out there.
I have programed Tic-Tac-Toe and Connect-4 before and do have idea of programing search algorithms like alpha-beta and nega-max.
I am a novice chess player and want to build a chess program which can play against people on internet on something like FICS or equivalent.

This is just a hobby project and nothing more than that.
Before I start to program, I would like to ask how should I go about it?

for example should I consider castlings and enpassants and promotion moves from start or add them later?
How many different classes should I make? and for what all purposes?

Few days back I came across a link on gamedev in which development of chess program was described, but now I dnt knw where it has vanished.
In general, kindly provide some useful practical guidelines and links if possible.
So that I start with proper steps.
Need not provide code, but the general idea.
-Thank you.
God Bless.

Share this post


Link to post
Share on other sites
alvaro    21246
[quote name='ashish123' timestamp='1306749883' post='4817447']
[...]
Before I start to program, I would like to ask how should I go about it?

for example should I consider castlings and enpassants and promotion moves from start or add them later?[/quote]
You should implement them early, if not in the very first version. It turns out not to be all that hard: In the board structure you need to have a little extra information (what castlings are available, what square contains a pawn that may be captured en passant (could be "none"), and how many moves have happened since a pawn move or a capture (to implement the 50-move rule). Additionally, you should be careful to restore this information in your "undo" function. You can use [url="http://chessprogramming.wikispaces.com/Perft"]Perft[/url] to make sure your move generation functions work.

[quote]How many different classes should I make? and for what all purposes?[/quote]
Just don't go crazy. Objects are not particularly well suited for this, and if you are not an experienced programmer you might be tempted to start defining classes for each type of piece, an abstract "Piece" class, and things like that. Don't: It won't really make your life easier in any meaningful way, and it will result in longer, less efficient code.

I normally just have a Board class and a Move class, with pretty obvious meanings. I sometimes use an "UndoInfo" class, or I make Board remember the history of the game, including whatever needs to be remembered to undo moves. I think I mildly prefer the latter.

[quote]In general, kindly provide some useful practical guidelines and links if possible.[/quote]
There is a lot of good information in the [url="http://chessprogramming.wikispaces.com/"]Chess Programming Wiki[/url].

One thing that I strongly recommend is that you implement a standard protocol (I like [url="http://chessprogramming.wikispaces.com/UCI"]UCI[/url]) early in the process, so you can use GUIs, automate testing against other programs, etc.

Share this post


Link to post
Share on other sites
m_waddams    274
Maybe have a look at wikipedia too.
[url="http://en.wikipedia.org/wiki/Computer_chess"]http://en.wikipedia..../Computer_chess[/url]

By the way, I'm such a lousy player, I would really appreciate a weak computer chess program :)

Share this post


Link to post
Share on other sites
ashish123    166
Thanks for reply.

Things I have done:
I have used starting chess position
Used a 0x88 board representation.
Generated pseudo-legal moves.
Programed a Perft generator.

My perft gives me correct values till 3-plys. Since on 4th ply black has to answer whites checks, I have question here.
Does perft numbers check the total number of pseudo-legal moves or legal moves?

BTW my recursion of perft at 3 plies is completed in 39 msecs, it it a good value?

Share this post


Link to post
Share on other sites
alvaro    21246
You need to figure out how to count only legal moves for Perft. Don't worry about performance until you are certain that you got the rules correctly implemented.

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro: Thank you for replying.

I am able to check whether the king is in check or not.
No the important part, at 5 plies, on can capture enpassant. But then I have actually no idea how to handle this. Basically the structure of my legal move generation goes this way:
1)Generate pseudo non captures and pseudo captures moves
2)Combine this together and then pass on to a function which filters the legal moves(i.e king of the moving side is not attacked).

No I have no idea how to and where to handle the special move of epassant, I think I can handle castling. just check the squares for castle and check if rook and king are on original squares without moving and king is not under attack or passing from attacked square.

But then I am not able to think how to handle enpassant as it can be played immidiately when possible.
kindly advise.
Thank you.

Share this post


Link to post
Share on other sites
alvaro    21246
For castling, you need to keep track of what castlings are still available: If a king moves, they both become unavailable, and if something moves to or from the corner, that particular castling becomes unavailable.

For en-passant captures, you keep a number that indicates what pawn can be captured. You only need to set this if a pawn moves two spaces and one of the horizontal neighbors of the destination square is occupied by an enemy pawn.

These pieces of information are part of the board description, and they need to be restored when you undo moves. One last thing you'll need to keep as part of the board description is the number of "reversible moves" that have happened (i.e., moves since the last time a pawn was moved or a capture happened), because the game is a draw if that ever gets to 100 (50 moves from each player). You also need to restore that number when you undo moves.

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro:
Thank you for replying.
With your suggestion, I have fixed up the enpassant captures and now my program plays all legal moves but castling is now the issue.
This is a very rare bug that occurs in my program.
I tried to debug but then didnot strike the appropriate.
[img]http://www.chessvideos.tv/bimg/2svi7mfy9kmcs.png[/img]
Consider the above position with white to move.
Program plays all legal moves uptill 3 plys.
At 4th ply it moves the black rook moves to h8 and now it thinks that the castling is possible. However this is not possible.
This is the bug.

I located the statements where I programed it to castle.
I make the changes in rights to castle in my MakeMove() function.
(If the king is not in place then no castling, if the rook is not on square, no castling on respective sides and so on)
but then logically I have to revert them back in my unMakemove() function.

How do I tell the program that the rook has now moved once and so its not possible to castle on that side.
I am missing something something that shouldn't be missed or is there any other way I can look at it?

With all other positions, it works correctly, no bugs, The only bug is when program castles where king and rooks are on the correct place but the castling is denied becaue of previous movemement of rooks.

kindly help,
Thank you.

Share this post


Link to post
Share on other sites
alvaro    21246
I think I described this already, but here it goes again.

You need to incorporate castling flags to your board position. For instance, I encode them like this:
[code]enum CastlingFlags {
WhiteShort=1,
WhiteLong=2,
BlackShort=4,
BlackLong=8
};
[/code]

The initial board gets a castling flags value of 15, which is (WhiteShort | WhiteLong | BlackShort | BlackLong). When you make a move, if the origin or the destination of the move is h1, you need to disable the WhiteShort bit, and so on:
[code] if (move.orig == sq_h1 || move.dest == sq_h1) castling_flags &= ~WhiteShort;
if (move.orig == sq_a1 || move.dest == sq_a1) castling_flags &= ~WhiteLong;
if (move.orig == sq_h8 || move.dest == sq_h8) castling_flags &= ~BlackShort;
if (move.orig == sq_a8 || move.dest == sq_a8) castling_flags &= ~BlackLong;
if (move.orig == sq_e1) castling_flags &= ~(WhiteShort|WhiteLong);
if (move.orig == sq_e8) castling_flags &= ~(BlackShort|BlackLong);
[/code]

You also have to save what the value of castling_flags was before the move, so you can restore it when you undo the move. The en-passant square and the number of reversible moves (towards the 50-move rule) also need to be treated similarly.

EDIT: Just to be clear, during move generation you check if the castling is still available.
[code] if (side_to_move == White && (castling_flags & WhiteShort) != 0 && !in_check
&& square[sq_f1]==Empty && square[sq_g1]==Empty
&& !attacked(sq_f1, Black) && !attacked(sq_g1, Black)) {
// White can castle short!
}[/code]

Share this post


Link to post
Share on other sites
ashish123    166
Hidden
Aha! I found out the bug.
I implemented the castling rights in terms of boolean variables.
From FEN I set up the position and then used switch case statement.
In switch , I used to integer literal instead of character, a typo but compiler didnt bother and hence didnt change the rights.
I made use of booleans. I think your program is based on bitboards whereas since this is my first program, I used simple but efficient 0x88 apprach.
BTW what should be my next step now?

Share this post


Link to post
ashish123    166
@Alvaro: I think I have fixed up the bug.
Now the point is it takes a long time to complete the test upto 6 plys.
The Perft suite from [url="http://hem.passagen.se/maragor/perftsuite.epd"]website[/url], contains about 126 positions in FEN and my program takes about 3 hours to evaluate most of the positions at 6th ply.
I tested a few of them, do you think that keeping my computer on for this purpose for days is of any worth?
Do you have some short listed positions which can help me track bugs, so the time required to run the suite is less than the original.

What should be my next step?

Share this post


Link to post
Share on other sites
alvaro    21246
How many positions per second does your Perft test go through? If the number is too low, you should see where the time is going. I expect a fast engine on modern hardware can go through several million positions per seconds. If you get something like a hundred thousand, you are probably still OK and shouldn't obsess about it. But if your speed is much lower than that, you are probably doing something wrong (copying tons of boards around, or allocating memory...).

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro: Thanks for the reply.
I donot copy the board any time.
this is my perft method.
I purposely kept captures and non captures separate as it will help me in quiscent search.

[code]
Move noCaps_moves[];
Move Caps_moves[];
Move total_moves[] = new Move[200];
Move[] total_final_moves;
public long Perft(int depth, boolean turn) {
long nodes = 0, nods = 0;
//


noCaps_moves = g.nonCaps(turn);
Caps_moves = g.Caps(turn);
//total_moves = new Move[200];


int l = 0;
for (int i = 0; i < noCaps_moves.length; i++) {
total_moves[l++] = noCaps_moves[i];
}

for (int j = 0; j < Caps_moves.length; j++) {
total_moves[l++] = Caps_moves[j];
}
total_final_moves = g.filterMoves(total_moves, turn);
// System.out.println(total_final_moves.length);
if (depth == 0) {
return 1;
}

for (int x = 0; x < total_final_moves.length; x++) {
if (total_final_moves[x] != null) {
nods = nodes;
g.makeMove(total_final_moves[x]);
// Algebraic(total_final_moves[x]);
// g.Print(boardArray);
nodes += divide(depth - 1, !turn);
// System.out.println("\tnodes : "+(nodes - nods));
g.unMakeMove(total_final_moves[x]);

}


}
return nodes;
}[/code]
The value of nodes per second is dependent on the position.
For the starting position its like

Solving position number 1
[img]http://www.chessvideos.tv/bimg/4iedi3uk6goww.png[/img]
Number of moves : 20 in 16 msecs at depth of 1
Number of moves : 400 in 51 msecs at depth of 2
Number of moves : 8902 in 847 msecs at depth of 3
Number of moves : 197281 in 18591 msecs at depth of 4
Number of moves : 4865609 in 465042 msecs at depth of 5

Share this post


Link to post
Share on other sites
alvaro    21246
[code] if (depth == 0) {
return 1;
}[/code]
Why is that code after all the move generation and filtering of valid moves? You can move it to the beginning of the function and you'll probably get a huge speedup.


Share this post


Link to post
Share on other sites
ashish123    166
I went through that, and placing that code before the move generation and filtering, made absolutely no difference to the timing whatsoever. Logically it should have done, but it doesnt.
I also think that the move-generation speed depends upon the board structure used.
I have used 0x88 system an array of 128 elements.
I get maximum of 10,000 nodes per second using my code.
Now what do you suggest me to do?

Share this post


Link to post
Share on other sites
alvaro    21246
[font=arial, verdana, tahoma, sans-serif][size=2]I suggest you learn how to use a profiler, which is a program that let's you explore where in your code is time being spent.[/size][/font][font=arial, verdana, tahoma, sans-serif][size=2]
[/size][/font][font=arial, verdana, tahoma, sans-serif][size=2]From your code, the only thing that I can see that might be slowing you down a lot is using variable-length arrays for moves. If you can somehow avoid all dynamic memory allocation, it might be a big win.[/size][/font]

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro: I agree with you, and the results too showed that avoiding dynamic memory allocation was a speed up.However I was caught by surprise, I restarted my laptop and then the things further speed up after restarting, I dont really know why.
I am getting around 2,00,000 nodes per second.
Is this around the expected value?
what should I do next now?
kindly help.
Thank you.

Share this post


Link to post
Share on other sites
alvaro    21246
If you are satisfied that your move generator is working and you have a recursive function to iterate through some fixed-depth tree, I think the next step is to put together a simple evaluation function and a simple minimax search function. The program will probably play horribly at this point. Implement quiescence search next, and then alpha-beta pruning. The list gets quite long: Iterative deepening, move ordering, hash tables, null-move pruning, extensions of certain moves, end-game databases, late-move reductions... And of course, you can always improve your evaluation function.

There are other forums that are much more appropriate for chess programming, like talkchess.com. You should also use the Chess Programming Wiki.

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro:Thanks for replying.
I have programed the basic chess, which can find checks. Did the search part with negamax+alphabeta pruning, works quiet well.
I have also noticed that my program is faster if I check for captures first(Sorted the captures), after a thought, I think this is because the material difference gives the cutoff.
I further want to improve the move ordering, so I tried for the Killer moves, but I am not finding any killer till depth of 6 here is a snippet of what I have done.
[code] if (total_final_moves[i] == killers[depth]) {
Move temp1;
temp1 = total_final_moves[0];
total_final_moves[0] = total_final_moves[i];
total_final_moves[i] = temp1;
System.out.println("KILLER found");
}
}

for (int i = 0; i < total_final_moves.length; i++) {

Move coor = total_final_moves[i];
g_e.makeMove(coor, board);
eval = -NegaMax_ab(board, !turn, depth - 1, -beta, -alpha);
g_e.unMakeMove(coor, board);
if (eval >= beta) {
killers[depth] = total_final_moves[i];

return beta; // beta-cutoff
}
if (eval > alpha) {
killers[depth] = total_final_moves[i];

alpha = eval; // alpha acts like max in MiniMax
}[/code]
Please let me know, Is my code correct for killer Moves?
Another question I am having is, Do I have to wait for some more plys to get a killer move?
Its surprising that even if I am getting a cut-off(beta), there is no killer move generated.

Thank you.

PS: Since this is not a total chess related question, I have posted it here.

Share this post


Link to post
Share on other sites
alvaro    21246
Your killer-move code seems correct, and I find it very surprising that you don't find any killer moves before depth 6. Perhaps there is a bug elsewhere...

Share this post


Link to post
Share on other sites
ashish123    166
@Alvaro: In my program, the captures are themselves the killers, so i am not getting any killers based on non-capture moves, is this a bug or is it correct?
I think its correct because material difference is most likely to get me a cutoff in most of the positions.
Does killer speeds the process by large amounts for chess?

Share this post


Link to post
Share on other sites
alvaro    21246
The killer heuristic is typically restricted to non-capture moves. There is a lot of information about this in the Chess Programming Wiki, so you should read it. Start [url="http://chessprogramming.wikispaces.com/Move+Ordering"]here[/url].

Share this post


Link to post
Share on other sites
jakubn    104
Take a look here:
[url="http://www.sluijten.com/winglet/#010"]http://www.sluijten.com/winglet/#010[/url]
Site which desciribes how to write own chess program from scratch in 99 steps.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this