?? group__search.html
字號:
02064 <span class="keywordflow">if</span> (lower < move-><a class="code" href="structMove.html#o2">score</a> && move-><a class="code" href="structMove.html#o2">score</a> < upper)02065 move-><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-><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-><a class="code" href="structMove.html#o2">score</a> > bestmove-><a class="code" href="structMove.html#o2">score</a>) {02069 bestmove = move;02070 <span class="keywordflow">if</span> (bestmove-><a class="code" href="structMove.html#o2">score</a> > lower) lower = bestmove-><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-><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-><a class="code" href="structMove.html#o2">score</a>, *bestmove-><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">( </td> <td class="md" nowrap valign="top"><a class="el" href="structBoard.html">Board</a> * </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> * </td> <td class="mdname" nowrap> <em>hash_table</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>int </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> * </td> <td class="mdname" nowrap> <em>bestmove</em></td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </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> </td><td>board to solve. </td></tr> <tr><td valign=top><em>hash_table</em> </td><td>hash table to memorize the analysis. </td></tr> <tr><td valign=top><em>mode</em> </td><td>search mode: exact or win/draw/loss. </td></tr> <tr><td valign=top><em>bestmove</em> </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-><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-><a class="code" href="structMoveList.html#o1">next</a> != NULL) { <span class="comment">/* normal play ? */</span>02106 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o3">n_empties</a> > <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-><a class="code" href="structMoveList.html#o1">next</a>-><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 > 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-><a class="code" href="structMoveList.html#o1">next</a>-><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 >= bound) {02132 <span class="comment">/* failed -> 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 < 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-><a class="code" href="structMoveList.html#o1">next</a>-><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 <= bound) {02141 <span class="comment">/* failed -> 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-><a class="code" href="structMoveList.html#o1">next</a>-><a class="code" href="structMoveList.html#o0">move</a>;02148 } <span class="keywordflow">else</span> { <span class="comment">/* pass ? */</span>02149 bestmove-><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-><a class="code" href="structMoveList.html#o1">next</a> == NULL) { <span class="comment">/* game over ? */</span>02153 bestmove-><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-><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-><a class="code" href="structBoard.html#o3">n_empties</a> > <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-><a class="code" href="structMoveList.html#o1">next</a>-><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 > 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-><a class="code" href="structMoveList.html#o1">next</a>-><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 >= 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 < 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-><a class="code" href="structMoveList.html#o1">next</a>-><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 <= 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-><a class="code" href="structMove.html#o2">score</a> = -movelist-><a class="code" href="structMoveList.html#o1">next</a>-><a class="code" href="structMoveList.html#o0">move</a>.<a class="code" href="structMove.html#o2">score</a>;02187 *bestmove-><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>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -