<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 />
<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>
<br />
<p>- Ian Wadham</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>