group__search.html

黑白棋终局解算程序

<p>
Get the final score, when 2 empty squares remain. <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>the board to evaluate. </td></tr>
    <tr><td valign=top><em>alpha</em>&nbsp;</td><td>upper score value. </td></tr>
    <tr><td valign=top><em>beta</em>&nbsp;</td><td>lower score value. </td></tr>
    <tr><td valign=top><em>passed</em>&nbsp;</td><td>a flag indicating if previous move was a pass. </td></tr>
  </table>
</dl>
<dl compact><dt><b>Returns:</b></dt><dd>the final score, as a disc difference. </dd></dl>

<p>
<div class="fragment"><pre>01745 {
01746     <span class="keyword">const</span> <span class="keywordtype">char</span> p = board-&gt;<a class="code" href="structBoard.html#o1">player</a>;
01747     <span class="keyword">const</span> <span class="keywordtype">char</span> o = <a class="code" href="group__mac.html#ga50">OPPONENT</a>(p);
01748     <a class="code" href="structSquareList.html">SquareList</a> *empties = board-&gt;<a class="code" href="structBoard.html#o7">empties</a>-&gt;<a class="code" href="structSquareList.html#o2">next</a>;
01749     <span class="keywordtype">int</span> x1 = empties-&gt;<a class="code" href="structSquareList.html#o0">position</a>;
01750     <span class="keywordtype">int</span> x2 = empties-&gt;<a class="code" href="structSquareList.html#o2">next</a>-&gt;<a class="code" href="structSquareList.html#o0">position</a>;
01751     <span class="keywordtype">int</span> score, bestscore, n1_flips, n2_flips, diff_discs;
01752     <a class="code" href="structMove.html">Move</a> move;
01753 
01754     diff_discs = board-&gt;<a class="code" href="structBoard.html#o2">n_discs</a>[(<span class="keywordtype">int</span>)p] - board-&gt;<a class="code" href="structBoard.html#o2">n_discs</a>[(<span class="keywordtype">int</span>)o];
01755     bestscore = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;
01756 
01757     <span class="comment">/* try to play on the first available square */</span>
01758     <span class="keywordflow">if</span> ((n1_flips = <a class="code" href="group__board.html#ga3">board_do_flip</a>(board, x1, &amp;move)) &gt; 0) {
01759         <span class="keywordflow">if</span> ((n2_flips = <a class="code" href="group__board.html#ga2">board_count_flips</a>(board, x2, o)) &gt; 0) {
01760             bestscore = diff_discs + 2 * (n1_flips - n2_flips);
01761             <a class="code" href="group__mac.html#ga27">BOARD_UPDATE_TERMINAL_NODES</a>();
01762         } <span class="keywordflow">else</span> <span class="keywordflow">if</span> ((n2_flips = <a class="code" href="group__board.html#ga2">board_count_flips</a>(board, x2, p)) &gt; 0) {
01763             bestscore = diff_discs + 2 * (n1_flips + n2_flips) + 2;
01764             <a class="code" href="group__mac.html#ga27">BOARD_UPDATE_TERMINAL_NODES</a>();
01765         } <span class="keywordflow">else</span> {
01766             bestscore = diff_discs + 2 * n1_flips + 1;
01767             <span class="keywordflow">if</span> (bestscore &gt; 0) bestscore++;
01768             <span class="keywordflow">else</span> <span class="keywordflow">if</span> (bestscore &lt; 0) bestscore--;
01769         }
01770         <a class="code" href="group__mac.html#ga37">BOARD_RESTORE_SQUARE</a>(board, &amp;move);
01771         <a class="code" href="group__mac.html#ga39">BOARD_RESTORE_PLAYER</a>(board);
01772     }
01773     <span class="comment">/* if needed, try to play on the second &amp; last available square */</span>
01774     <span class="keywordflow">if</span> (bestscore &lt; beta &amp;&amp; (n1_flips = board_do_flip(board, x2, &amp;move)) &gt; 0) {
01775         <span class="keywordflow">if</span> ((n2_flips = <a class="code" href="group__board.html#ga2">board_count_flips</a>(board, x1, o)) &gt; 0) {
01776             score = diff_discs + 2 * (n1_flips - n2_flips);
01777             <a class="code" href="group__mac.html#ga27">BOARD_UPDATE_TERMINAL_NODES</a>();
01778         } <span class="keywordflow">else</span> <span class="keywordflow">if</span> ((n2_flips = <a class="code" href="group__board.html#ga2">board_count_flips</a>(board, x1, p)) &gt; 0) {
01779             score = diff_discs + 2 * (n1_flips + n2_flips) + 2;
01780             <a class="code" href="group__mac.html#ga27">BOARD_UPDATE_TERMINAL_NODES</a>();
01781         } <span class="keywordflow">else</span> {
01782             score = diff_discs + 2 * n1_flips + 1;
01783             <span class="keywordflow">if</span> (score &gt; 0) score++;
01784             <span class="keywordflow">else</span> <span class="keywordflow">if</span> (score &lt; 0) score--;
01785         }
01786         <a class="code" href="group__mac.html#ga37">BOARD_RESTORE_SQUARE</a>(board, &amp;move);
01787         <a class="code" href="group__mac.html#ga39">BOARD_RESTORE_PLAYER</a>(board);
01788         <span class="keywordflow">if</span> (score &gt; bestscore) bestscore = score;
01789     }
01790     <span class="comment">/* if no move were available */</span>
01791     <span class="keywordflow">if</span> (bestscore == -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>) {
01792         <span class="keywordflow">if</span> (passed) { <span class="comment">/* game is over */</span>
01793             <a class="code" href="group__mac.html#ga28">BOARD_CORRECT_TERMINAL_NODES</a>();
01794             bestscore = diff_discs;
01795             <span class="keywordflow">if</span> (bestscore &gt; 0) bestscore += 2;
01796             <span class="keywordflow">else</span> <span class="keywordflow">if</span> (bestscore &lt; 0) bestscore -= 2;
01797         } <span class="keywordflow">else</span> { <span class="comment">/* pass... */</span>
01798             <a class="code" href="group__mac.html#ga38">BOARD_UPDATE_PLAYER</a>(board);
01799             <a class="code" href="group__mac.html#ga26">BOARD_UPDATE_INTERNAL_NODES</a>();
01800             bestscore = -<a class="code" href="group__search.html#ga3">board_get_final_score_2</a>(board, -beta, -alpha, 1);
01801             <a class="code" href="group__mac.html#ga39">BOARD_RESTORE_PLAYER</a>(board);
01802         }
01803     }
01804 
01805     <span class="keywordflow">return</span> bestscore;
01806 }
</pre></div>    </td>
  </tr>
