group__search.html

黑白棋终局解算程序

01935         }
01936     } <span class="keywordflow">else</span> {
01937         <span class="comment">/* enhanced transposition cutoff */</span>
01938 <span class="preprocessor">#if USE_ENHANCED_TRANSPOSITION_CUTOFF</span>
01939 <span class="preprocessor"></span>        <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &gt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a> &amp;&amp;
01940             <a class="code" href="group__mac.html#ga51">HASH_TABLE_OK</a>(hash_table)) {
01941             <span class="keywordflow">if</span> (bestmove != <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>) <a class="code" href="group__move.html#ga2">movelist_sort_bestmove</a>(movelist, bestmove);
01942             <span class="keywordflow">for</span> (iter = movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a>; iter != NULL; iter = iter-&gt;<a class="code" href="structMoveList.html#o1">next</a>) {
01943                 move = &amp;(iter-&gt;<a class="code" href="structMoveList.html#o0">move</a>);
01944                 hash_index = (board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[0] ^ move-&gt;<a class="code" href="structMove.html#o3">hash_code</a>[0]);
01945                 hash_lock = (board-&gt;<a class="code" href="structBoard.html#o5">hash_code</a>[1] ^ move-&gt;<a class="code" href="structMove.html#o3">hash_code</a>[1]);
01946                 hash_entry = hash_table-&gt;<a class="code" href="structHashTable.html#o0">hash_entry</a> + hash_index;
01947                 <a class="code" href="group__mac.html#ga29">BOARD_UPDATE_ALL_NODES</a>();
01948                 <span class="keywordflow">if</span> (hash_entry-&gt;<a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o0">lock</a> ==  hash_lock &amp;&amp; -hash_entry-&gt;<a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o2">upper</a> &gt;= upper)
01949                     <span class="keywordflow">return</span> -hash_entry-&gt;<a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o2">upper</a>;
01950                 <span class="keywordflow">if</span> (hash_entry-&gt;<a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o0">lock</a> ==  hash_lock &amp;&amp; -hash_entry-&gt;<a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o2">upper</a> &gt;= upper)
01951                     <span class="keywordflow">return</span> -hash_entry-&gt;<a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o2">upper</a>;
01952             }
01953         }
01954 <span class="preprocessor">#endif</span>
01955 <span class="preprocessor"></span>        <span class="comment">/* move sorting */</span>
01956 <span class="preprocessor">#if PLAY_FAST_SUBTREE_FIRST</span>
01957 <span class="preprocessor"></span>        <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &gt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>)
01958             <a class="code" href="group__move.html#ga3">movelist_sort_fastfirst</a>(movelist, board);
01959 <span class="preprocessor">#endif</span>
01960 <span class="preprocessor"></span><span class="preprocessor">#if PLAY_BEST_MOVE_IN_MEMORY_FIRST</span>
01961 <span class="preprocessor"></span>        <span class="keywordflow">if</span> (bestmove != <a class="code" href="group__mac.html#gga56a56">NOMOVE</a> &amp;&amp; bestmove != *movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a>-&gt;<a class="code" href="structMoveList.html#o0">move</a>.<a class="code" href="structMove.html#o0">position</a>)
01962             <a class="code" href="group__move.html#ga2">movelist_sort_bestmove</a>(movelist, bestmove);
01963 <span class="preprocessor">#endif</span>
01964 <span class="preprocessor"></span>
01965         <span class="comment">/* first move */</span>
01966         iter = movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a>;
01967         move = &amp;(iter-&gt;<a class="code" href="structMoveList.html#o0">move</a>);
01968         <a class="code" href="group__board.html#ga5">board_update_move</a>(board, move);
01969         <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &lt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {
01970             bestscore = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -upper, -lower, 0);
01971         } <span class="keywordflow">else</span> {
01972             bestscore = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -upper, -lower, 0);
01973         }
01974         bestmove = *move-&gt;<a class="code" href="structMove.html#o0">position</a>;
01975         <span class="keywordflow">if</span> (bestscore &gt; lower) lower = bestscore;
01976         <a class="code" href="group__board.html#ga6">board_restore_move</a>(board, move);
01977 
01978         <span class="comment">/* other moves : try to refute the first/best one */</span>
01979         <span class="keywordflow">for</span> (iter = iter-&gt;<a class="code" href="structMoveList.html#o1">next</a>; lower &lt; upper &amp;&amp; iter != NULL; iter = iter-&gt;<a class="code" href="structMoveList.html#o1">next</a>) {
01980             move = &amp;(iter-&gt;<a class="code" href="structMoveList.html#o0">move</a>);
01981             <a class="code" href="group__board.html#ga5">board_update_move</a>(board, move);
01982             <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &lt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {
01983                 score = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -lower - 1, -lower, 0);
01984                 <span class="keywordflow">if</span> (lower &lt; score &amp;&amp; score &lt; upper)
01985                     score = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -upper, -score, 0);
01986             } <span class="keywordflow">else</span> {
01987                 score = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -lower - 1, -lower, 0);
01988                 <span class="keywordflow">if</span> (lower &lt; score &amp;&amp; score &lt; upper)
01989                     score = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -upper, -score, 0);
01990             }
01991             <a class="code" href="group__board.html#ga6">board_restore_move</a>(board, move);
01992             <span class="keywordflow">if</span> (score &gt; bestscore) {
01993                 bestscore = score;
01994                 bestmove = *move-&gt;<a class="code" href="structMove.html#o0">position</a>;
01995                 <span class="keywordflow">if</span> (bestscore &gt; lower) lower = bestscore;
01996             }
01997         }
01998     }
01999 <span class="preprocessor">#if USE_HASH_TABLE</span>
02000 <span class="preprocessor"></span>    <a class="code" href="group__hash.html#ga4">hash_update</a>(hash_table, board, alpha, beta, bestscore, bestmove);
02001 <span class="preprocessor">#endif</span>
02002 <span class="preprocessor"></span>
02003     <span class="keywordflow">return</span> bestscore;
02004 }
</pre></div>    </td>
  </tr>
