Jump to content
  • Advertisement
Sign in to follow this  
ashish123

Programing basic Chess AI

This topic is 2536 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement

[...]
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?

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 Perft to make sure your move generation functions work.

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.

In general, kindly provide some useful practical guidelines and links if possible.[/quote]
There is a lot of good information in the Chess Programming Wiki.

One thing that I strongly recommend is that you implement a standard protocol (I like UCI) 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
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
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
@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
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
@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.
2svi7mfy9kmcs.png
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
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:
enum CastlingFlags {
WhiteShort=1,
WhiteLong=2,
BlackShort=4,
BlackLong=8
};


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:
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);


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

Share this post


Link to post
Share on other sites
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!