</table>
<a class="anchor" name="ga5" doxytag="solver.c::PVS_deep" ></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"> int PVS_deep </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>int&nbsp;</td>
          <td class="mdname" nowrap> <em>passed</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>
Evaluate a position with a deep Principal Variation Search algorithm. 
<p>
This function is used when there are still many empty squares on the board. <a class="el" href="structMove.html">Move</a> ordering, hash table cutoff, enhanced transposition cutoff, etc. are used in order to diminish the size of the tree to analyse, but at the expense of a slower speed.<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. </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>passed</em>&nbsp;</td><td>a flag indicating if previous move was a pass. </td></tr>
  </table>
</dl>
<dl compact><dt><b>Returns:</b></dt><dd>the final score, as a disc difference. </dd></dl>

<p>
<div class="fragment"><pre>01897 {
01898     <span class="keywordtype">int</span> score, bestscore, lower, upper, bestmove;
01899     <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> hash_lock, hash_index;
01900     <a class="code" href="structMoveList.html">MoveList</a> movelist[<a class="code" href="group__mac.html#ga23">MAX_MOVE</a> + 2], *iter;
01901     <a class="code" href="structMove.html">Move</a> *move;
01902     <a class="code" href="structHash.html">Hash</a> *hash;
01903     <a class="code" href="structHashEntry.html">HashEntry</a> *hash_entry;
01904 
01905     bestmove = <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>;
01906     lower = alpha;
01907     upper = beta;
01908     <span class="comment">/* transposition cutoff ? */</span>
01909 <span class="preprocessor">#if USE_HASH_TABLE</span>
01910 <span class="preprocessor"></span>    hash = <a class="code" href="group__hash.html#ga5">hash_get</a>(hash_table, board);
01911     <span class="keywordflow">if</span> (hash != NULL) {
01912         <span class="keywordflow">if</span> (upper &gt; hash-&gt;<a class="code" href="structHash.html#o2">upper</a>) {
01913             upper = hash-&gt;<a class="code" href="structHash.html#o2">upper</a>;
01914             <span class="keywordflow">if</span> (upper &lt;= lower) <span class="keywordflow">return</span> upper;
01915         }
01916         <span class="keywordflow">if</span> (lower &lt; hash-&gt;<a class="code" href="structHash.html#o1">lower</a>) {
01917             lower = hash-&gt;<a class="code" href="structHash.html#o1">lower</a>;
01918             <span class="keywordflow">if</span> (lower &gt;= upper) <span class="keywordflow">return</span> lower;
01919         }
01920         bestmove = hash-&gt;<a class="code" href="structHash.html#o3">move</a>;
01921     }
01922 <span class="preprocessor">#endif</span>
01923 <span class="preprocessor"></span>    <a class="code" href="group__board.html#ga9">board_get_movelist</a>(board, movelist);
01924     <span class="keywordflow">if</span> (movelist-&gt;<a class="code" href="structMoveList.html#o1">next</a> == NULL) {
01925         <span class="keywordflow">if</span> (passed) {
01926             <a class="code" href="group__mac.html#ga28">BOARD_CORRECT_TERMINAL_NODES</a>();
01927             alpha = -(beta = +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>);
01928             bestscore = <a class="code" href="group__search.html#ga0">board_get_final_score</a>(board);
01929             bestmove = <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>;
01930         } <span class="keywordflow">else</span> {
01931             <a class="code" href="group__board.html#ga7">board_update_pass</a>(board);
01932             bestscore = -<a class="code" href="group__search.html#ga5">PVS_deep</a>(board, hash_table, -upper, -lower, 1);
01933             bestmove = <a class="code" href="group__mac.html#gga56a57">PASS</a>;
01934             <a class="code" href="group__board.html#ga8">board_restore_pass</a>(board);