📄 index.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: Main Page</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindexHL" 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>Othello Solver Documentation</h1><p><h3 align="center">version 1.4 </h3><a class="el" href="solver_8c.html">solver.c</a> : a program to solve Othello endgame script.<ul><li>copyleft (c) 2001-2004</li><li>version 1.4 (2004-04-12 18:00:00)</li><li>author: Richard A Delorme</li><li>e-mail: <a href="mailto:abulmo@club-internet.fr">abulmo@club-internet.fr</a></li><li>web site: <a href="http://perso.club-internet.fr/abulmo/resources/">http://perso.club-internet.fr/abulmo/resources/</a></li></ul><h2><a class="anchor" name="lic">Licence</a></h2>This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.<p>This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.<p>You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA<h2><a class="anchor" name="dl">Download</a></h2>You can download the source with its documentation here: <a href="http://perso.club-internet.fr/abulmo/resources/solver/solver.1-4.zip">http://perso.club-internet.fr/abulmo/resources/solver/solver.1-4.zip</a><h2><a class="anchor" name="pres">Presentation</a></h2>"The important decisions in design are not what to put in but what to leave out." Tony Hoare<p>At <a href="ftp://ftp.nj.nec.com/pub/igord/IOS/src">ftp://ftp.nj.nec.com/pub/igord/IOS/src</a>, an Othello archive site, there is a program about endgame solving firstly written by Jean-Christophe Weill, then improved by Warren D Smith and further improved by Gunnar Anderson. Although my work was greatly influenced by these programs, the solver I present here is not another improvement but a complete re-implementation, done in a few hours by cutting and pasting code from my own program Edax. I tried to write an optimized but readable code, two incompatible things. Do not forget that the C language is a write-only language :-( Compared to their previous works:<ul><li>more general user interface. In addition to the best score, this solver also provides the best move and (if hash table is ON) the best principal variation, some performance data and, on demand, the tested board. The test positions (too easy, IMHO) are no more included into the code but are present within an external standardized script file "endgame.scr". Moreover, you may try "fforum-1-19.scr", "fforum-20-39.scr", and "fforum-40-59.scr", that contain problems published in the magazine of the Federation Francaise d'Othello: FFORUM.</li><li>strict ansi-C89 conformance.</li><li>more modular code. I put into functions many things sparsed into the same function.</li><li>avoidance of global variables. Instead I organize them into structures passed to functions as pointers. Structure and function naming was carefully chosen to give an object-oriented-programming feeling.</li><li>to keep code clear but fast, I overuse macro inlining.</li><li>more and better algorithms used:<ul><li>fast (due to inlining and loop-unrolling) move generators.</li><li>Principal Variation Search (an enhanced alphabeta) [1].</li><li>move sorting according to the type of the squares.</li><li>move sorting to play fastest & stablest lines first.</li><li>move sorting based on approximated parity.</li><li>hash table [2] used to:<ul><li>anticipate cutoff at present level (if position is stored).</li><li>anticipate cutoff at the next level (enhanced transposition cutoff [3]).</li><li>replay known bestmove first.</li></ul></li></ul></li></ul><p>A faster endgame solver would need:<ul><li>a good evaluation function.</li><li>iterative deepening.</li><li>move sorting using shallow search.</li><li>"hard coding" of move generation, ...</li><li>64 bit board representation (bitboard) on 64 bit machine.</li><li>other heuristics: conspiracy number, ...</li></ul><p>but the following code is already much too long. Whatever, this solver is very fast for positions with less than 15 empties and still quiet good until 20 empties. The source has been kept in a single file to mimic other similar but older othello endgame solvers ; however, any clever implementation should split it in smaller files gathering the same logical content.<h2><a class="anchor" name="comp">Compilation</a></h2>I recommend to compile it with very aggressive optimizing settings, for example with the gnu compiler:<p>gcc -O3 -fomit-frame-pointer -funroll-loops -march=<your-CPU> <a class="el" href="solver_8c.html">solver.c</a> -o solver<p>A few #define at the top of the code may be changed to test/tune the effect of different parameters.<h2><a class="anchor" name="us">Usage</a></h2>Usage: solver [options] script_file<p>Options:<ul><li>-v verbose mode.</li><li>-vv very verbose mode.</li><li>-wdl search for win/draw/loss.</li><li>-wd search for win/(draw-loss).</li><li>-dl search for (win-draw)/loss.</li><li>-h set hash table size.</li></ul><p>Note: the best value for the '-h' option, i.e. the hash table size in bit number is approximately the number of empty squares of the position. Example: solver -v -h 20 fforum-20-39.scr<h2><a class="anchor" name="hist">History</a></h2><ul><li>version 1.0: 2001-10-31</li><li>version 1.1: 2001-12-19<ul><li>added stablest square based sorting</li><li>node counter as Macros</li><li>cosmetic enhancements.</li></ul></li><li>version 1.2: 2003-12-06<ul><li>added parity based sorting</li><li>plain alphabeta near the leaves</li><li>better comments & documentation (compatible with doxygen).</li><li>suppression of annoying statistic routines.</li><li>minor bug removals.</li><li>minor speed enhancements.</li><li>cosmetic enhancements.</li></ul></li><li>version 1.3: 2004-02-18<ul><li>major bug removals: parity missing initialisation.</li><li>minor bug removals.</li></ul></li><li>version 1.4: 2004-04-12<ul><li>major bug removal: wrong score returned from game-over positions.</li><li>minor speed enhancements: board update/restore unrolling.</li></ul></li></ul><h2><a class="anchor" name="ref">Reference</a></h2><ol><li>Marsland T.A. (1983) Relative efficiency of alpha-beta implementations. 8th IIJCAI. p 763-766.</li><li>Breuker D.M., Uiterwijk J.W.H.M. & van den Herik H.J. (1996) Replacement Schemes and Two-Level Tables. ICCA J 19-3 p 183-193.</li><li>Plaat A, Schaeffer J., Wirn P. & de Bruin A.(1996) Exploiting Graph Properties of Game Trees.</li></ol><h2><a class="anchor" name="thk">Thanks</a></h2><ul><li>to Christophe Lanuit, for the stablest sorting heuristics.</li><li>to Bruno Causse, who discovered an illogical bug when passing.</li><li>to Gunnar Anderson, who gave me the idea about the parity based on quadrant, as a fast sorting algorithm at shallow depth.</li><li>to Bj鰎n Lindberg, who reported a bug in version 1.3.</li><li>to people at GGS for their invaluable comments about this file. </li></ul><hr size="1"><address style="align: right;"><small>Generated on Mon Apr 12 19:31:51 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 + -