Programing basic Chess AI

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

Maybe have a look at wikipedia too.
http://en.wikipedia..../Computer_chess

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

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?

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.

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

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.

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

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.

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

@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 website, 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?

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

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


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;
}

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;
}
The value of nodes per second is dependent on the position.
For the starting position its like

Solving position number 1

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

if (depth == 0) {
return 1;
}
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.

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?

[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.[/font][font=arial, verdana, tahoma, sans-serif][size=2]
[/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.[/font]

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

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.

@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.
if (total_final_moves == killers[depth]) {
Move temp1;
temp1 = total_final_moves[0];
total_final_moves[0] = total_final_moves;
total_final_moves = temp1;
System.out.println("KILLER found");
}
}

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

Move coor = total_final_moves;
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;

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

alpha = eval; // alpha acts like max in MiniMax
}
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.

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

@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?