Stockfish do_move + undo_move

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

Stockfish do_move + undo_move

Post by mpurland » Wed Jun 02, 2010 9:51 pm

I'm using Stockfish 1.7.1 and having issues with the improvements in position.cpp with do_move/undo_move. I have written tests for testing move orders using do_move and reversing them with undo_move. This works for non-capture moves. However, if a move is a capture move it can't update pieceList correctly if I'm right.

inside do_capture_move:

Code: Select all

    // Update piece list, move the last piece at index[capsq] position
    //
    // WARNING: This is a not perfectly revresible operation. When we
    // will reinsert the captured piece in undo_move() we will put it
    // at the end of the list and not in its original place, it means
    // index[] and pieceList[] are not guaranteed to be invariant to a
    // do_move() + undo_move() sequence.
    Square lastPieceSquare = pieceList[them][capture][pieceCount[them][capture]];
    index[lastPieceSquare] = index[capsq];
    pieceList[them][capture][index[lastPieceSquare]] = lastPieceSquare;
    pieceList[them][capture][pieceCount[them][capture]] = SQ_NONE;
Performing the following moves using do_move, then detach (without st->previous = NULL). Then calling in reverse order the moves.

1. do_move using 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Bxc6 bxc6 5. Nc3 h5
2. detach safely without st->previous = NULL
3. undo_move in reverse order h5, Nc3, and bxc6. bxc6 is a capture move, but does not correctly work.

After h5

Code: Select all

+---+---+---+---+---+---+---+---+
|=R=|   |=B=|=Q=|=K=|=B=|=N=|=R=|
+---+---+---+---+---+---+---+---+
|   | . |=P=|=P=|   |=P=|=P=| . |
+---+---+---+---+---+---+---+---+
|=P=|   |=P=|   | . |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |=P=| . |   |=P=|
+---+---+---+---+---+---+---+---+
| . |   | . |   | P |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . | N | . |   | N |   | . |
+---+---+---+---+---+---+---+---+
| P | P | P | P | . | P | P | P |
+---+---+---+---+---+---+---+---+
| R | . | B | Q | K | . |   | R |
+---+---+---+---+---+---+---+---+
Fen is: r1bqkbnr/2pp1pp1/p1p5/4p2p/4P3/2N2N2/PPPP1PPP/R1BQK2R w KQkq -
Key is: 18341137315284503223
After undo_move h5

Code: Select all

+---+---+---+---+---+---+---+---+
|=R=|   |=B=|=Q=|=K=|=B=|=N=|=R=|
+---+---+---+---+---+---+---+---+
|   | . |=P=|=P=|   |=P=|=P=|=P=|
+---+---+---+---+---+---+---+---+
|=P=|   |=P=|   | . |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |=P=| . |   | . |
+---+---+---+---+---+---+---+---+
| . |   | . |   | P |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . | N | . |   | N |   | . |
+---+---+---+---+---+---+---+---+
| P | P | P | P | . | P | P | P |
+---+---+---+---+---+---+---+---+
| R | . | B | Q | K | . |   | R |
+---+---+---+---+---+---+---+---+
Fen is: r1bqkbnr/2pp1ppp/p1p5/4p3/4P3/2N2N2/PPPP1PPP/R1BQK2R b KQkq -
Key is: 18341137315284503223
After undo_move Nc3:

Code: Select all

+---+---+---+---+---+---+---+---+
|=R=|   |=B=|=Q=|=K=|=B=|=N=|=R=|
+---+---+---+---+---+---+---+---+
|   | . |=P=|=P=|   |=P=|=P=|=P=|
+---+---+---+---+---+---+---+---+
|=P=|   |=P=|   | . |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |=P=| . |   | . |
+---+---+---+---+---+---+---+---+
| . |   | . |   | P |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |   | N |   | . |
+---+---+---+---+---+---+---+---+
| P | P | P | P | . | P | P | P |
+---+---+---+---+---+---+---+---+
| R | N | B | Q | K | . |   | R |
+---+---+---+---+---+---+---+---+
Fen is: r1bqkbnr/2pp1ppp/p1p5/4p3/4P3/5N2/PPPP1PPP/RNBQK2R w KQkq -
Key is: 18341137315284503223
After undo_move bxc6 which is incorrect:

Code: Select all

+---+---+---+---+---+---+---+---+
|=R=|   |=B=|=Q=|=K=|=B=|=N=|=R=|
+---+---+---+---+---+---+---+---+
|   |=P=|=P=|=P=|   |=P=|=P=|=P=|
+---+---+---+---+---+---+---+---+
|=P=|   | . |   | . |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |=P=| . |   | . |
+---+---+---+---+---+---+---+---+
| . |   | . |   | P |   | . |   |
+---+---+---+---+---+---+---+---+
|   | . |   | . |   | N |   | . |
+---+---+---+---+---+---+---+---+
| P | P | P | P | . | P | P | P |
+---+---+---+---+---+---+---+---+
| R | N | B | Q | K | . |   | R |
+---+---+---+---+---+---+---+---+
Fen is: r1bqkbnr/1ppp1ppp/p7/4p3/4P3/5N2/PPPP1PPP/RNBQK2R b KQkq -
Key is: 18341137315284503223
Is there a way to fix do_capture_move or undo_move to fix this issue accordingly?

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish do_move + undo_move

Post by mcostalba » Thu Jun 03, 2010 11:48 am

mpurland wrote: 1. do_move using 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Bxc6 bxc6 5. Nc3 h5
2. detach safely without st->previous = NULL
3. undo_move in reverse order h5, Nc3, and bxc6. bxc6 is a capture move, but does not correctly work.
How did you undo the move ? There is not an UCI command to do this as far as I know.

Regarding detaching, I assume you have clear that doing so it means you discard all the previous state history so that after a detach you cannot go backward (for anything that could mean "go backward", that I have still to understand what you did in detail).

mpurland

Re: Stockfish do_move + undo_move

Post by mpurland » Thu Jun 03, 2010 6:45 pm

This is just a simple test to reproduce the errors I'm seeing with do_move + undo_move. It doesn't work with undoing the capture b7c6. This is using the latest Stockfish 1.7.1 release.

Code: Select all

	Position pos;
	pos.from_fen(StartPosition);
	StateInfo st;
	pos.print();
	
	NSArray *moveStrings = [NSArray arrayWithObjects: @"e4", @"e5", @"Nf3", @"Nc6", @"Bb5", @"a6", @"Bxc6", @"bxc6", @"Nc3", @"h5", nil];
	NSMutableArray *moves = [NSMutableArray array];
	
	for (NSString *moveString in moveStrings) {
		Move move = move_from_san(pos, [moveString UTF8String]);
		[moves addObject: [NSNumber numberWithLongLong: move]];
		pos.do_move(move, st);
		pos.print();
	}
	
	for (NSNumber *moveNumber in [moves reverseObjectEnumerator]) {
		Move move = (Move)[moveNumber longLongValue];
		pos.undo_move(move);
		pos.print();
	}
After using the code as a test the following assertion fails:

Assertion failed: (color_of_piece_on(to) == us), function undo_move, file position.cpp, line 1091.

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish do_move + undo_move

Post by mcostalba » Thu Jun 03, 2010 7:15 pm

mpurland wrote:

Code: Select all

	StateInfo st;
You cannot use the same StateInfo object for all the moves !

If you want to undo you need an array or, as done in search(), allocate on the stack one new StateInfo object at each search() call (define StateInfo object as a local variable).

In SF we use the form you suggested _only_ when we are not interested in take the moves back, for instance in line_to_san(), but there you don't see any undo_move() call.


IOW 'st' stores the position state after the move, but if you do another move and use the _same_ st variable you end up overwriting old information so that you are no more able to step back. Hope it is clear.

mpurland

Re: Stockfish do_move + undo_move

Post by mpurland » Fri Jun 04, 2010 2:37 pm

It looks like the issue was occurring because the Stockfish StateInfo does not behave exactly like UndoInfo. The StateInfo here needs to be correctly maintained in memory where UndoInfo could simply be allocated on the stack and let go out of scope.

The working fix I have implemented passes a reference to a correctly maintained StateInfo outside of the current scope when passing to do_move or undo_move. This allows the st->previous set in do_move or undo_move to set correctly. If you simply pass a local StateInfo then do_move copies it and stores the StateInfo on the stack as st->previous and will not behave as expected after it goes out of scope.

It seems to be working now. Thanks for your help.

Nils Magnusson

Re: Stockfish do_move + undo_move

Post by Nils Magnusson » Fri Jun 04, 2010 4:16 pm

Hi Matthew

