Having problems in unMakeMove() for chess

[Ashish Schottky]

I have started to develop chess program AI.
I started with 0x88 representation and quiet successfully generated the moves for all pieces except for castles and enpassant moves, which are special moves in chess.
My move generator works correctly upto move 3 plys where there is no need to replace the capture pieces.
To replace the captured pieces, I have made to arrays called as pieces_from and pieces_to, the pieces are replaced according to the depths. the empty squares are nothing but 0.
and the following code.
Code
The concept is to replace the last piece first and so on , so depth is taken as index to access captured from the later squares.
But then I am missing something.
Can anyone show me a cleaner way to do it?
Thank you.

[Mich Robinson]

Normally you'd have a single dimension array for the board that contains a border around the playing area which allows you to detect moves off the board. It can be done via checking the xy coordinates are not <0 or >7 but this makes for more complicated programming. The following is for checkers with x's and o's for the pieces. Note the border around the board.

	char[] InitBoard = { 
		'+', '+', '+', '+', '+', '+', '+', '+', '+', '+', 
		'+', '+', 'x', '+', 'x', '+', 'x', '+', 'x', '+', 
		'+', 'x', '+', 'x', '+', 'x', '+', 'x', '+', '+', 
		'+', '+', 'x', '+', 'x', '+', 'x', '+', 'x', '+', 
		'+', '-', '+', '-', '+', '-', '+', '-', '+', '+', 
		'+', '+', '-', '+', '-', '+', '-', '+', '-', '+', 
		'+', 'o', '+', 'o', '+', 'o', '+', 'o', '+', '+', 
		'+', '+', 'o', '+', 'o', '+', 'o', '+', 'o', '+', 
		'+', 'o', '+', 'o', '+', 'o', '+', 'o', '+', '+', 
		'+', '+', '+', '+', '+', '+', '+', '+', '+', '+' };

There would then be direction arrays which allow you to step through the moves ie tried direction one now try direction two. Obviously castling and enpassant are special cases which require extra checks. The directions for checkers is quite simple but the principle is the same. You store which piece moved and, after trying a move, you remove that move and try the next direction. If there are no more directions then you look for the next piece to move.

	int[] Directions = { 9, 11, -9, -11 };

To store the moves in chess I think you could just have arrays for the following:

From

Direction

Distance

PawnChangedTo

CapturedPiece

If you start the game with Pk4 then you'd store 25 (the pawn's position in the Board array above) in the From array at position one for the first move. The direction it moved is stored in Direction (directions could include capture right, capture left, enpassant and move forwards), Distance would be either 1 or two for pawns. PawnChangedTo would hold the piece it changed to on the last row. CapturedPiece would hold whatever piece was taken. Once a move is done then you increment the array pointer.

I assume you know about minmax tree searching where you put on a move, swap sides, put on a move etc until you hit your maximum search depth. Then you score the position and step backwards through the tree. If you haven't done this sort of thing before then chess is probably quite a difficult game to start out on.

Not sure if that helped but ...

Perhaps you can be more explit with what problems you're having with the unmakemove?

[fred rosenberger]

Mich Robinson wrote:To store the moves in chess I think you could just have arrays for the following:

From

Direction

Distance

PawnChangedTo

CapturedPiece

not sure your "Direction" and "Distance" work for Knights or Castling...

[Ashish Schottky]

@Mich and Fred:
Thank you for replying.
At Mich: Chess and Checkers are quiet similar games but they differ a lot when it comes to move generation.
There are two types of pieces in chess the sliding and the non-sliding.
Sliding includes Queen,Bishop,Rook, Non sliding includes Knight and pawn and king.
I implemented 0x88 scheme of board in representation because its eays to search for boundaries.
I think your checkers program will definitley speedup move generation if you use 0x88 board, as it doesnot require any extra checks to see whether the square is on board or not.
The above were reasons why I chose 0x88.

I have solved the problem, it was just a goofup with from and to squares...
just was not my day.

I assume you know about minmax tree searching where you put on a move, swap sides, put on a move etc until you hit your maximum search depth. Then you score the position and step backwards through the tree. If you haven't done this sort of thing before then chess is probably quite a difficult game to start out on.

Yes I think so I know how the search algorithms work.
I implemented tict-tac-toe and connect-4 before, both of them played very nicely.
So now started to program chess, I know its a huge thing to even program a weak AI, forget about making it even decent, but then after say few years when my program would beat few humans and some newbie programs, I would feel like father who is proud of his child.In my case its just silicon child

Not sure if that helped but ...

Well everything posted here is very helpful, it might not be to the point but then atleast makes my head tick, gives ideas. So I thank you and fred one more time for replying to my post.

BTW did any one of you programed a chess AI before? What were the experiences?

[Mich Robinson]

fred rosenberger wrote:not sure your "Direction" and "Distance" work for Knights or Castling...

The distance would only apply to bishops, queens and rooks. While the direction for knights would just be a list of offsets that a knight can move to - assuming a border 2 deep surrounding the actual board making each row to be 8 + 2 + 2 = 12 places. This means the directions for a knight would just be would be { -10, -23,-25,-14,23,25,14 }. It's different for castling because there are lots of tests you need to apply but you'd just have store two special values in the king directions array to represent castling king side or queen side.

Ashish Schottky wrote:I implemented 0x88 scheme of board in representation because its eays to search for boundaries.
I think your checkers program will definitley speedup move generation if you use 0x88 board, as it doesnot require any extra checks to see whether the square is on board or not.
The above were reasons why I chose 0x88.

Could you give a quick description of how it works especially with border checks. If it offers a sizeable improvement then I'll add it to my games. Often though the difficulty is how to handicap your programs to allow a human to beat them rather than getting them to play stronger. I tend to favour better evaluation routines to deeper searches as judging a board position wrong at a depth of 2 is really no different to judging it wrong at a depth of 4.

Ashish Schottky wrote:I implemented tict-tac-toe and connect-4

Have you tried it against my little applet?

Ashish Schottky wrote:BTW did any one of you programed a chess AI before? What were the experiences?

I play chess reasonably well and have written lots of game playing programs so it would be a natural thing to do but there are so many free programs that play well that it kind of put me off. But I guess people are more impressed if you tell them you've written a chess program than almost anything else though I'd be more inclined to have a go at the game of Go first as the programs that play this currently are quite poor. I think writing the move generation part is more difficult than the board evaluation part - at least to get it to play to a reasonable level. You also need to look into restricting which moves you look at because there's a the number of moves to examine explodes as you search deeper - that might be a good reason to emphasise the exchanging "sliding pieces" first.

Perhaps you should split the effort into different areas and then farm the work out:

opening book

move generation

restricting the tree explosion

board evaluation

3D animation of the pieces

The 3D part is quite important as most chess games will crush human opponents but having one where the pieces actually kill each other (there was a spectrum game that did this in the 1980's) is far more interesting.

[Ashish Schottky]

@Mich:

0x88 is hexadecimal 88 (10001000) in binaray.

The board contains 128 memory locations and is divided into 2 parts.
1)Real Board
2)Dummy board
It loks like thisimage
The dummy board is on the right hand side and real on left.

Now comes the best and most interesting part.
Take any sq and AND it with 0x88 if the resulting value is 1, then its on the dummy board else if it is 0 then its on the board.

for example say the we check for the square 69 and whether its on board or not.

69 in binary is 1000101.
0x88 in binary is 10001000

01000101
AND 10001000
---------------------
000000000
so since ((0x88)&69)=0, 69 lies on the board.

Now lets check for 56.
56=111000
56 AND 0x88
00111000
AND 10001000
---------------------
000001000
so ((0x88)&56)!=0 so its outside the board.

[Mich Robinson]

It's (very) clever but I'm not sure whether it offers any advantages as you still need to check that the position on the board is free. So to check a piece can move a piece to square 69:

Your method: if ( to_pos & 0x88 == 0 and Board[to_pos] == EMPTY ) { // then can move there

Normal method with border: if ( Board[to_pos] == EMPTY ) { // then can move there

So I also don't see how it's faster. Obviously you still need to loop through all the directions for that piece and, in the case of sliding pieces, try the small distances before the long ones to make sure the path isn't blocked. This needs to be done for both methods though. Perhaps the biggest advantage of the normal method is that it's simple and simplicity is a virtue when approaching anything complex like a chess program.

[Ashish Schottky]

@Mich:
I agree to what you are saying, but then there was an explanation given why 0x88 is preffered over borderd array I dont remember exactly where I read it.
It was given that 0x88 representation is faster than non 0x88 representations because of advantages in microprocessor pipelining.
May be someone having more knowledege here might guide us. Since this is my first 8x8 game(Othello,chess,checkers), I think I am not i position to make any strong points further as i have less expericence in it.

In case if you have time then you can compare the two time differences and post it back so that other members can know.
As of my program of chess, I decided to restart it beause it was getting very messy , generated ordinary pseudo legal moves.
Heck never thought chess to be so difficult, I learnt it quickly.

[Mich Robinson]

Ashish Schottky wrote:@Mich:
I agree to what you are saying, but then there was an explanation given why 0x88 is preffered over borderd array I dont remember exactly where I read it.

A whole board position can be stored in a 32 bit number for checkers (or so I'm told) so it's much faster and more compact to hold end game databases in this fashion. Trying to write / debug this code though would give me a headache so I didn't bother.

Ashish Schottky wrote:In case if you have time then you can compare the two time differences and post it back so that other members can know.

perhaps ...

Ashish Schottky wrote:As of my program of chess, I decided to restart it beause it was getting very messy , generated ordinary pseudo legal moves.
Heck never thought chess to be so difficult, I learnt it quickly.

It's a great education writing these things - the hassle with chess is that it can be an uphill struggle before you even end up with a program that plays legal moves. In another recent post someone pointed out a chess program that was only 4k long, played quite well and only took the author 6 weeks to write. I'm usually pretty good at estimating time for projects and I'm a reasonable programmer but I was amazed this guy did it in 6 weeks. Good luck with it!

[Ashish Schottky]

Well finally I am able to generate legal moves for all the positions here on
What should be my next task then now or some more house keeping please describe?

[Mich Robinson]

You need an evaluation method. I'd stick with just material for the moment. Then have a look at min max and alpha beta trees. Then get the web interface working. Then provide us with a link so we can play. After that you can improve the evaluation routines and add scoring for development, space, pawn structures, open files, xray attacks etc.

[Ashish Schottky]

@Mich: Thanks for the reply.
I am trying to find a test suite which comprises of Check-Mates in 2 and 3 moves, but then I don't get it anywhere on internet, did you make something like that for your chess program?

My program, is still console based but now I have added the way to find check-mate, and it completes this in reasonable time, maximum of a 60 secs to find mate in 3 using mini-max and alpha-beta, I haven't yet chose to order the move, will do it later some time, till then I would like to check that it is capable of solving most complicated positions having mate in 3, so looking for some fen test position with the solution moves.

[Mich Robinson]

I haven't done chess but I've done many classic board games.

To find mate in 3 problems: just google for "chess mate in 3" and then pick from 1/2 billion pages. If it can solve a few then I can see why it couldn't solve any mate in 3. It would be straightforward to set up some more complicated tests yourself.

I'd suggest getting it to playing as an applet 1st. When you (or friends) can actually play the program it provides a big incentive to make it play better. The applet would need to allow entering of moves, check for valid moves, change level, undo moves, test for mate/stalemate. It would be a good idea to allow people (ie yourself) to enter positions so you can make testing easier.

60 secs to do a 3 ply search is quite a lot. How many different positions is it evaluating? You may need to work on this because a program that can only look 3 ply ahead is unlikely to play strongly and most people are unlikely to want to wait more than 5 seconds to move

Mike

[Ashish Schottky]

@Mich:

60 secs to do a 3 ply search is quite a lot. How many different positions is it evaluating? You may need to work on this because a program that can only look 3 ply ahead is unlikely to play strongly and most people are unlikely to want to wait more than 5 seconds to move

Actually i meant 3 moves=6 plys.

[Mich Robinson]

That's still not exactly a deep search (for a minutes thinking time) The problem you will face is that most human players look much deeper than this when playing and in much less time. This will be a problem for you if you want the program to play at least moderately well. Perhaps you could not stop the search if there are still exchanges to be made - this will allow the search to go a little deeper where needed.

Also keep in mind that the evaluation routine isn't overly complex yet so performance is likely to go down as you add more ideas to the evaluation side.