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

[Inge Wallin]

> On Feb. 8, 2014, 12:32 a.m., Ian Wadham wrote:
> > 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.
> > 
> >
> 
> Inge Wallin wrote:
>     Yes, this real point of this change is to move to an do-undo way of handling the board rather than save-do-restore.  Which is also what I wrote in the description. The reason is that it prepares for the use of the new AI library, not that it is a speedup in itself. It might be but that's not the point.
>     
>     savedCubes[] is only used inside doMove() and it is used because we should only save every changed cube during a move once.  See the "if (undodata && savedCubes[indexN...]...)" a bit down in doMove()
>     
>     Regarding overflow, that cannot happen. And the reason is because I use savedCubes to only save any cube once.  :)  
>     
>     But your comment is unclear to me.  I don't see any issue that I could fix and I don't see any rejection on principle. But I also don't see any "ship it".  So is this reply to your questions ehat you wanted?  I will be happy to fix any issue that you find, including style changes to the code, but this patch is a necessary step to use the AI library. If you don't want it, I can move on to test it on KReversi instead.
> 
> Ian Wadham wrote:
>     Your original statement "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" made me feel obliged to defend the previously existing code ... :-)
>     
>     Thank you for clarifying the use of savedCubes[] and the query about overflow. I am still a little concerned that saving changed cubes, and indeed the doMove() method itself, could cost time in the closing moves of the game, causing less look-ahead and missing a winning sequence. But that is a bridge yet to be crossed ...

Thanks for the ship it.  And regarding save/load I do still think it's faster.  But even if it is a little slower, it will be absolutely nothing compared to the gains that we will get when we implement alphabeta cutoffs.  It will move the search from O(n^2) to O(n). Typically the number of nodes searched using alphabeta is sqrt(x) where x is the number of nodes searched for a full minimax search, given the same search depth.


- Inge


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


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/1e260e2d/attachment.html>