<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 solid;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://git.reviewboard.kde.org/r/115535/">https://git.reviewboard.kde.org/r/115535/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<p style="margin-top: 0;">On February 8th, 2014, 12:32 a.m. UTC, <b>Ian Wadham</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.
</pre>
</blockquote>
</blockquote>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
<br />
<p>- Inge</p>
<br />
<p>On February 7th, 2014, 11:45 a.m. UTC, Inge Wallin wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" style="background-image: url('https://git.reviewboard.kde.org/static/rb/images/review_request_box_top_bg.ab6f3b1072c9.png'); background-position: left top; background-repeat: repeat-x; border: 1px black solid;">
<tr>
<td>
<div>Review request for KDE Games and Ian Wadham.</div>
<div>By Inge Wallin.</div>
<p style="color: grey;"><i>Updated Feb. 7, 2014, 11:45 a.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
kjumpingcube
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">Tested several full games. I also had a bug at one point which prompted me to do extensive logging and analysis of the logs.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>ai_box.h <span style="color: grey">(01ce182)</span></li>
<li>ai_box.cpp <span style="color: grey">(e481881)</span></li>
<li>ai_main.cpp <span style="color: grey">(9cee435)</span></li>
<li>game.cpp <span style="color: grey">(c8a7cb8)</span></li>
</ul>
<p><a href="https://git.reviewboard.kde.org/r/115535/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>