group__hash.html

黑白棋终局解算程序

<p>
Initialise the hashtable. 
<p>
Allocate the hash table entries and initialise the hash masks and codes. <dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign=top><em>hash_table</em>&nbsp;</td><td>hash table to setup. </td></tr>
    <tr><td valign=top><em>n_bits</em>&nbsp;</td><td>requested size for the hash table in number of bits. </td></tr>
  </table>
</dl>

<p>
<div class="fragment"><pre>00618 {
00619     <span class="keywordtype">int</span> i,j;
00620     <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> hash_mask[2], size = 1u &lt;&lt; n_bits;
00621 
00622     <span class="keywordflow">if</span> (hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a> != NULL) free(hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a>);
00623     hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a> = malloc(size * <span class="keyword">sizeof</span> (<a class="code" href="structHashEntry.html">HashEntry</a>));
00624     <span class="keywordflow">if</span> (hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a> == NULL) {
00625         fprintf(stderr, <span class="stringliteral">"hash_init: cannot allocate the hash table\n"</span>);
00626         exit(EXIT_FAILURE);
00627     }
00628     hash_mask[0] = hash_table-&gt;<a class="code" href="structHashTable.html#o1">hash_mask</a> = size - 1;
00629     hash_mask[1] = 0xffffffff;
00630 
00631     <span class="keywordflow">for</span> (j = 0; j &lt; 2; j++) {
00632         hash_code_swap_player[j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() &amp; hash_mask[j]);
00633         <span class="keywordflow">for</span> (i = 0; i &lt; <a class="code" href="group__mac.html#ga22">BOARD_SIZE</a>; i++) {
00634             hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() &amp; hash_mask[j]);
00635             hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() &amp; hash_mask[j]);
00636             hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a132">EMPTY</a>][j] = 0;
00637             hash_code_flip_disc[i][j] = hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] ^
00638                 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j];
00639             hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] ^= hash_code_swap_player[j];
00640             hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j] ^= hash_code_swap_player[j];
00641         }
00642     }
00643 }
</pre></div>    </td>
  </tr>
</table>
<a class="anchor" name="ga0" doxytag="solver.c::hash_random" ></a><p>
<table class="mdTable" width="100%" cellpadding="2" cellspacing="0">
  <tr>
    <td class="mdRow">
      <table cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td class="md" nowrap valign="top"> unsigned long hash_random </td>
          <td class="md" valign="top">(&nbsp;</td>
          <td class="md" nowrap valign="top">void&nbsp;</td>
          <td class="mdname1" valign="top" nowrap>          </td>
          <td class="md" valign="top">&nbsp;)&nbsp;</td>
          <td class="md" nowrap></td>
        </tr>

      </table>
    </td>
  </tr>
</table>
<table cellspacing=5 cellpadding=0 border=0>
  <tr>
    <td>
      &nbsp;
    </td>
    <td>