</table>
<a class="anchor" name="ga6" doxytag="solver.c::PVS_root" ></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 PVS_root </td>
          <td class="md" valign="top">(&nbsp;</td>
          <td class="md" nowrap valign="top"><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><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>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><a class="el" href="structMoveList.html">MoveList</a> *&nbsp;</td>
          <td class="mdname" nowrap> <em>movelist</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>
Principal Variation Search algorithm at the root of the tree. 
<p>
This function solves the position provided within the limits set by the alpha and beta bounds. The movelist parameter is updated so that the bestmove is the first of the list when the search ended.<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
  <table border="0" cellspacing="2" cellpadding="0">
    <tr><td valign=top><em>board</em>&nbsp;</td><td>board. </td></tr>
    <tr><td valign=top><em>hash_table</em>&nbsp;</td><td>hash table to memorize the analysis. </td></tr>
    <tr><td valign=top><em>alpha</em>&nbsp;</td><td>lower bound. </td></tr>
    <tr><td valign=top><em>beta</em>&nbsp;</td><td>upper bound. </td></tr>
    <tr><td valign=top><em>movelist</em>&nbsp;</td><td>List of legal moves (should actually contain moves !). </td></tr>
  </table>
</dl>

<p>
<div class="fragment"><pre>02021 {
02022     <span class="keywordtype">int</span> lower, upper;
02023     <a class="code" href="structMoveList.html">MoveList</a> *iter;
02024     <a class="code" href="structMove.html">Move</a> *move, *bestmove;
02025 
02026     lower = alpha;
02027     upper = beta;
02028     board-&gt;<a class="code" href="structBoard.html#o4">n_nodes</a>++;
02029 
02030     <span class="comment">/* first move */</span>
02031     iter = movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a>;
02032     bestmove = &amp;(iter-&gt;<a class="code" href="structMoveList.html#o0">move</a>);
02033     <a class="code" href="group__board.html#ga5">board_update_move</a>(board, bestmove);
02034     <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 0) {
02035         bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga1">board_get_final_score_0</a>(board);
02036     } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 1) {
02037         bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga2">board_get_final_score_1</a>(board);
02038     } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 2) {
02039         bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga3">board_get_final_score_2</a>(board, -upper, -lower, 0);
02040     } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &lt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {
02041         bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -upper, -lower, 0);
02042     } <span class="keywordflow">else</span> {
02043         bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -upper, -lower, 0);
02044     }
02045     <span class="keywordflow">if</span> (bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> &gt; lower) lower = bestmove-&gt;<a class="code" href="structMove.html#o2">score</a>;
02046     <a class="code" href="group__board.html#ga6">board_restore_move</a>(board, bestmove);
02047 
02048     <span class="comment">/* other moves : try to refute the first/best one */</span>
02049     <span class="keywordflow">for</span> (iter = iter-&gt;<a class="code" href="structMoveList.html#o1">next</a>; lower &lt; upper &amp;&amp; iter != NULL; iter = iter-&gt;<a class="code" href="structMoveList.html#o1">next</a>) {
02050         move = &amp;(iter-&gt;<a class="code" href="structMoveList.html#o0">move</a>);
02051         <a class="code" href="group__board.html#ga5">board_update_move</a>(board, move);
02052         <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 0) {
02053             move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga1">board_get_final_score_0</a>(board);
02054         } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 1) {
02055             move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga2">board_get_final_score_1</a>(board);
02056         } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> == 2) {
02057             move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga3">board_get_final_score_2</a>(board, -upper, -lower, 0);
02058         } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-&gt;<a class="code" href="structBoard.html#o3">n_empties</a> &lt; <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {
02059             move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -lower - 1, -lower, 0);
02060             <span class="keywordflow">if</span> (lower &lt; move-&gt;<a class="code" href="structMove.html#o2">score</a> &amp;&amp; move-&gt;<a class="code" href="structMove.html#o2">score</a> &lt; upper)
02061                 move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -upper, -move-&gt;<a class="code" href="structMove.html#o2">score</a>, 0);
02062         } <span class="keywordflow">else</span> {
02063             move-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -lower - 1, -lower, 0);