Care to share your patch with the rest of us? Would be appreciated, even if it is in Objective C

Nils

Nils Magnusson

Re: Stockfish do_move + undo_move

Post by Nils Magnusson » Fri Jun 04, 2010 4:31 pm

Hi Matthew

See you wrote an app for iPhone, iPod touch, and iPad called Chess O that uses the GPL'ed Glaurung engine. Since it is impossible to link to a binary with iPhone apps it is therefor safe to assume that Chess O's source is also licensed under the GPL. I did a bit of googling, but was unable to find Chess O's source code anywhere. Could you please provide a link?

Nils

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Stockfish do_move + undo_move

Post by mcostalba » Fri Jun 04, 2010 4:55 pm

mpurland wrote: It seems to be working now. Thanks for your help.
It was working also before.

Matthew, here the only fix is to understand how StateInfo shall be used, nothing more.

BTW I know you probably didn't even considered this possibility, but there is a reason why it was changed from old UndoInfo to current StateInfo behaviour...it didn't occured by chance.

Sven
Posts: 3830
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Stockfish do_move + undo_move

Post by Sven » Fri Jun 04, 2010 5:03 pm

mpurland wrote:It looks like the issue was occurring because the Stockfish StateInfo does not behave exactly like UndoInfo. The StateInfo here needs to be correctly maintained in memory where UndoInfo could simply be allocated on the stack and let go out of scope.

The working fix I have implemented passes a reference to a correctly maintained StateInfo outside of the current scope when passing to do_move or undo_move. This allows the st->previous set in do_move or undo_move to set correctly. If you simply pass a local StateInfo then do_move copies it and stores the StateInfo on the stack as st->previous and will not behave as expected after it goes out of scope.

It seems to be working now. Thanks for your help.
In the code you posted you are not doing a recursive function call (where allocating something like StateInfo or UndoInfo on the stack would mean allocating one instance per recursion level, so N instances in total) but a loop - more correctly, two loops, one to make moves and one to unmake all of them in reverse order. Since the first unmake needs the StateInfo instance from the last make move operation, and so on, it is clear that with that loop structure you definitely need an array of StateInfo, as Marco has pointed out.

Sven

mpurland

Re: Stockfish do_move + undo_move

Post by mpurland » Fri Jun 04, 2010 5:28 pm

The fix was on my end. As I said in the previous post I wasn't handling the StateInfo properly. When using UndoInfo (before StateInfo) keeping in local scope was working fine.

Here's a test to illustrate the correct way to do it that I wrote for a test bench to reproduce the issues. Once I incorporated Marco's instructions for StateInfo it works now.

Code: Select all

@interface PositionTest : SenTestCase { 
   NSArray *moveStrings; 
   NSMutableArray *moves; 
} 

@end 

@implementation PositionTest 
- (void) makeMoves: (Position *) pos inc: (BOOL) inc st: (StateInfo *) st { 
   int i = 0; 

   for (NSString *moveString in moveStrings) { 
      StateInfo *moveSt = &st[i]; 

      Move move = move_from_san(*pos, [moveString UTF8String]); 
      if (inc) { 
         i++; 
         [moves addObject: [NSNumber numberWithLongLong: move]]; 
      } 
       
      NSLog(@"Move: %s", move_to_string(move).c_str()); 
      pos->do_move(move, *moveSt); 
    
      pos->print(); 
   } 
} 

- (void) undoMoves: (Position *) pos { 
   for (NSNumber *moveNumber in [moves reverseObjectEnumerator]) { 
      Move move = (Move)[moveNumber longLongValue]; 
      NSLog(@"Move: %s", move_to_string(move).c_str()); 
      pos->undo_move(move); 
      pos->print(); 
   } 
} 

- (void) testPositionMove { 
        Position pos; 
   pos.from_fen(StartPosition); 
   pos.print(); 
    
   moveStrings = [NSArray arrayWithObjects: @"e4", @"c5", @"Nf3", @"d6", @"d4", @"cxd4", /*@"Bxc6", @"bxc6", @"Nc3", @"h5",*/ nil]; 
   moves = [NSMutableArray array]; 
   StateInfo st[[moveStrings count]]; 
    
   [self makeMoves: &pos inc: YES st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
   [self undoMoves: &pos]; 
   [self makeMoves: &pos inc: NO st: &(st[0])]; 
} 
@end

Post Reply