<p>
Pseudo-random number generator. 
<p>
A good random generator (similar to rand48 or Java's one) to set the hash codes. <dl compact><dt><b>Returns:</b></dt><dd>a 32 bits random unsigned long integer. </dd></dl>

<p>
<div class="fragment"><pre>00591 {
00592     <span class="keyword">static</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> x[3] = {0xe66du, 0xdeecu, 0x5u};
00593     <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> MASK = 0x0000ffffu;
00594     <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> A[3] = {0xe66du, 0xdeecu, 0x5u};
00595     <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> B = 0xBu;
00596     <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> product[3];
00597 
00598     product[0] = A[0] * x[0] + B;
00599     product[1] = A[1] * x[0] + (product[0] &gt;&gt; 16);
00600     product[2] = A[1] * x[1] + A[0] * x[2] + A[2] * x[0] + (product[1] &gt;&gt; 16);
00601     product[1] = A[0] * x[1] + (product[1] &amp; MASK);
00602     product[2] += (product[1] &gt;&gt; 16);
00603     x[0] = (product[0] &amp; MASK);
00604     x[1] = (product[1] &amp; MASK);
00605     x[2] = (product[2] &amp; MASK);
00606 
00607     <span class="keywordflow">return</span> x[1] + (x[2] &lt;&lt; 16);
00608 }
</pre></div>    </td>
  </tr>
</table>
<a class="anchor" name="ga4" doxytag="solver.c::hash_update" ></a><p>
<table class="mdTable" width="100%" cellpadding="2" cellspacing="0">
  <tr>
    <td class="mdRow">
      <table cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td class="md" nowrap valign="top"> void hash_update </td>
          <td class="md" valign="top">(&nbsp;</td>
          <td class="md" nowrap valign="top"><a class="el" href="structHashTable.html">HashTable</a> *&nbsp;</td>
          <td class="mdname" nowrap> <em>hash_table</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap>const <a class="el" href="structBoard.html">Board</a> *&nbsp;</td>
          <td class="mdname" nowrap> <em>board</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap>int&nbsp;</td>
          <td class="mdname" nowrap> <em>alpha</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap>int&nbsp;</td>
          <td class="mdname" nowrap> <em>beta</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap>int&nbsp;</td>
          <td class="mdname" nowrap> <em>score</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap>int&nbsp;</td>
          <td class="mdname" nowrap> <em>move</em></td>
        </tr>
        <tr>
          <td></td>
          <td class="md">)&nbsp;</td>
          <td class="md" colspan="2"></td>
        </tr>

      </table>
    </td>
  </tr>
</table>
<table cellspacing=5 cellpadding=0 border=0>
  <tr>
    <td>
      &nbsp;
    </td>
    <td>

<p>
Update an hashtable entry. 
<p>
Find an hash table entry according to the evaluated board hash codes. Then update the entry if it already exists otherwise create a new one. Collisions are managed in such a way that better existing entries are always preserved and the new evaluated data is always added. Lower and upper score bounds are then updated/set from the alpha, beta and score values according to the following alphabeta property (where alpha &lt; beta): -if (score &gt;= beta) score is a lower bound of the real score -if (score &lt;= alpha) score is an upper bound of the real score -if (alpha &lt; score &amp;&amp; score &lt; beta) score equals the real score So: -if (score &lt; beta) update the upper bound of the hash entry -if (score &gt; alpha) update the lower bound of the hash entry The best move is also stored. <dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign=top><em>hash_table</em>&nbsp;</td><td>hash table to update. </td></tr>
    <tr><td valign=top><em>board</em>&nbsp;</td><td>evaluated board. </td></tr>
    <tr><td valign=top><em>alpha</em>&nbsp;</td><td>alpha bound when calling the alphabeta function. </td></tr>
    <tr><td valign=top><em>beta</em>&nbsp;</td><td>beta bound when calling the alphabeta function. </td></tr>
    <tr><td valign=top><em>score</em>&nbsp;</td><td>best score found. </td></tr>
    <tr><td valign=top><em>move</em>&nbsp;</td><td>best move found. </td></tr>
  </table>
</dl>

<p>
<div class="fragment"><pre>00701 {
00702     <a class="code" href="structHashEntry.html">HashEntry</a> *hash_entry;
00703     <a class="code" href="structHash.html">Hash</a> *deepest, *newest;
00704 
00705     <span class="keywordflow">if</span> (!<a class="code" href="group__mac.html#ga51">HASH_TABLE_OK</a>(hash_table)) <span class="keywordflow">return</span>;
00706 
00707     hash_entry = hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a> + board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[0];
00708     deepest = &amp;(hash_entry-&gt;<a class="code" href="structHashEntry.html#o0">deepest</a>);
00709     newest = &amp;(hash_entry-&gt;<a class="code" href="structHashEntry.html#o1">newest</a>);
00710     <span class="comment">/* try to update deepest entry */</span>
00711     <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[1] == deepest-&gt;<a class="code" href="structHash.html#o0">lock</a>) {
00712         <span class="keywordflow">if</span> (score &lt; beta &amp;&amp; score &lt; deepest-&gt;<a class="code" href="structHash.html#o2">upper</a>) 
00713             deepest-&gt;<a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;
00714         <span class="keywordflow">if</span> (score &gt; alpha &amp;&amp; score &gt; deepest-&gt;<a class="code" href="structHash.html#o1">lower</a>)
00715             deepest-&gt;<a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;
00716         deepest-&gt;<a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;
00717     <span class="comment">/* else try to update newest entry */</span>
00718     } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[1] == newest-&gt;<a class="code" href="structHash.html#o0">lock</a>) {
00719         <span class="keywordflow">if</span> (score &lt; beta &amp;&amp; score &lt; newest-&gt;<a class="code" href="structHash.html#o2">upper</a>)
00720             newest-&gt;<a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;
00721         <span class="keywordflow">if</span> (score &gt; alpha &amp;&amp; score &gt; newest-&gt;<a class="code" href="structHash.html#o1">lower</a>)
00722             newest-&gt;<a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;
00723         newest-&gt;<a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;
00724     <span class="comment">/* else try to add to deepest entry */</span>
00725     } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (deepest-&gt;<a class="code" href="structHash.html#o4">depth</a> &lt; board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a>) {
00726         <span class="keywordflow">if</span> (newest-&gt;<a class="code" href="structHash.html#o4">depth</a> &lt; deepest-&gt;<a class="code" href="structHash.html#o4">depth</a>) *newest = *deepest;
00727         deepest-&gt;<a class="code" href="structHash.html#o0">lock</a> = board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[1];
00728         deepest-&gt;depth = (<span class="keywordtype">char</span>) board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a>;
00729         deepest-&gt;lower = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;
00730         deepest-&gt;upper = +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;
00731         <span class="keywordflow">if</span> (score &lt; beta) deepest-&gt;upper = (<span class="keywordtype">char</span>) score;
00732         <span class="keywordflow">if</span> (score &gt; alpha) deepest-&gt;lower = (<span class="keywordtype">char</span>) score;
00733         deepest-&gt;move = (<span class="keywordtype">char</span>) move;
00734     <span class="comment">/* else add to newest entry */</span>
00735     } <span class="keywordflow">else</span> {
00736         newest-&gt;<a class="code" href="structHash.html#o0">lock</a> = board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[1];
00737         newest-&gt;<a class="code" href="structHash.html#o4">depth</a> = (<span class="keywordtype">char</span>) board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a>;
00738         newest-&gt;<a class="code" href="structHash.html#o1">lower</a> = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;
00739         newest-&gt;<a class="code" href="structHash.html#o2">upper</a> = +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;
00740         <span class="keywordflow">if</span> (score &lt; beta) newest-&gt;<a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;
00741         <span class="keywordflow">if</span> (score &gt; alpha) newest-&gt;<a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;
00742         newest-&gt;<a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;
00743     }
00744 }
</pre></div>    </td>
  </tr>
</table>
<hr size="1"><address style="align: right;"><small>Generated on Mon Apr 12 19:31:52 2004 for Othello Solver by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 > 
</a>1.3.5 </small></address>
</body>
</html>