/* $Header: /export/home/richb/CVS-MASTER/reve/README,v 1.2 2005/10/13 17:13:47 richb Exp $ * * Copyright (C) 1990-2005 - Rich Burridge & Yves Gallot. * All rights reserved. */ Reve - README - October 2005. ----------------------------------------------------------------------- CONTENTS: 1. What is reve? 2. Getting started. 3. Strategy used by reve. 4. Acknowledgements. ----------------------------------------------------------------------- 1. What is reve? ---------------- This is version 3.0.X of reve (an othello game). This version works with GNOME/Gtk+. See the manual pages for a detailed description of the rules of Othello. Two humans can play each other (either locally or remotely), or you can play against the computer. Reve has various levels of difficulty. You can decide, whether you would like to set a time limit, or a search depth limit on the computer move. The levels of play can be rated approximately as follows: Instant: Beginner level. The search depth is one ply. Even at this level, beating reve is not trivial! 1 Minute/3 Minutes/5 Minutes: Intermediate levels. If you often beat reve at the 5 minute level, you have probably mastered the basics, and played a lot of games. Interested in playing real people in tournaments ? 10 Minutes: Advanced. Beating reve at this level is no piece of cake. 30 Minutes: (tournament level) More advanced. None of us has beaten reve at this level yet. If you do, you should seriously consider participating in your countries national championship. 60 Minutes: At this level reve looks further ahead than most humans can. If you win a game here, send us a transcript, because you have either found a serious bug in the algorithm, or your game deserves to be published. Set Search Depth: Setting the depth is an alternative to using a clock. With a clock, the time left decides, how many plys you search for each move. This usually varies by one or two plys, depending on where in the game you are, and towards the end, it is often worth calculating all the way and then storing some moves. By setting the depth you force the computer to search n plys, no matter where in the game you are. There is no clock. This means, that if the depth is set to something other than say '0', or whatever you want to use, the computer uses the depth, otherwise it will use the time. Or something like that. The point of this feature is game analysis. Especially towards the endgame you want to be able to let the computer run (for example, over night). Or if you know that you usually look 4 plys ahead, you want to play an opponent that consistently examines 6 plys. Or you are simply curious what the computer would have played had it searched a little further (like situations which can only be recognized properly in 6 plys etc. Note, that for each additional ply, the compute time increases by about a factor of 4. 2. Getting started. ------------------- See the file 'INSTALL' Introduced with reve v1.3, is the ability to play over the network. A network daemon is used for this, and in order for this to work correctly, a couple of files need to be edited (as super-user). Add the following line to /etc/services: reve 518/udp [Note if you are running NIS, then you might wish to add this to the /etc/services file on the NIS master server, then propogate the change]. Add the following line to /etc/inetd.conf: reve dgram udp wait root /usr/local/lib/in.reved in.reved [Note that /usr/local/games/in.reved needs to be replaced with the pathname of wherever you've installed the in.reved program]. The inetd daemon needs to either be restarted, or forced to re-read its' configuration file. The manual pages describe the rules of reve in detail. See the TODO file for the list of known problems and ideas for future enhancements. 3. Strategy used by reve. ------------------------- reve is a "classical Othello program", using state of the art othello strategy. It does not include Bayesian learning [Bill, 1989]. References : "A World-Championship-Level Othello Program", Paul S.Rosenbloom, Artificial Intelligence 19(1982), 279-320. "The Development of a World Class Othello Program", Kai-Fu Lee and Sanjoy Mahajan, Art. Int. 43(1990) 21-36. Turning Notes on, displays an evaluation for each computer move. This value is calculated as follows: An edgetable is pre-computed. A value is given to each border configuration. The average is 0, the mean value about 500. Then I fix c1 = 312 + 6 * movenumber c2 = | 50 + 2 * movenumber 1 <= movenumber <= 25 | 75 + movenumber 25 <= movenumber <= 60 c3 = 99 ( Iago implementation constants ) then eval = ( c1 * ( edgesnote + Xsquaresnote ) + c2 * currentmobility + c3 * Potentialmobility ) / 1000 mobility = 1000 * ( p - o ) / ( p + o + 2 ) where p is the evaluation for the player and o for the opponent p and o are about in the set [ -10, 10 ] In short, a positive number is good for the computer, and a negative numvber is good for the opponent. Here is a listing of a high level reve vs reve match. reve vs reve example. nt : note reve gives to the position. profmax : Depth reve looks forward. nbtotnodes : Accumulated number of final nodes evaluated. 1, , nt : 0, profmax : 1, nbtotnodes : 0 2, , nt : 5107, profmax : 9, nbtotnodes : 168236 3, , nt : 31284, profmax : 9, nbtotnodes : 459892 4, , nt : 7392, profmax : 9, nbtotnodes : 692337 5, , nt : -7392, profmax : 8, nbtotnodes : 843560 6, , nt : -29267, profmax : 8, nbtotnodes : 1305926 7, , nt : 8574, profmax : 8, nbtotnodes : 1461111 8, , nt : -38130, profmax : 8, nbtotnodes : 1630589 9, , nt : 7020, profmax : 8, nbtotnodes : 1882791 10, , nt : -36894, profmax : 8, nbtotnodes : 2136012 11, , nt : 4819, profmax : 8, nbtotnodes : 2684014 12, , nt : -4819, profmax : 7, nbtotnodes : 3331165 13, , nt : 34302, profmax : 7, nbtotnodes : 3539609 14, , nt : -5858, profmax : 7, nbtotnodes : 4229607 15, , nt : 5858, profmax : 6, nbtotnodes : 4390818 16, , nt : -11790, profmax : 7, nbtotnodes : 5137455 17, , nt : 11790, profmax : 6, nbtotnodes : 5418077 18, , nt : -46674, profmax : 6, nbtotnodes : 5570855 19, , nt : 15648, profmax : 6, nbtotnodes : 5766803 20, , nt : -15648, profmax : 5, nbtotnodes : 5825491 21, , nt : 52994, profmax : 7, nbtotnodes : 6365630 22, , nt : -52994, profmax : 6, nbtotnodes : 6556423 23, , nt : 5229, profmax : 6, nbtotnodes : 6656104 24, , nt : -3054, profmax : 7, nbtotnodes : 7221420 25, , nt : 3054, profmax : 6, nbtotnodes : 7313040 26, , nt : -845, profmax : 7, nbtotnodes : 7615130 27, , nt : 26592, profmax : 7, nbtotnodes : 8026020 28, , nt : -26592, profmax : 6, nbtotnodes : 8123951 29, , nt : 5691, profmax : 6, nbtotnodes : 8226483 30, , nt : -13265, profmax : 7, nbtotnodes : 8301302 31, , nt : 21196, profmax : 7, nbtotnodes : 8498532 32, , nt : -19960, profmax : 7, nbtotnodes : 8700743 33, , nt : 30104, profmax : 8, nbtotnodes : 9672532 34, , nt : -30104, profmax : 7, nbtotnodes : 9953691 35, , nt : 63346, profmax : 8, nbtotnodes : 10817345 36, , nt : -63346, profmax : 7, nbtotnodes : 11038102 37, , nt : 50472, profmax : 8, nbtotnodes : 11346042 38, , nt : -11415, profmax : 8, nbtotnodes : 11495189 39, , nt : 61958, profmax : 8, nbtotnodes : 11783153 40, , nt : 3313, profmax : 8, nbtotnodes : 12069521 41, , nt : -585518, profmax : 9, nbtotnodes : 12484782 42, , nt : -50483, profmax : 9, nbtotnodes : 12680889 43, , nt : -1469439, profmax : 9, nbtotnodes : 12791711 44, , nt : 2250360, profmax : 10, nbtotnodes : 13053695 45, , nt : 3, profmax : 16, nbtotnodes : 13217789 46, , nt : -3, profmax : 15, nbtotnodes : 13408870 47, , nt : 3, profmax : 14, nbtotnodes : 13471036 48, , nt : -3, profmax : 13, nbtotnodes : 13492740 49, , nt : 3, profmax : 12, nbtotnodes : 13500234 50, , nt : -3, profmax : 11, nbtotnodes : 13503151 51, , nt : 3, profmax : 10, nbtotnodes : 13503785 52, , nt : -3, profmax : 9, nbtotnodes : 13504016 53, , nt : 3, profmax : 8, nbtotnodes : 13504094 54, , nt : -3, profmax : 7, nbtotnodes : 13504146 55, , nt : 3, profmax : 6, nbtotnodes : 13504159 56, , nt : -3, profmax : 5, nbtotnodes : 13504167 57, , nt : 3, profmax : 4, nbtotnodes : 13504171 58, , nt : 0, profmax : 1, nbtotnodes : 13504171 59, , nt : 0, profmax : 1, nbtotnodes : 13504171 4. Acknowledgements. -------------------- See the 'AUTHORS' file. ------------------------------------------------------------------------ Suggestions for further improvement would be most welcome, plus bug reports and comments. Rich Burridge, rich.burridge@Sun.COM