group__search.html

黑白棋终局解算程序

02064             <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)
02065                 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);
02066         }
02067         <a class="code" href="group__board.html#ga6">board_restore_move</a>(board, move);
02068         <span class="keywordflow">if</span> (move-&gt;<a class="code" href="structMove.html#o2">score</a> &gt; bestmove-&gt;<a class="code" href="structMove.html#o2">score</a>) {
02069             bestmove = move;
02070             <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>;
02071         }
02072     }
02073     <a class="code" href="group__move.html#ga2">movelist_sort_bestmove</a>(movelist, *bestmove-&gt;<a class="code" href="structMove.html#o0">position</a>);
02074 <span class="preprocessor">#if USE_HASH_TABLE</span>
02075 <span class="preprocessor"></span>    <a class="code" href="group__hash.html#ga4">hash_update</a>(hash_table, board, alpha, beta, bestmove-&gt;<a class="code" href="structMove.html#o2">score</a>, *bestmove-&gt;<a class="code" href="structMove.html#o0">position</a>);
02076 <span class="preprocessor">#endif</span>
02077 <span class="preprocessor"></span>}
</pre></div>    </td>
  </tr>
</table>
<a class="anchor" name="ga7" doxytag="solver.c::solve" ></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 solve </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>mode</em>, </td>
        </tr>
        <tr>
          <td></td>
          <td></td>
          <td class="md" nowrap><a class="el" href="structMove.html">Move</a> *&nbsp;</td>
          <td class="mdname" nowrap> <em>bestmove</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>
Search the bestmove of a given board. 
<p>
Depending on the mode, the function will try to solve for a draw (DL_SCORE), a win (WD_SCORE), the exact outcome (WDL_SCORE) or the exact score. For the latter case, aspiration windows have been implemented. Thus, the search does not start with a plain alphabeta window [-INF_SCORE, +INF_SCORE], but with a reduce window [-1, +1] that will just find who is the winner. In case the game outcome is a draw, the search will stop here otherwise another search with a [+1, +8] window for the winner side will start. If the winning score falls within these bounds, the search is stopped else it is restarted with a last window of [+8, +64]. The search is then made within the PVS_root function.<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 to solve. </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>mode</em>&nbsp;</td><td>search mode: exact or win/draw/loss. </td></tr>
    <tr><td valign=top><em>bestmove</em>&nbsp;</td><td>the bestmove found. </td></tr>
  </table>
</dl>

