?? group__hash.html
字號(hào):
<p>Initialise the hashtable. <p>Allocate the hash table entries and initialise the hash masks and codes. <dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>hash_table</em> </td><td>hash table to setup. </td></tr> <tr><td valign=top><em>n_bits</em> </td><td>requested size for the hash table in number of bits. </td></tr> </table></dl><p><div class="fragment"><pre>00618 {00619 <span class="keywordtype">int</span> i,j;00620 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> hash_mask[2], size = 1u << n_bits;00621 00622 <span class="keywordflow">if</span> (hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> != NULL) free(hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a>);00623 hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> = malloc(size * <span class="keyword">sizeof</span> (<a class="code" href="structHashEntry.html">HashEntry</a>));00624 <span class="keywordflow">if</span> (hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> == NULL) {00625 fprintf(stderr, <span class="stringliteral">"hash_init: cannot allocate the hash table\n"</span>);00626 exit(EXIT_FAILURE);00627 }00628 hash_mask[0] = hash_table-><a class="code" href="structHashTable.html#o1">hash_mask</a> = size - 1;00629 hash_mask[1] = 0xffffffff;00630 00631 <span class="keywordflow">for</span> (j = 0; j < 2; j++) {00632 hash_code_swap_player[j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() & hash_mask[j]);00633 <span class="keywordflow">for</span> (i = 0; i < <a class="code" href="group__mac.html#ga22">BOARD_SIZE</a>; i++) {00634 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() & hash_mask[j]);00635 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j] = (<a class="code" href="group__hash.html#ga0">hash_random</a>() & hash_mask[j]);00636 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a132">EMPTY</a>][j] = 0;00637 hash_code_flip_disc[i][j] = hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] ^00638 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j];00639 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a130">BLACK</a>][j] ^= hash_code_swap_player[j];00640 hash_code_set_disc[i][<a class="code" href="group__mac.html#gga58a131">WHITE</a>][j] ^= hash_code_swap_player[j];00641 }00642 }00643 }</pre></div> </td> </tr></table><a class="anchor" name="ga0" doxytag="solver.c::hash_random" ></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"> unsigned long hash_random </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">void </td> <td class="mdname1" valign="top" nowrap> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Pseudo-random number generator. <p>A good random generator (similar to rand48 or Java's one) to set the hash codes. <dl compact><dt><b>Returns:</b></dt><dd>a 32 bits random unsigned long integer. </dd></dl><p><div class="fragment"><pre>00591 {00592 <span class="keyword">static</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> x[3] = {0xe66du, 0xdeecu, 0x5u};00593 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> MASK = 0x0000ffffu;00594 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> A[3] = {0xe66du, 0xdeecu, 0x5u};00595 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> B = 0xBu;00596 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> product[3];00597 00598 product[0] = A[0] * x[0] + B;00599 product[1] = A[1] * x[0] + (product[0] >> 16);00600 product[2] = A[1] * x[1] + A[0] * x[2] + A[2] * x[0] + (product[1] >> 16);00601 product[1] = A[0] * x[1] + (product[1] & MASK);00602 product[2] += (product[1] >> 16);00603 x[0] = (product[0] & MASK);00604 x[1] = (product[1] & MASK);00605 x[2] = (product[2] & MASK);00606 00607 <span class="keywordflow">return</span> x[1] + (x[2] << 16);00608 }</pre></div> </td> </tr></table><a class="anchor" name="ga4" doxytag="solver.c::hash_update" ></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 hash_update </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><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>const <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>score</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>int </td> <td class="mdname" nowrap> <em>move</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>Update an hashtable entry. <p>Find an hash table entry according to the evaluated board hash codes. Then update the entry if it already exists otherwise create a new one. Collisions are managed in such a way that better existing entries are always preserved and the new evaluated data is always added. Lower and upper score bounds are then updated/set from the alpha, beta and score values according to the following alphabeta property (where alpha < beta): -if (score >= beta) score is a lower bound of the real score -if (score <= alpha) score is an upper bound of the real score -if (alpha < score && score < beta) score equals the real score So: -if (score < beta) update the upper bound of the hash entry -if (score > alpha) update the lower bound of the hash entry The best move is also stored. <dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>hash_table</em> </td><td>hash table to update. </td></tr> <tr><td valign=top><em>board</em> </td><td>evaluated board. </td></tr> <tr><td valign=top><em>alpha</em> </td><td>alpha bound when calling the alphabeta function. </td></tr> <tr><td valign=top><em>beta</em> </td><td>beta bound when calling the alphabeta function. </td></tr> <tr><td valign=top><em>score</em> </td><td>best score found. </td></tr> <tr><td valign=top><em>move</em> </td><td>best move found. </td></tr> </table></dl><p><div class="fragment"><pre>00701 {00702 <a class="code" href="structHashEntry.html">HashEntry</a> *hash_entry;00703 <a class="code" href="structHash.html">Hash</a> *deepest, *newest;00704 00705 <span class="keywordflow">if</span> (!<a class="code" href="group__mac.html#ga51">HASH_TABLE_OK</a>(hash_table)) <span class="keywordflow">return</span>;00706 00707 hash_entry = hash_table-><a class="code" href="structHashTable.html#o0">hash_entry</a> + board-><a class="code" href="structBoard.html#o5">hash_code</a>[0];00708 deepest = &(hash_entry-><a class="code" href="structHashEntry.html#o0">deepest</a>);00709 newest = &(hash_entry-><a class="code" href="structHashEntry.html#o1">newest</a>);00710 <span class="comment">/* try to update deepest entry */</span>00711 <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o5">hash_code</a>[1] == deepest-><a class="code" href="structHash.html#o0">lock</a>) {00712 <span class="keywordflow">if</span> (score < beta && score < deepest-><a class="code" href="structHash.html#o2">upper</a>) 00713 deepest-><a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;00714 <span class="keywordflow">if</span> (score > alpha && score > deepest-><a class="code" href="structHash.html#o1">lower</a>)00715 deepest-><a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;00716 deepest-><a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;00717 <span class="comment">/* else try to update newest entry */</span>00718 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (board-><a class="code" href="structBoard.html#o5">hash_code</a>[1] == newest-><a class="code" href="structHash.html#o0">lock</a>) {00719 <span class="keywordflow">if</span> (score < beta && score < newest-><a class="code" href="structHash.html#o2">upper</a>)00720 newest-><a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;00721 <span class="keywordflow">if</span> (score > alpha && score > newest-><a class="code" href="structHash.html#o1">lower</a>)00722 newest-><a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;00723 newest-><a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;00724 <span class="comment">/* else try to add to deepest entry */</span>00725 } <span class="keywordflow">else</span> <span class="keywordflow">if</span> (deepest-><a class="code" href="structHash.html#o4">depth</a> < board-><a class="code" href="structBoard.html#o3">n_empties</a>) {00726 <span class="keywordflow">if</span> (newest-><a class="code" href="structHash.html#o4">depth</a> < deepest-><a class="code" href="structHash.html#o4">depth</a>) *newest = *deepest;00727 deepest-><a class="code" href="structHash.html#o0">lock</a> = board-><a class="code" href="structBoard.html#o5">hash_code</a>[1];00728 deepest->depth = (<span class="keywordtype">char</span>) board-><a class="code" href="structBoard.html#o3">n_empties</a>;00729 deepest->lower = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;00730 deepest->upper = +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;00731 <span class="keywordflow">if</span> (score < beta) deepest->upper = (<span class="keywordtype">char</span>) score;00732 <span class="keywordflow">if</span> (score > alpha) deepest->lower = (<span class="keywordtype">char</span>) score;00733 deepest->move = (<span class="keywordtype">char</span>) move;00734 <span class="comment">/* else add to newest entry */</span>00735 } <span class="keywordflow">else</span> {00736 newest-><a class="code" href="structHash.html#o0">lock</a> = board-><a class="code" href="structBoard.html#o5">hash_code</a>[1];00737 newest-><a class="code" href="structHash.html#o4">depth</a> = (<span class="keywordtype">char</span>) board-><a class="code" href="structBoard.html#o3">n_empties</a>;00738 newest-><a class="code" href="structHash.html#o1">lower</a> = -<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;00739 newest-><a class="code" href="structHash.html#o2">upper</a> = +<a class="code" href="group__mac.html#ga21">INF_SCORE</a>;00740 <span class="keywordflow">if</span> (score < beta) newest-><a class="code" href="structHash.html#o2">upper</a> = (<span class="keywordtype">char</span>) score;00741 <span class="keywordflow">if</span> (score > alpha) newest-><a class="code" href="structHash.html#o1">lower</a> = (<span class="keywordtype">char</span>) score;00742 newest-><a class="code" href="structHash.html#o3">move</a> = (<span class="keywordtype">char</span>) move;00743 }00744 }</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>?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -