Tough promotion bug(s)

[Sven]

I didn't understand anything

Nor I....

Join the club. If I try to explain it, it probably won't help I I'll be busy the next two hours talking about things no one understands.

What's easy to understand is this:
If you play pawn moves d3-d2 .. d2-d1 .. Qd1-a1 and later with another pawn e3xd2 and later d2-d1. You have two identical promotion moves (d2-d1)
played one stems from the d-pawn and the other from the e-pawn.

In your implementation a piece appears to be something like an immutable object. The white pawn that is on d2 in the initial position is always that particular pawn. Promoting a pawn to a queen means to take that pawn object from the board and to put a new queen object on the promotion square instead. Therefore for unmaking a promotion you need to remember that particular pawn somehow in order to restore it after removing the queen. As you see this can cause trouble.

But you could also think about a slightly different modelling of pieces, by making their piece type a property that can be changed. You would have two operations on a piece object for that purpose:

Code: Select all

void promote(PieceType promotionPieceType); // change piece type into given type
void unpromote(); // change piece type into "Pawn"

That could make your life a lot easier. At least it would avoid the need to store anything about promotions on a stack. Only the move data structure needs to include the type of the promotion piece, if any.

In many chess engines the representation of pieces and their types is even simpler.

Sven

[Henk]

My opinion is that storing prior state data in a played move is a bad idea and leads to bugs. Better is to store this data in a separate structure, stacking one new entry prior to move execution and restoring from that entry (unstacking it) on move retraction.

There are several reasons for this, one of them being that you don't want the structure of a move to be excessively complicated or large.

Problem with that is that you don't want overhead for every move because of the promotion move special case (treatment). I do not want to check for every move if it is a promotion move or not when making and unmaking moves.

There is always going to be a need for a save/restore of state data regardless of whatever the move might be. This includes the en passant target square and the halfmove counter at the very minimum.

If you are unclear as to why this is so, you should first examine some open source programs and see how they treat the problem before continuing with your coding.

Also, you should first get your program to do absolutely correct perft() operations on all the usual test positions before writing a single line of the search.

I do have state data called MoveMemeto with capture, enpassent, last move, castling rights etc,, which is used when calling move.TakeBack(memeto). But this memeto is created before the move loop so it doesn't contain information special to a promotion move if one of the next moves is a Promotion.

By the way I do call move.GetCapture() in the move loop and store the capture in the memeto.

[Henk]

Interesting idea. That would be a major change to my program.

[sje]

Do you have perft() working correctly? Accuracy first, speed later.

[Henk]

Do you have perft() working correctly? Accuracy first, speed later.

No maybe my en passant does not work for my latest changes were not that accurate. If not I have to do more basic testing. Maybe perft. perft only gives a count and how do I know if that count is ok. Perhaps I do not understand why perft is useful.

Sorry it's getting late now here in Europe.

[lucasart]

My opinion is that storing prior state data in a played move is a bad idea and leads to bugs. Better is to store this data in a separate structure, stacking one new entry prior to move execution and restoring from that entry (unstacking it) on move retraction.

There are several reasons for this, one of them being that you don't want the structure of a move to be excessively complicated or large.

Exactly:
* prior state is not a function of the move
* move structure has to be small, because it is best to keep one TT entries small (eg. my move_t is 2 bytes, and my TT entries are 16 bytes).

[JVMerlino]

Do you have perft() working correctly? Accuracy first, speed later.

No maybe my en passant does not work for my latest changes were not that accurate. If not I have to do more basic testing. Maybe perft. perft only gives a count and how do I know if that count is ok. Perhaps I do not understand why perft is useful.

Sorry it's getting late now here in Europe.

If your move generation and/or your functions to make and unmake a move are not perfect, then any number of very frustrating and strength-crippling bugs could occur.

Perft is indeed a way to simply verify that your engine gives the right number of moves for a specified starting position and tree depth. There are lots of excellent perft test positions that each take less than a minute to run, unless your engine is very slow.

Here's my list, many of which came from Ron Murawski and the Chess Programming Wiki. If your engine gets any of them wrong, then it is crucial to fix it before thinking of anything else. It's very easy to track down these issues using a form of perft called "divide", and then comparing the results to any other engine that also supports divide, such as my own Myrddin.

r3k2r/8/8/8/3pPp2/8/8/R3K1RR b KQkq e3 0 1
perft 6 = 485,647,607

r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1
perft 6 = 706,045,033

8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
perft 6 = 38,633,283

8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - - 1 67
perft 7 = 493,407,574

rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3
perft 6 = 244,063,299

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
perft 5 = 193,690,690

8/p7/8/1P6/K1k3p1/6P1/7P/8 w - -
perft 8 = 8,103,790

n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - -
perft 6 = 71,179,139

r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq -
perft 6 = 77,054,993

8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
perft 7 = 178,633,661

8/5p2/8/2k3P1/p3K3/8/1P6/8 b - -
perft 8 = 64,451,405

r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R w KQkq -
perft 5 = 29,179,893

jm

[Henk]

My opinion is that storing prior state data in a played move is a bad idea and leads to bugs. Better is to store this data in a separate structure, stacking one new entry prior to move execution and restoring from that entry (unstacking it) on move retraction.

There are several reasons for this, one of them being that you don't want the structure of a move to be excessively complicated or large.

Exactly:
* prior state is not a function of the move
* move structure has to be small, because it is best to keep one TT entries small (eg. my move_t is 2 bytes, and my TT entries are 16 bytes).

I store references (pointers) to moves in hash table so the size of the move doesn't matter anymore. A reference is probably 4 or 8 bytes so not that efficient.

[Henk]

I didn't understand anything

Nor I....

Join the club. If I try to explain it, it probably won't help I I'll be busy the next two hours talking about things no one understands.

What's easy to understand is this:
If you play pawn moves d3-d2 .. d2-d1 .. Qd1-a1 and later with another pawn e3xd2 and later d2-d1. You have two identical promotion moves (d2-d1)
played one stems from the d-pawn and the other from the e-pawn.

In your implementation a piece appears to be something like an immutable object. The white pawn that is on d2 in the initial position is always that particular pawn. Promoting a pawn to a queen means to take that pawn object from the board and to put a new queen object on the promotion square instead. Therefore for unmaking a promotion you need to remember that particular pawn somehow in order to restore it after removing the queen. As you see this can cause trouble.

But you could also think about a slightly different modelling of pieces, by making their piece type a property that can be changed. You would have two operations on a piece object for that purpose:

Code: Select all

void promote(PieceType promotionPieceType); // change piece type into given type
void unpromote(); // change piece type into "Pawn"

That could make your life a lot easier. At least it would avoid the need to store anything about promotions on a stack. Only the move data structure needs to include the type of the promotion piece, if any.

In many chess engines the representation of pieces and their types is even simpler.

Sven

Modeling type as a property is some form of the bridge design pattern. A disadvantage is that it is takes more time to access the PieceType (piece.PieceType instead of piece (where piece is PieceType))

[sje]

Do you have perft() working correctly? Accuracy first, speed later.

No maybe my en passant does not work for my latest changes were not that accurate. If not I have to do more basic testing. Maybe perft. perft only gives a count and how do I know if that count is ok. Perhaps I do not understand why perft is useful.

Sorry it's getting late now here in Europe.

If your move generation and/or your functions to make and unmake a move are not perfect, then any number of very frustrating and strength-crippling bugs could occur.

Perft is indeed a way to simply verify that your engine gives the right number of moves for a specified starting position and tree depth. There are lots of excellent perft test positions that each take less than a minute to run, unless your engine is very slow.

Here's my list, many of which came from Ron Murawski and the Chess Programming Wiki. If your engine gets any of them wrong, then it is crucial to fix it before thinking of anything else. It's very easy to track down these issues using a form of perft called "divide", and then comparing the results to any other engine that also supports divide, such as my own Myrddin.

r3k2r/8/8/8/3pPp2/8/8/R3K1RR b KQkq e3 0 1
perft 6 = 485,647,607

r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1
perft 6 = 706,045,033

8/7p/p5pb/4k3/P1pPn3/8/P5PP/1rB2RK1 b - d3 0 28
perft 6 = 38,633,283

8/3K4/2p5/p2b2r1/5k2/8/8/1q6 b - - 1 67
perft 7 = 493,407,574

rnbqkb1r/ppppp1pp/7n/4Pp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3
perft 6 = 244,063,299

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -
perft 5 = 193,690,690

8/p7/8/1P6/K1k3p1/6P1/7P/8 w - -
perft 8 = 8,103,790

n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - -
perft 6 = 71,179,139

r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq -
perft 6 = 77,054,993

8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
perft 7 = 178,633,661

8/5p2/8/2k3P1/p3K3/8/1P6/8 b - -
perft 8 = 64,451,405

r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R w KQkq -
perft 5 = 29,179,893

jm

Symbolic has verified that all of the perft() counts for the above positions are correct. Note: The last seven records are missing the half move counter and full move number fields; I had to supply a trailing " 0 1" for each of these to aid Symbolic's digestion.

For perft() results for the initial array, see: http://dl.dropboxusercontent.com/u/3163 ... alPosition

Before doing work on move ordering, a search, a transposition table, or any other more advanced topic, a program should first be able to get perft() running. It will be much easier for others to assist with questions. It is a waste of time to debug code which might never actually be used, and it won't be usable if the much more simple perft() is not working.

Also: Using a class representation for a simple scalar is usually not a good idea.