[Kde-games-devel] Review Request 115535: Implement undoMove() for KJumpingCube

[Ian Wadham]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/115535/#review49236
-----------------------------------------------------------


It seems to me the main difference to the old code is in the manner and timing of the "save". The old code makes a working copy (not a save) of the current position, which doMove() can then dirty up as much as required. The working copy is appended to a list, which grows and involves allocation only on the first AI move of the first game (unless the user changes the board size). There is no de-allocation until the app terminates or the user changes the board size. "Undo" is implemented by switching pointers (C-style) back to the position that was copied.

The new code appears to rely on recursion and the stack to allocate/de-allocate "MoveUndodata undodata;" and "quint64 savedCubes[(maxSide * maxSide - 1) / 64 + 1];". I presume this is efficient and that the stack is unlikely to run out of space.

The "savedCubes[]" bitmap seems to be updated but never used. Does it have a use further down the track?

Timing differences would be between the old copyPosition(), which copies the whole board up front using a tight loop and single-indexed pre-allocated C-style arrays, and the new doMove(), which saves only the pieces that change as it goes along. It uses bit-packing which might slow it down, but it ought to be faster on save/undo cycles most of the time, especially early in the game when moves affect only 1-5 squares. Later in the game, when there are cascade moves sweeping across the board, saving the changed pieces might turn out to be slower.

There is a possible corner case that, in a cascade move near the end of a 15x15 game, some pieces could change more than once per move and MoveUndodata might overflow, but I do not think it is worth worrying about at this stage.



- Ian Wadham


On Feb. 7, 2014, 11:45 a.m., Inge Wallin wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/115535/
> -----------------------------------------------------------
> 
> (Updated Feb. 7, 2014, 11:45 a.m.)
> 
> 
> Review request for KDE Games and Ian Wadham.
> 
> 
> Repository: kjumpingcube
> 
> 
> Description
> -------
> 
> This patch implements undoMove() for the AI.
> 
> The primary reason is that the current model [save position - move - assess - restore position] fits very badly with the [move - assess - undo move] that is used in the upcoming kde games AI library that was discussed on the mailing list. So this is a preparatory patch to start using that library, something that Ian said he was interested in.
> 
> As a bonus, this patch also speeds up the AI somewhat. I don't know exactly how much but the previously used save/restore cycle of a position was not very efficient. Among other thing it called new/delete at least twice *per move* in the minimax algorithm.  As a side note, it would be interesting if Ian has a simple way of finding out how much more efficient it is, but even without it I'm fairly certain that the saving is significant.
> 
> Btw, the save/restore position thing is still used in the main game, this patch only touches the innards of the AI.  But I have an upcoming patch for that too. Stay tuned.
> 
> 
> Diffs
> -----
> 
>   ai_box.h 01ce182 
>   ai_box.cpp e481881 
>   ai_main.cpp 9cee435 
>   game.cpp c8a7cb8 
> 
> Diff: https://git.reviewboard.kde.org/r/115535/diff/
> 
> 
> Testing
> -------
> 
> Tested several full games. I also had a bug at one point which prompted me to do extensive logging and analysis of the logs.
> 
> 
> Thanks,
> 
> Inge Wallin
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-games-devel/attachments/20140208/f9e683bc/attachment.html>