<p>
<div class="fragment"><pre>02099 {
02100     <span class="keywordtype">int</span> score, bound;
02101     <a class="code" href="structMoveList.html">MoveList</a> movelist[<a class="code" href="group__mac.html#ga23">MAX_MOVE</a> + 2];
02102 
02103     board-&gt;<a class="code" href="structBoard.html#o4">n_nodes</a> = 0;
02104     <a class="code" href="group__board.html#ga9">board_get_movelist</a>(board, movelist);
02105     <span class="keywordflow">if</span> (movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a> != NULL) { <span class="comment">/* normal play ? */</span>
02106         <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>)
02107             <a class="code" href="group__move.html#ga3">movelist_sort_fastfirst</a>(movelist, board);
02108         <span class="keywordflow">switch</span> (mode) {
02109         <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a137">DL_SCORE</a>:
02110             <span class="comment">/* look for a draw or a loss */</span>
02111             <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1,  0, movelist);
02112             <span class="keywordflow">break</span>;
02113         <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a136">WD_SCORE</a>:
02114             <span class="comment">/* look for a win or a draw */</span>
02115             <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table,  0, +1, movelist);
02116             <span class="keywordflow">break</span>;
02117         <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a135">WDL_SCORE</a>:
02118             <span class="comment">/* look for a win or a draw or a loss */</span>
02119             <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1, +1, movelist);
02120             <span class="keywordflow">break</span>;
02121         <span class="keywordflow">default</span>:
02122             <span class="comment">/* look for the exact best score */</span>
02123             <span class="comment">/* start to look for a win or a draw or a loss */</span>
02124             <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1, +1, movelist);
02125             score = 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#o2">score</a>;
02126             <span class="keywordflow">if</span> (score &gt; 0) {
02127                 <span class="comment">/* if a win look for a score between [+2 +8] */</span>
02128                 bound = score + 8;
02129                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, score, bound, movelist);
02130                 score = 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#o2">score</a>;
02131                 <span class="keywordflow">if</span> (score &gt;= bound) {
02132                     <span class="comment">/* failed -&gt; look for a score between [+8, +64] */</span>
02133                     <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, score, +MAX_SCORE, movelist);
02134                 }
02135             } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (score &lt; 0) {
02136                 <span class="comment">/* if a loss look for a score between [-8 -2] */</span>
02137                 bound = score - 8;
02138                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, bound, score, movelist);
02139                 score = 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#o2">score</a>;
02140                 <span class="keywordflow">if</span> (score &lt;= bound) {
02141                     <span class="comment">/* failed -&gt; look for a score between [-64, -8] */</span>
02142                     <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -MAX_SCORE, score, movelist);
02143                 }
02144             }
02145             <span class="keywordflow">break</span>;
02146         }
02147         *bestmove = movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a>-&gt;<a class="code" href="structMoveList.html#o0">move</a>;
02148     } <span class="keywordflow">else</span> { <span class="comment">/* pass ? */</span>
02149         bestmove-&gt;<a class="code" href="structMove.html#o1">n</a> = 0;
02150         <a class="code" href="group__board.html#ga7">board_update_pass</a>(board);
02151         <a class="code" href="group__board.html#ga9">board_get_movelist</a>(board, movelist);
02152         <span class="keywordflow">if</span> (movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a> == NULL) { <span class="comment">/* game over ? */</span>
02153             bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -<a class="code" href="group__search.html#ga0">board_get_final_score</a>(board);
02154             *bestmove-&gt;<a class="code" href="structMove.html#o0">position</a> = <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>;
02155         } <span class="keywordflow">else</span> {
02156             <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>)
02157                 <a class="code" href="group__move.html#ga3">movelist_sort_fastfirst</a>(movelist, board);
02158             <span class="keywordflow">switch</span> (mode) {
02159             <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a137">DL_SCORE</a>:
02160                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table,  0, +1, movelist);
02161                 <span class="keywordflow">break</span>;
02162             <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a136">WD_SCORE</a>:
02163                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1,  0, movelist);
02164                 <span class="keywordflow">break</span>;
02165             <span class="keywordflow">case</span> <a class="code" href="group__mac.html#gga59a135">WDL_SCORE</a>:
02166                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1, +1, movelist);
02167                 <span class="keywordflow">break</span>;
02168             <span class="keywordflow">default</span>:
02169                 <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -1, +1, movelist);
02170                 score = 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#o2">score</a>;
02171                 <span class="keywordflow">if</span> (score &gt; 0) {
02172                     bound = score + 8;
02173                     <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, score, bound, movelist);
02174                     score = 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#o2">score</a>;
02175                     <span class="keywordflow">if</span> (score &gt;= bound)
02176                         <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, score, +MAX_SCORE, movelist);
02177                 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (score &lt; 0) {
02178                     bound = score - 8;
02179                     <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, bound, score, movelist);
02180                     score = 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#o2">score</a>;
02181                     <span class="keywordflow">if</span> (score &lt;= bound)
02182                         <a class="code" href="group__search.html#ga6">PVS_root</a>(board, hash_table, -MAX_SCORE, score, movelist);
02183                 }
02184                 <span class="keywordflow">break</span>;
02185             }
02186             bestmove-&gt;<a class="code" href="structMove.html#o2">score</a> = -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#o2">score</a>;
02187             *bestmove-&gt;<a class="code" href="structMove.html#o0">position</a> = <a class="code" href="group__mac.html#gga56a57">PASS</a>;
02188         }
02189         <a class="code" href="group__board.html#ga8">board_restore_pass</a>(board);
02190     }
02191 }
</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>