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