?? group__search.html
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>Othello Solver: Search module</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="modules.html">Modules</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a></div><h1>Search module</h1><table border=0 cellpadding=0 cellspacing=0><tr><td></td></tr><tr><td colspan=2><br><h2>Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga0">board_get_final_score</a> (const <a class="el" href="structBoard.html">Board</a> *board)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Get the final score. <a href="#ga0"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga1">board_get_final_score_0</a> (const <a class="el" href="structBoard.html">Board</a> *board)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Get the final score. <a href="#ga1"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga2">board_get_final_score_1</a> (<a class="el" href="structBoard.html">Board</a> *board)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Get the final score. <a href="#ga2"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga3">board_get_final_score_2</a> (<a class="el" href="structBoard.html">Board</a> *board, int alpha, int beta, int passed)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Get the final score. <a href="#ga3"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga4">alphabeta_shallow</a> (<a class="el" href="structBoard.html">Board</a> *board, int alpha, int beta, int passed)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Evaluate a position using a shallow Alphabeta. <a href="#ga4"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>int </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga5">PVS_deep</a> (<a class="el" href="structBoard.html">Board</a> *board, <a class="el" href="structHashTable.html">HashTable</a> *hash_table, int alpha, int beta, int passed)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Evaluate a position with a deep Principal Variation Search algorithm. <a href="#ga5"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga6">PVS_root</a> (<a class="el" href="structBoard.html">Board</a> *board, <a class="el" href="structHashTable.html">HashTable</a> *hash_table, int alpha, int beta, <a class="el" href="structMoveList.html">MoveList</a> *movelist)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Principal Variation Search algorithm at the root of the tree. <a href="#ga6"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="group__search.html#ga7">solve</a> (<a class="el" href="structBoard.html">Board</a> *board, <a class="el" href="structHashTable.html">HashTable</a> *hash_table, int mode, <a class="el" href="structMove.html">Move</a> *bestmove)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Search the bestmove of a given board. <a href="#ga7"></a><br><br></td></tr></table><hr><a name="_details"></a><h2>Detailed Description</h2>Functions that evaluate a board with different methods depending on the position in the tree search and/or that finds the best move of a given board.<p>At the end of the game, some trivial functions are used to compute the score. Optimization here is reached by maintaining a disc number record that is updated each time a move is made. At the end of the game, computing the score consists only to a simple substraction. For further optimization, the last move is not made and only the number of flipped discs is evaluated. Special and optimized functions are used when one or two empty squares remain on the board, in order to speed up the search.<p>The search of the best move is driven with the Principal Variation Search algorithm (PVS) [1], an enhanced variation of the alphabeta algorithm. The alphabeta algorithm is known to visit less nodes when the alphabeta window is reduced. PVS takes this property into account. From a set of sibling nodes, the first node is searched using a plain alpha beta window. Then the sibling nodes are only searched with minimal windows (where beta = alpha + 1), just to refute the best (first) score. In rare cases the first move is actually refuted, then the current move is re-searched a second time in order to determinate its score more accurately. On highly ordered tree, very few re-searches will be done. Moreover, thanks to the hash table, a second search is usually faster than a first search. So the seldom and fast re-searches will not impact too much the benefit of using minimal windows. Aspiration windows have been added as another improvement, so that even the first search is done with a reduced window. During the 1990s, several re-re-search algorithm based on null-window alphabeta have been proposed : SSS*ab [2], Dual*ab[2], NegaC*[3], MDT[2], negascout[4]. Some (unpublished) experimental tests I made with them did not show any significant improvement compare to the PVS algorithm with aspiration-windows used here.<p>To be efficient PVS need highly ordered tree. The following ordering have been made :<ul><li>fixed square ordering : square usually leading to a good move are visited first, ie from corner squares to X and C squares.</li><li>most stable ordering : a crude evaluation of stability at the corner (corner, X and C squares) to order the moves.</li><li>fast first ordering : the moves leading to the most reduced mobility for the opponent are played first.</li><li>best move previously found : If the position have been previously searched, the best move that was found is replayed as the first move.</li></ul><p><ol><li>Campbell MS & Marsland TA (1983) A Comparison of Minimax Trees Search Algorithms. Artificial Intelligence, 20, pp. 347-367.</li><li>Plaat A. et al. (1996) Best-First Fixed Depth Minimax Algorithms. Artificial Intelligence, 84, pp. 255-293.</li><li>Weill JC. (1992) Experiments With The NegaC* Search. An alternative for Othello Endgame Search. ICCA journal, 15(1), pp. 3-7.</li><li>Reinsfeld A. (1983) An Improvement Of the Scout Tree-Search Algorithm. ICCA journal, 6(4), pp. 4-14. </li></ol><hr><h2>Function Documentation</h2><a class="anchor" name="ga4" doxytag="solver.c::alphabeta_shallow" ></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 alphabeta_shallow </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>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>int </td> <td class="mdname" nowrap> <em>passed</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>Evaluate a position using a shallow Alphabeta. <p>This function is used when there are few empty squares on the board. Here, optimizations are in favour of speed instead of efficiency. A simple alphabeta is used because of the low branching factor that makes PVS less efficient. <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>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>passed</em> </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>01822 {01823 <span class="keyword">const</span> <span class="keywordtype">char</span> p = board-><a class="code" href="structBoard.html#o1">player</a>;01824 <span class="keyword">const</span> <span class="keywordtype">char</span> o = <a class="code" href="group__mac.html#ga50">OPPONENT</a>(p);01825 <span class="keywordtype">int</span> score, bestscore = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;01826 <a class="code" href="structSquareList.html">SquareList</a> *empties;01827 <a class="code" href="structMove.html">Move</a> move;01828 01829 <span class="preprocessor">#if PLAY_ODD_SQUARE_FIRST</span>01830 <span class="preprocessor"></span> <span class="keywordtype">int</span> parity;01831 <span class="keywordflow">for</span> (parity = 1; parity >= 0; parity--) {01832 <span class="keywordflow">for</span> (empties = board-><a class="code" href="structBoard.html#o7">empties</a>-><a class="code" href="structSquareList.html#o2">next</a>; empties-><a class="code" href="structSquareList.html#o0">position</a> != <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>; empties = empties-><a class="code" href="structSquareList.html#o2">next</a>) {01833 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o6">parity</a>[<a class="code" href="group__mac.html#ga1">QUADRANT_ID</a>[empties-><a class="code" href="structSquareList.html#o0">position</a>]] == parity01834 && <a class="code" href="group__board.html#ga3">board_do_flip</a>(board, empties-><a class="code" href="structSquareList.html#o0">position</a>, &move)) {01835 <span class="preprocessor">#else</span>01836 <span class="preprocessor"></span> {01837 <span class="keywordflow">for</span> (empties = board-><a class="code" href="structBoard.html#o7">empties</a>-><a class="code" href="structSquareList.html#o2">next</a>; empties-><a class="code" href="structSquareList.html#o0">position</a> != <a class="code" href="group__mac.html#gga56a56">NOMOVE</a>; empties = empties-><a class="code" href="structSquareList.html#o2">next</a>) {01838 <span class="keywordflow">if</span> (<a class="code" href="group__board.html#ga3">board_do_flip</a>(board, empties-><a class="code" href="structSquareList.html#o0">position</a>, &move)) {01839 <span class="preprocessor">#endif</span>01840 <span class="preprocessor"></span> <a class="code" href="group__mac.html#ga38">BOARD_UPDATE_PLAYER</a>(board);01841 <a class="code" href="group__mac.html#ga40">BOARD_UPDATE_DISCS</a>(board, move.<a class="code" href="structMove.html#o1">n</a>);01842 <a class="code" href="group__mac.html#ga42">BOARD_UPDATE_PARITY</a>(board, *move.<a class="code" href="structMove.html#o0">position</a>);01843 <a class="code" href="group__mac.html#ga44">BOARD_UPDATE_EMPTIES</a>(board, empties, *move.<a class="code" href="structMove.html#o0">position</a>);01844 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o3">n_empties</a> == 2) {01845 score = -<a class="code" href="group__search.html#ga3">board_get_final_score_2</a>(board, -beta, -alpha, 0);01846 } <span class="keywordflow">else</span> {01847 score = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -beta, -alpha, 0);01848 }01849 <a class="code" href="group__mac.html#ga37">BOARD_RESTORE_SQUARE</a>(board, &move);01850 <a class="code" href="group__mac.html#ga39">BOARD_RESTORE_PLAYER</a>(board);01851 <a class="code" href="group__mac.html#ga41">BOARD_RESTORE_DISCS</a>(board, move.<a class="code" href="structMove.html#o1">n</a>);01852 <a class="code" href="group__mac.html#ga43">BOARD_RESTORE_PARITY</a>(board, *move.<a class="code" href="structMove.html#o0">position</a>);01853 <a class="code" href="group__mac.html#ga45">BOARD_RESTORE_EMPTIES</a>(board, empties, *move.<a class="code" href="structMove.html#o0">position</a>);01854 <span class="keywordflow">if</span> (score > bestscore) {01855 bestscore = score;01856 <span class="keywordflow">if</span> (bestscore > alpha) {01857 alpha = bestscore;01858 <span class="keywordflow">if</span> (alpha >= beta) <span class="keywordflow">return</span> bestscore;01859 }01860 }01861 }01862 }01863 }01864 01865 <span class="comment">/* no move */</span>01866 <span class="keywordflow">if</span> (bestscore == -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>) {01867 <span class="keywordflow">if</span> (passed) { <span class="comment">/* game over */</span>01868 <a class="code" href="group__mac.html#ga28">BOARD_CORRECT_TERMINAL_NODES</a>();01869 bestscore = <a class="code" href="group__search.html#ga0">board_get_final_score</a>(board);01870 } <span class="keywordflow">else</span> { <span class="comment">/* pass */</span>01871 <a class="code" href="group__mac.html#ga38">BOARD_UPDATE_PLAYER</a>(board);01872 <a class="code" href="group__mac.html#ga26">BOARD_UPDATE_INTERNAL_NODES</a>();01873 bestscore = -<a class="code" href="group__search.html#ga4">alphabeta_shallow</a>(board, -beta, -alpha, 1);01874 <a class="code" href="group__mac.html#ga39">BOARD_RESTORE_PLAYER</a>(board);01875 }01876 }01877 01878 <span class="keywordflow">return</span> bestscore;01879 }</pre></div> </td> </tr></table><a class="anchor" name="ga0" doxytag="solver.c::board_get_final_score" ></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 board_get_final_score </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">const <a class="el" href="structBoard.html">Board</a> * </td> <td class="mdname1" valign="top" nowrap> <em>board</em> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -