### reve-1.4.0 README file

    /*  @(#)README 1.22 93/03/30
     *
     *  Copyright (C) 1990 - 1993 - Rich Burridge & Yves Gallot.
     *  All rights reserved.
     *
     *  Permission is granted to copy this source, for redistribution
     *  in source form only, provided the news headers in "substantially
     *  unaltered format" are retained, the introductory messages are not
     *  removed, and no monies are exchanged.
     *
     *  Permission is also granted to copy this source, without the
     *  news headers, for the purposes of making an executable copy by
     *  means of compilation, provided that such copy will not be used
     *  for the purposes of competition in any othello tournaments, without
     *  prior permission from the authors.
     *
     *  No responsibility is taken for any errors on inaccuracies inherent
     *  either to the comments or the code of this program, but if reported
     *  (see README file), then an attempt will be made to fix them.
     */

    Reve  -  README  -  March 1993.

    -----------------------------------------------------------------------
    CONTENTS:

    1. What is reve?
    2. Getting started.
    3. Strategy used by reve.
    4. Acknowledgements.
    -----------------------------------------------------------------------

    1. What is reve?
    ----------------

    This is version 1.4.0 of reve (an othello game). This version works under
    X11 and on dumb tty terminals.

    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.

    ----------

    There is a mailing list for people interested in reve. It is:

      reve@stard.Eng.Sun.COM

    To get added to the list, send a request to:

      reve-request@stard.Eng.Sun.COM

    Early patches are sent to the mailing list, plus active discussion on
    ideas for enhancements to reve, plus othello strategy in general.

    ----------

    The latest version of reve, recent patches plus an archive of the messages
    sent to the reve mailing list are available via anonymous ftp from:

       brolga.cc.uq.oz.au     (130.102.128.5)  [Queensland, Australia].

       ireq-robot.hydro.qc.ca (131.195.2.130)  [Quebec, Canada].

    Pick the site nearest to you, and please try to restrict your connections
    to outside 9:00am - 5:00pm local time during weekdays.

    ----------

    The address where people can get information about tournaments, Othello
    Quarterly, and "Othello Brief and Basic' is:

            Othello Quarterly
            c/o C.Hewlett
            920 Northgate Ave.
            Waynesboro, VA 22980
            USA

    2. Getting started.
    -------------------

    Initially there is no Makefile file present in the reve source directory.
    You will need to copy Makefile.dist to Makefile, then adjust accordingly.

    You need to specify one of the following two options to compile reve:

        make tty          - to make the dumb tty version.
        make x11          - to make the X11 version.

    This should then be followed by a "make install". You might need super-user
    permission to do this successfully. The "make install" will concatenate the
    two halves of the reve edge stability table together, before installing them.

    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, you firstly
    must have compiled reve with the HASNETWORK definition in the Makefile
    uncommented, then (as super-user) you need to edit a couple of files.

    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.

    The Makefile compilation details are setup to default to compiling the
    tty version of reve on a Sun4 running SunOS v4.x. Note that there are
    various compilation definitions that might need uncommenting if you are
    trying to compile and run it on any other machine or graphics environment
    or operating system.

    These are:

    EDGENAMEFILE - alternate location for the reve edge table.
    EDGENAME     - alternate location for the reve edge table.
    HASNETWORK   - uncomment to enable -opponent user@host networking code.
    HASPOLL      - uncomment if you have the poll(2) system call.
    HASREVEPROC  - uncomment to enable separate process for computer moves.
    HELPNAMEFILE - alternate location for the reve online help file.
    HELPNAME     - alternate location for the reve online help file.
    NOGETDTAB    - uncomment if you don't have getdtablesize().
    NOINDEX      - uncomment if you don't have the index() function.
    NOSELECT     - uncomment if your machine doesn't have the select() call.
    NO_USLEEP    - uncomment if you don't have the usleep(3) call.
    NO_TIMEVAL   - uncomment if you don't have a timeval struct definition.
    PROLOGUE     - alternate location for the trans PostScript prologue file.
    REVEPROCFILE - alternate location of the reve_proc program.
    REVEPROC     - alternate location of the reve_proc program.
    SELTYPE      - uncomment for old select(2) calls.
    SIGRET       - uncomment if your signal function expects an integer function.
    SYSV         - uncomment if you are running Unix System V.
    SVR4LIBS     - uncomment and set, if building under SVR4.
    X11INCDIR    - X11 only: location of the X11 #include files.
    X11LIBDIR    - X11 only: location of the X11 libraries.

    See the Makefile for a detailed description of each of these definitions.

    If you need to make other changes in order to get reve to compile and run
    on your system, please let us know the details (see email addresses below),
    and we will try to include them into a future version.

    See the TODO file for the list of known problems and ideas for future
    enhancements.

    Here are the settings for a variety of machines. Please send additional
    machine settings to the address below, to be included in this section.

       Type of machine:               Sun 4/65 (color - 1152x900x8).
       O/S release:                   Solaris 2.1(FCS).
       Version of reve:               X11 (Xlib).
       Uncommented Makefile settings:

         EDGENAMEFILE    = $(LIBDIR)/reve.edgetable
         EDGENAME        = -DEDGENAME=\"$(EDGENAMEFILE)\"
         HASNETWORK      = -DHASNETWORK
         HASPOLL         = -DHASPOLL
         HASREVEPROC     = -DHASREVEPROC
         HELPNAMEFILE    = $(LIBDIR)/reve.help
         HELPNAME        = -DHELPNAME=\"$(HELPNAMEFILE)\"
         NOGETDTAB       = -DNOGETDTAB
         NOINDEX         = -DNOINDEX
         NOSELECT        - -DNOSELECT
         REVEPROCFILE    = $(LIBDIR)/reve_proc
         REVEPROC        = -DREVEPROC=\"$(REVEPROCFILE)\"
         SYSV            = -DSYSV
         SVR4LIBS        = -lnsl -lsocket -lgen
         X11INCDIR       = -I$(OPENWINHOME)/include
         X11LIBDIR       = -L$(OPENWINHOME)/lib

       Additional notes:           Uses OpenWindows v3.2 libraries.

       ---------

       Type of machine:               HP Series 9000, model 3[67]0
       O/S release:                   HP-UX release 7.0
       Version of reve:               X11 (Xlib), MIT X11R4 source
       Imakefile settings:

         NO_USLEEP       = -DNO_USLEEP
         NOINDEX         = -DNOINDEX
         USRLIBDIR       = /usr/games/lib

       ---------

       Type of machine:               HP 9000/370.
       O/S release:                   HP-UX 7.0.
       Version of reve:               X11R3.
       Uncommented Makefile configuration settings:

         NOGETDTAB       = -DNOGETDTAB
         NOINDEX         = -DNOINDEX
         NO_USLEEP       = -DNO_USLEEP
         X11R3           = -DX11R3

       ---------

       Type of machine:               DEC 5000/200 (color - 1024x864x8)
                                      DEC 3100     (mono - 1024x864x1)
       O/S release:                   Ultrix 4.1
                                      Ultrix 4.0
       Version of reve:               X11 (Xlib) (release 4)
       Uncommented Makefile settings:

         EDGENAMEFILE    = $(LIBDIR)/reve.edgetable
         EDGENAME        = -DEDGENAME=\"$(EDGENAMEFILE)\"
         HELPNAMEFILE    = $(LIBDIR)/reve.help
         HELPNAME        = -DHELPNAME=\"$(HELPNAMEFILE)\"
         REVEPROCFILE    = $(LIBDIR)/reve_proc
         REVEPROC        = -DREVEPROC=\"$(REVEPROCFILE)\"
         X11INCDIR       = -I$(OPENWINHOME)/include
         X11LIBDIR       = -L$(OPENWINHOME)/lib

    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, <C-4>, nt : 0,        profmax : 1,  nbtotnodes : 0
     2, <E-3>, nt : 5107,     profmax : 9,  nbtotnodes : 168236
     3, <F-4>, nt : 31284,    profmax : 9,  nbtotnodes : 459892
     4, <C-5>, nt : 7392,     profmax : 9,  nbtotnodes : 692337
     5, <D-6>, nt : -7392,    profmax : 8,  nbtotnodes : 843560
     6, <C-3>, nt : -29267,   profmax : 8,  nbtotnodes : 1305926
     7, <C-6>, nt : 8574,     profmax : 8,  nbtotnodes : 1461111
     8, <F-5>, nt : -38130,   profmax : 8,  nbtotnodes : 1630589
     9, <E-6>, nt : 7020,     profmax : 8,  nbtotnodes : 1882791
    10, <D-3>, nt : -36894,   profmax : 8,  nbtotnodes : 2136012
    11, <F-3>, nt : 4819,     profmax : 8,  nbtotnodes : 2684014
    12, <F-6>, nt : -4819,    profmax : 7,  nbtotnodes : 3331165
    13, <E-2>, nt : 34302,    profmax : 7,  nbtotnodes : 3539609
    14, <G-4>, nt : -5858,    profmax : 7,  nbtotnodes : 4229607
    15, <G-3>, nt : 5858,     profmax : 6,  nbtotnodes : 4390818
    16, <E-1>, nt : -11790,   profmax : 7,  nbtotnodes : 5137455
    17, <D-2>, nt : 11790,    profmax : 6,  nbtotnodes : 5418077
    18, <F-2>, nt : -46674,   profmax : 6,  nbtotnodes : 5570855
    19, <F-1>, nt : 15648,    profmax : 6,  nbtotnodes : 5766803
    20, <C-1>, nt : -15648,   profmax : 5,  nbtotnodes : 5825491
    21, <D-1>, nt : 52994,    profmax : 7,  nbtotnodes : 6365630
    22, <G-1>, nt : -52994,   profmax : 6,  nbtotnodes : 6556423
    23, <H-5>, nt : 5229,     profmax : 6,  nbtotnodes : 6656104
    24, <H-4>, nt : -3054,    profmax : 7,  nbtotnodes : 7221420
    25, <G-5>, nt : 3054,     profmax : 6,  nbtotnodes : 7313040
    26, <H-6>, nt : -845,     profmax : 7,  nbtotnodes : 7615130
    27, <H-3>, nt : 26592,    profmax : 7,  nbtotnodes : 8026020
    28, <C-2>, nt : -26592,   profmax : 6,  nbtotnodes : 8123951
    29, <H-7>, nt : 5691,     profmax : 6,  nbtotnodes : 8226483
    30, <G-6>, nt : -13265,   profmax : 7,  nbtotnodes : 8301302
    31, <E-7>, nt : 21196,    profmax : 7,  nbtotnodes : 8498532
    32, <D-7>, nt : -19960,   profmax : 7,  nbtotnodes : 8700743
    33, <C-8>, nt : 30104,    profmax : 8,  nbtotnodes : 9672532
    34, <E-8>, nt : -30104,   profmax : 7,  nbtotnodes : 9953691
    35, <D-8>, nt : 63346,    profmax : 8,  nbtotnodes : 10817345
    36, <B-8>, nt : -63346,   profmax : 7,  nbtotnodes : 11038102
    37, <F-7>, nt : 50472,    profmax : 8,  nbtotnodes : 11346042
    38, <C-7>, nt : -11415,   profmax : 8,  nbtotnodes : 11495189
    39, <B-6>, nt : 61958,    profmax : 8,  nbtotnodes : 11783153
    40, <A-5>, nt : 3313,     profmax : 8,  nbtotnodes : 12069521
    41, <B-3>, nt : -585518,  profmax : 9,  nbtotnodes : 12484782
    42, <B-5>, nt : -50483,   profmax : 9,  nbtotnodes : 12680889
    43, <A-6>, nt : -1469439, profmax : 9,  nbtotnodes : 12791711
    44, <A-4>, nt : 2250360,  profmax : 10, nbtotnodes : 13053695
    45, <B-4>, nt : 3,        profmax : 16, nbtotnodes : 13217789
    46, <F-8>, nt : -3,       profmax : 15, nbtotnodes : 13408870
    47, <B-2>, nt : 3,        profmax : 14, nbtotnodes : 13471036
    48, <A-7>, nt : -3,       profmax : 13, nbtotnodes : 13492740
    49, <G-7>, nt : 3,        profmax : 12, nbtotnodes : 13500234
    50, <B-7>, nt : -3,       profmax : 11, nbtotnodes : 13503151
    51, <B-1>, nt : 3,        profmax : 10, nbtotnodes : 13503785
    52, <A-1>, nt : -3,       profmax : 9,  nbtotnodes : 13504016
    53, <A-8>, nt : 3,        profmax : 8,  nbtotnodes : 13504094
    54, <A-2>, nt : -3,       profmax : 7,  nbtotnodes : 13504146
    55, <A-3>, nt : 3,        profmax : 6,  nbtotnodes : 13504159
    56, <H-8>, nt : -3,       profmax : 5,  nbtotnodes : 13504167
    57, <G-8>, nt : 3,        profmax : 4,  nbtotnodes : 13504171
    58, <H-2>, nt : 0,        profmax : 1,  nbtotnodes : 13504171
    59, <G-2>, nt : 0,        profmax : 1,  nbtotnodes : 13504171

    4. Acknowledgements.
    --------------------

    The previous version of this program was posted to comp.sources.games
    under the name othello2. That version was a rework of the SunView
    graphics front-end from Ed Falk, Sun Microsystems, CA. It contained
    computer strategy and remarks code from Chris Miller.

    The graphics code was abstracted, and graphics drivers were added for
    X11 (Xlib), the XView toolkit, and a dumb tty version.

    This version has virtually the same graphical interface. The remarks code
    has been removed, and the computer strategy is written by Yves Gallot.

    Thanks to Valerie Haecky for the code for printing reve game boards to
    PostScript printers.

    Thanks to the University of California (Berkeley) for making the talk and
    in.talkd programs freely distributable, and therefore providing the basis
    for the networked version of reve.

    Thanks also go to the following for various bug reports, fixes and
    suggestions for improvement:

      Thomas K. Bischoff,
      Martin Boyer,
      Brett K. Carver,
      Martin Chudley,
      Robert Cohen,
      Scott W. Danielson,
      John Eldredge,
      John Eras,
      Tom Friedel,
      Gordon C. Galligher,
      Krishnamurthy Ganesan,
      Arnold Gill,
      Michael Glad,
      Jacob E. Goodman,
      Valerie Haecky,
      Olaf Heimburger,
      Soren Hein,
      Kjetil Torgrim Homme,
      Peter Johansson,
      Eric R. Jorgensen,
      Norbert Jung,
      Jonathan I. Kamens,
      Gary D. Kline,
      Hugues Leroy,
      Richard K. Lloyd,
      Daniel Edward Lovinger,
      Linton Miller,
      Steve Misrack,
      Keith Moore,
      Alfred Nathaniel,
      D. Hugh Redelmeier,
      John Rosauer,
      Heather Rose,
      Mike Stump,
      W. Mat Waites,
      Mike Wexler,
      Rod Whitby,
      Daniel Yang,
      Andreas Zins.

    ------------------------------------------------------------------------

    Suggestions for furthur improvement would be most welcome, plus bugs,
    comments and flames.

    Rich Burridge           richb@Eng.Sun.COM
    Yves Gallot             (no net address at present).