Tough promotion bug(s)

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sven
Posts: 3830
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Tough promotion bug(s)

Post by Sven » Tue Aug 20, 2013 8:13 pm

Henk wrote:
JVMerlino wrote:
elcabesa wrote: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
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Storing prior state data

Post by Henk » Tue Aug 20, 2013 8:16 pm

sje wrote:
Henk wrote:
sje wrote: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
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Tough promotion bug(s)

Post by Henk » Tue Aug 20, 2013 8:29 pm

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

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Storing prior state data

Post by sje » Tue Aug 20, 2013 9:59 pm

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

Henk
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Storing prior state data

Post by Henk » Tue Aug 20, 2013 10:36 pm

sje wrote: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.

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Storing prior state data

Post by lucasart » Tue Aug 20, 2013 11:11 pm

sje wrote: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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
JVMerlino
Posts: 1003
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Storing prior state data

Post by JVMerlino » Tue Aug 20, 2013 11:41 pm

Henk wrote:
sje wrote: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
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Storing prior state data

Post by Henk » Wed Aug 21, 2013 10:29 am

lucasart wrote:
sje wrote: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
Posts: 5833
Joined: Mon May 27, 2013 8:31 am

Re: Tough promotion bug(s)

Post by Henk » Wed Aug 21, 2013 10:38 am

Sven Schüle wrote:
Henk wrote:
JVMerlino wrote:
elcabesa wrote: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))

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Prioritization

Post by sje » Wed Aug 21, 2013 2:08 pm

JVMerlino wrote:
Henk wrote:
sje wrote: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.

Post Reply