?? 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-><a class="code" href="structBoard.html#o3">n_empties</a> > <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a> &&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-><a class="code" href="structMoveList.html#o1">next</a>; iter != NULL; iter = iter-><a class="code" href="structMoveList.html#o1">next</a>) {01943 move = &(iter-><a class="code" href="structMoveList.html#o0">move</a>);01944 hash_index = (board-><a class="code" href="structBoard.html#o5">hash_code</a>[0] ^ move-><a class="code" href="structMove.html#o3">hash_code</a>[0]);01945 hash_lock = (board-><a class="code" href="structBoard.html#o5">hash_code</a>[1] ^ move-><a class="code" href="structMove.html#o3">hash_code</a>[1]);01946 hash_entry = hash_table-><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-><a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o0">lock</a> == hash_lock && -hash_entry-><a class="code" href="structHashEntry.html#o0">deepest</a>.<a class="code" href="structHash.html#o2">upper</a> >= upper)01949 <span class="keywordflow">return</span> -hash_entry-><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-><a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o0">lock</a> == hash_lock && -hash_entry-><a class="code" href="structHashEntry.html#o1">newest</a>.<a class="code" href="structHash.html#o2">upper</a> >= upper)01951 <span class="keywordflow">return</span> -hash_entry-><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-><a class="code" href="structBoard.html#o3">n_empties</a> > <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> && bestmove != *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#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-><a class="code" href="structMoveList.html#o1">next</a>;01967 move = &(iter-><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-><a class="code" href="structBoard.html#o3">n_empties</a> < <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-><a class="code" href="structMove.html#o0">position</a>;01975 <span class="keywordflow">if</span> (bestscore > 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-><a class="code" href="structMoveList.html#o1">next</a>; lower < upper && iter != NULL; iter = iter-><a class="code" href="structMoveList.html#o1">next</a>) {01980 move = &(iter-><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-><a class="code" href="structBoard.html#o3">n_empties</a> < <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 < score && score < 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 < score && score < 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 > bestscore) {01993 bestscore = score;01994 bestmove = *move-><a class="code" href="structMove.html#o0">position</a>;01995 <span class="keywordflow">if</span> (bestscore > 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">( </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>alpha</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>int </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> * </td> <td class="mdname" nowrap> <em>movelist</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>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> </td><td>board. </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>alpha</em> </td><td>lower bound. </td></tr> <tr><td valign=top><em>beta</em> </td><td>upper bound. </td></tr> <tr><td valign=top><em>movelist</em> </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-><a class="code" href="structBoard.html#o4">n_nodes</a>++;02029 02030 <span class="comment">/* first move */</span>02031 iter = movelist-><a class="code" href="structMoveList.html#o1">next</a>;02032 bestmove = &(iter-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 0) {02035 bestmove-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 1) {02037 bestmove-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 2) {02039 bestmove-><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-><a class="code" href="structBoard.html#o3">n_empties</a> < <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {02041 bestmove-><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-><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-><a class="code" href="structMove.html#o2">score</a> > lower) lower = bestmove-><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-><a class="code" href="structMoveList.html#o1">next</a>; lower < upper && iter != NULL; iter = iter-><a class="code" href="structMoveList.html#o1">next</a>) {02050 move = &(iter-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 0) {02053 move-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 1) {02055 move-><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-><a class="code" href="structBoard.html#o3">n_empties</a> == 2) {02057 move-><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-><a class="code" href="structBoard.html#o3">n_empties</a> < <a class="code" href="group__mac.html#ga12">EMPTIES_DEEP_TO_SHALLOW_SEARCH</a>) {02059 move-><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 < move-><a class="code" href="structMove.html#o2">score</a> && move-><a class="code" href="structMove.html#o2">score</a> < upper)02061 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);02062 } <span class="keywordflow">else</span> {02063 move-><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);?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -