Crawly Crypt Collection 1/crawlyvol1.bin/games/stello11/doc/stello.txt

Text File | 1994-07-04 | 24KB | 482 lines

Hello everybody.

Here  is version 1.10 of my Othello/Reversi game Stello  (ST-Othello  or
Super-Othello or whatever you like best).

Files:
  README            (short description of stello)
  STELLO.PRG        (Othello for 68000)
  STELLO30.PRG      (Othello for 68030)
  STEENG.RSC        (english rsc.)
  STEGER.GER        (german rsc.)
  STEDAN.RSC        (danish rsc.)
  BLACK.LIB         (black opening lib)
  WHITE.LIB         (white opening lib)
  DISCS\*.BIN       (different discs)
  BOARD\COL2\*.IMG  (pictures for 2 colors)
  BOARD\COL4\*.IMG  (pictures for 4 colors)
  BOARD\COL16\*.IMG (pictures for 16 colors)
  DOC\REGISTER.TXT  (Send this to me please)
  DOC\STELLO.TXT    (you are reading it)
  DOC\WHATSNEW      (what is new in this version)
  GAM\BADPOS.GAM    (set response time to infinity and wait)
  GAM\PLY22.GAM                      do
  GAM\END.GAM                        do
  GAM\WOW64.GAM                      do

History:
  5 years ago.

  Beeing very interested in game theory,  and the game of Othello, i had
  (in   vain)  for  a  long  time  searched  for  a  good   and   strong
  implementation  of  this  game  for  the  Atari  computer  line.   Not
  succeding i said to myself,  why not write one myself. Had i known how
  difficult  and  timeconsuming it would be,  i would probably  not  had
  started.  Anyway i bought a book called advanced Pascal in which there
  was a tiny othello game.  It was quickly adopted to my atari computer,
  and  of cause then i played some matches against it.  What a  bommer!!
  It  played so bad that i could not belive it.  Looking at  the  source
  code i had to admit that i really didn't understand what was going on.
  I needed to learn about the fundamentals before i could make a  better
  program.  I then began to study the theory behind game  playing,  such
  as  the  alfa/beta minimax algorithm and many other  related  objects.
  During the next two years i developed the fundamental algorithms,  and
  implemented  it  in  Pascal,  and where it was  needed  for  speed  in
  assembler.  Writing in Prospero Pascal was not anything i would  whish
  for  my worst enemies.  After two years of work (in my spare  time)  i
  had  a  working version of a Othello game which had  a  primitive  Gem
  interface.  The searching algorithms were quite good,  but the "brain"
  was  not working so good.  Once in a while it would loose  control  of
  the  game due to something that i didn't quite  understand.  You  must
  understand,  that while i tried to make my program better,  i also had
  to  develop my own understanding of the game.  I can clearly say  that
  it had made me a much better Othello player to write this program.  In
  these  two  years  i concentrated on learning the  theory  behind  the
  searching  algoritmes  and the different techniques  to  optimize  the
  minimax algorithme.  (There is still room for improvement, for example
  it  was  just  during the last three months  that  i  implemented  the
  zerowidth  modifikation to minimax,  and i still need  to  investigate
  the hash table techniques).  What i needed was a better  understanding
  of the game itself.  Something then happend which were the major force
  behind  the increase in playing strength during the last three  years.
  I  read an article of Paul Rosenblaum who had made a  Othello  program
  of  remarkable strength.  In this article he made a very good  analyse
  of  the  game itself,  and made some suggestions about  the  ways  one
  could  implement  a  evaluation function which  could  understand  the
  features  of the game.  After studing his article i began  implmenting
  his  ideas  and  improving upon them.  Eureka,  my  program  got  much
  stronger.  Programming in pascal was not fun any more,  so i  switched
  to  Turbo  C,  and later to Pure C.  What a joy programming  now  was,
  compiling  the  program  was  now a  matter  of  seconds  compared  to
  minutes.  The  last two years whent by,  and i improved the  interface
  beyond  recognation  and  optimized  the shit  out  of  the  searching
  algorithms.  The brain got a facelift,  which means that i implemented
  some  ideas  of  my  own,  that made a much  stronger  player  of  the
  program.  I  did  this  by making the  program  avoid  the  inherently
  unstable evaluations which most othello programs do,  and that  really
  made  it come up amongst the best programs in the world.  So now  here
  it  is.  After  five  years  of  development  i  will  release  it  as
  Shareware.  i  really hope thet you will enyoy it,  and that you  will
  gratify a hardworking programmer with his modest shareware fee.

Tecnicals:

  The  search  is based on the alfa/beta - minimax  algorithm.  It  uses
  several   heuristics  to  improve  the  search   strategi.   Iterative
  deepening,  response  killer table,  saving the game tree  (all  moves
  are saved, as long as there is memory, the program reserves all memery
  except 10%,  so if you have 4 megabyte it could take 3.6 megabyte  for
  the  tree  of  moves alone) and sorting  the  moves  dynamically  when
  everything  else fails.  This reduces the brancing factor  to  between
  3.0  to 4.5.  It really depends on the position.  In the end game  the
  banching factor is between 1.8 to 2.4.

  The  evaluation is based on several independent  components,  such  as
  mobility,  stability and corner and edge disks. The program is capable
  of  solving  most  endgame positions when there is  only  16-14  moves
  left  (depending  on  computer and position,  some  positions  can  be
  solved  when  20 moves are missing).  It does so by using  the  highly
  optimized  search algoritms,  which in the end game is  improved  with
  the  recursive  zerowidth alfa/beta-minimax algorithm.  On  a  TT  the
  endgame  routine searches the game tree,  with 15000-20000 nodes  per.
  second.  A  TT has a clock of 32 MH.  A instruction neads at  least  2
  clock  cycles  to  complete.   This  gives  32000000/(20000*2)  =  800
  instructions  per  node.  For every node the program has to  sort  the
  moves,  make at least one move and evaluate the move. Then call itself
  recursively to do so for the rest of the nodes.  Doing so in just  800
  instructions  is,  in my own opinion,  rather good.  The speed of  the
  normal  search  is  1500-4500 nodes pr  second.  You  can  not  really
  compare  this  with other programs,  as it depends on  the  evaluation
  function.  My evaluation function, dosen't just evaluate one node, but
  investigates  the  possible responds and counterresponds  to  be  sure
  that  the position is approximately stable,  wich really improves  the
  playing strenght..

Playing strength:

  To test how strong my program was,  i made a little testmatch  against
  the program Thor.  Thor is one of the best Othollo playing programs in
  the  world,  having  participated in several  turnements,  and  usally
  ending  amongst  the top programs.  I made the two  programs  play  10
  different positions against each other,  as both black and white. This
  is 20 games in all.  The play level was turnement,  which means 30 min
  for  one game.  The results follow.

             Stello        Thor         Thor         Stello
           | Black  | p |  White | p |  Black | p |  White | p |
  ---------------------------------------------------------------
  game  1. |   41   | 1 |   23   | 0 |   44   | 1 |   20   | 0 |
  game  2. |   30   | 0 |   33   | 1 |    7   | 0 |   57   | 1 |
  game  3. |   54   | 1 |   10   | 0 |   14   | 0 |   50   | 1 |
  game  4. |   53   | 1 |   11   | 0 |   15   | 0 |   49   | 1 |
  game  5. |   58   | 1 |    6   | 0 |   27   | 0 |   37   | 1 |
  game  6. |   22   | 0 |   42   | 1 |   19   | 0 |   45   | 1 |
  game  7. |   38   | 1 |   26   | 0 |   19   | 0 |   45   | 1 |
  game  8. |   25   | 0 |   39   | 1 |   23   | 0 |   41   | 1 |
  game  9. |   29   | 0 |   35   | 1 |   24   | 0 |   40   | 1 |
  game 10. |   37   | 1 |   27   | 0 |   22   | 0 |   42   | 1 |
  --------------------------------------------------------------
  Total:   |  38.7  | 6 |  25.2  | 4 |  21.4  | 1 |  42.6  | 9 |

             Stello         Thor
             Discs     p    Discs   P
  Total:   |  40.7  | 15 |  23.3  | 5 |
  -------------------------------------

  The  theory behind Othello suggests that it is better to  have  white.
  This means that one would suspect the white side to win.  If you  look
  at  the results you will see,  that my program as white wins  9-1  !!.
  But  even as black it manages to win by 6-4.  All in all a victory  by
  15-5.  I  must emphase that this is by no means a bashing of  Thor.  I
  really belive that it is a excelent Othello player,  and i admire  the
  work  that has been put in that program.  One could probobly  find  10
  other  positions where the result would be different,  i can only  say
  that  these positions were the first 10 to be reached by  playing  the
  two programs against each other.  My conclusions are, in retrospekt of
  the  results,  you  can say that my program playes Othello  at  Master
  level.

-----------Update: Match against Thor v 3.36. (july 1994)---------------

  The  last  match  was against thor v 3.33,  and in  the  meantime  the
  authors behind Thor have improved the program.  As far as i can see it
  searches somewhat faster,  and it dosen't anymore occasionally make  a
  bad move.  Furthermore the endgameroutine is 2-3 times faster.  I made
  the  same match with the same 10 different openings.  The  new  result
  was.

             Stello      Thor 3.36    Thor 3.36     Stello
           | Black  | p |  White | p |  Black | p |  White | p |
  ---------------------------------------------------------------
  game  1. |   52   | 1 |   12   | 0 |   32   |1/2|   32   |1/2|
  game  2. |   46   | 1 |   18   | 0 |   32   |1/2|   32   |1/2|
  game  3. |   24   | 0 |   40   | 1 |   21   | 0 |   43   | 1 |
  game  4. |   55   | 1 |    9   | 0 |   30   | 0 |   34   | 1 |
  game  5. |   27   | 0 |   37   | 1 |   23   | 0 |   41   | 1 |
  game  6. |   32   |1/2|   32   |1/2|   19   | 0 |   45   | 1 |
  game  7. |   26   | 0 |   38   | 1 |   21   | 0 |   43   | 1 |
  game  8. |   35   | 1 |   29   | 0 |   52   | 1 |   12   | 0 |
  game  9. |   32   |1/2|   32   |1/2|   31   | 0 |   33   | 1 |
  game 10. |   39   | 1 |   25   | 0 |   28   | 0 |   36   | 1 |
  --------------------------------------------------------------
  Total:   |  36.8  | 6 |  27.2  | 4 |  28.9  | 2 |  35.1  | 8 |


             Stello         Thor 3.36
             Discs     p    Discs   P
  Total:   |  36.0  | 14 |  28.0  | 6 |

  As we can see,  the outcome in points is almost identical to the  last
  testmatch.  Stello wins 14-6.  If we analyse the games in more  detail
  we can see that it now is a much closer match.  The disc  differential
  now is 8 discs,  where it in the last match was 17 discs.  We can  see
  that Thor really has improved.  Maybe i should start implementing some
  of those new ideas that i have been thinking about.

-----------------------------Update end---------------------------------

  One  of the more facinating things about Stello,  and  gameplaying  in
  general,  is  that  i  can't  beat  it  anymore.  I  have  a  complete
  understanding  of why it makes its moves,  but i don't have  the  same
  memory  and processing power as the computer.  In the game of  Othello
  the  computer  has  a bigger advantage than for example  in  chess  or
  chekers,  as the positions change so quickly. In a sense you could say
  that  the computer have outmastered me.  Then again i can always  pull
  the plug. 8-).

Interface:

  The  interface is completely GEM controlled,  so that the game  should
  run  in all graphic resolutions (x resolution must be at  least  640),
  and  on all Atari computers.  It uses some of the features in the  new
  multitos,  such  as iconification of the windows (AES 4.1),  3d  look,
  buttom  windows etc.  It is possible to load a bacground  picture,  if
  the picture is in GEM-XIMG format.  If you are in 16 color  resolution
  it  must  be a 16 color picture of size  256x256.  Some  pictures  are
  included, for 2,4 and 16 color modes. It also supports WINX.

---------------------update july 1994 stello v1.1-----------------------

  By popular demand (my own 8-) i have put the dialogs in windows.  This
  means,  that the program dosent hog the computer when showing dialogs.
  A  side  effect  is  that  under  normal  tos  it  almost  feels  like
  multitasking,  as the computer continues thinking while you are  using
  the  dialogs.  You  can now have 3D activator  and  indicator  buttons
  under normal tos, 3D checkboxes and niceline menus.

-------------------------------update end-------------------------------

  Multitasking:

  The  first  versions of my program had the normal structure of  a  gem
  program.  A event_multi loop, to interact with the user, and then when
  you  made a move the computer would begin thinking and  the  interface
  would  freeze  until the computer had  finished  claculating.  It  was
  rather  irritating to see the clock stop working,  not beeing able  to
  move the windows or do anything else while the computer was  thinking.
  I  had  to develop a technique to allow a sort  of  quasimultitasking.
  What  i did was to implement corutines.  I started by  implementing  a
  interrupt  routine  (timer  A)  to update the  clock  and  a  internal
  variable,  that  meant i didn' need to make a systemcall 1000 times  a
  second  to check the clock.  Of cause i could have made  a  even_multi
  call  in my recursive minimax routine,  but i didn't like to  mess  up
  the  nice  structure of my program by making interface  calls  in  the
  brain  of the program.  I was programming the interface and  brain  as
  two independent units.  Later on when i used the features of  multitos
  it turned out,  that it was much easier to implement multitasking as i
  already  had  programmed  the interface to look at  the  brain  as  an
  independent task.  In the minimax routine i check if the timeslice for
  the  brain  has  been  used,  if  so i do  a  context  switch  to  the
  event_multi  loop,  which checks if there are any messages.  If  there
  are it does the appropriate thing,  and then turns control over to the
  brain again.  In practice it seems just as multitasking. The interface
  and  the  brain  has  their own  stack  and  communicates  via  global
  variables.  Under Multitos the interface and the "brain" is running as
  two  independent  tasks.  This means,  that you cannot  interrupt  the
  brain,  by  for example showing a dialog in another program.  It  also
  means,  that you can move the windows,  update the clock, and anything
  else  the  interface will allow you.  Isn't  multitasking  wonderfull.
  Under multitos the brain and interface communicate via signals and  by
  sending messages via appl_write.  That is the reason,  that the  brain
  is  shown in the menu under multitos.  I had to make the brain  a  Gem
  application,  as  the interface is wating in a event_multi loop for  a
  message,  and  the  only  nice  way to tell  it  that  the  brain  has
  finished,  was to send it a message via appl_write.  I could have made
  a  global  variable,  and made a event_multi call with a  small  timer
  value,  but  my goal was a interface that didn't use  any  unnecessary
  time under multitos.  The program supports WINX by using wind_update's
  check and set mode.  This means,  that the interface doesn't stop when
  it tries to update the clock or the analyse window,  and someone  else
  has  control over the update semafor,  but just turns control over  to
  the  brain.  This solution isn't perfect,  but much nicer than to  see
  everything freeze.  The perfect solution is to use multitos. This must
  be  one of the first programs on the atari computers to make a  really
  good use of multitasking.  If you have a shell, and the program "top",
  you can follow how the program multitasks.


Help for interface:

Menu "File"

  New game:
    Starts a new game.

  Load game:
    Loads a previosly saved game.

  Save game:
    Saves current game.

  Stop:
    Stop playing.

Menu "Game"

  Computer/human:
    Play against the computer.

  Computer/computer
    Computer playes itself.

  Human/human
    Play against another person.

Menu "Level"

  Plyes ahead:
    Computer thinks until a given search depht limit is reached.

  Time for one move:
    Computer  thinks until a given time limit is reached.  It  tries  to
    make inteligent use of the time,  so it will somtimes respond faster
    when it sees, that it cannot make a deeper search within the current
    timelimit.

  Time for one game:
    Set  the time for one game,  and the computer makes the best use  of
    this  time.  It means that it uses more time at stages in  the  game
    where  it is importent,  this is the level which should be  used  to
    play a normal game, the others are basicly for analyses.

  Openings lib:
    Turns on/of the openings lib.

Menu "Move"

  Forward:
    Move forvard one position in game:

  Back:
    Move one position back in game.

  Move now:
    Interrupt thinking, and move now.

  Change sides:
    Change sides.

  Next best:
    Make next best move.

  Hint:
    Suggest a move.

Meny "Options"

  Show move list:
    Show the moves, number of discs and clock in a window.

  Show analysis:
    Show  some information concerning the game.  Value is  the  internal
    representation of how good the computer thinks it is doing. Positive
    means good for the computer.  When it is possible to completly solve
    the game,  you will see this value as either "XX e" or "XX p"  where
    "XX"  is the number of disks it nows it will (when both sides  plays
    perfect) win or lose by.  The "e" means estimated and the "p"  means
    precisely.  The  endgamesearch is split in two,  first it  tries  to
    find  a winning line,  and if such a line exists,  it then tries  to
    find  the line which wins by the largest margin.  Nodes is how  many
    nodes is visited in the tree.  Evaluations is how many nodes that is
    evaluated.  Time  is  in 1/100 sek.  "d" is the  current  depth  and
    current move. Move shows the current best line of moves.

  Reversi setup:
    Make your own position.  Dobble click to empty the board. Left mouse
    button  puts  a black disc on the board,  right mouse puts  a  white
    disc  on board,  and pressing Control and left mouse  button  clears
    the board where the mouse currently is.

  Zero clock:
    Reset clock.

  Print moves:
    Print a list of the currently played moves.

  Load picture:
    Loads  a bacground picture.  The picture format is any ximg  picture
    of  size  256x256  with the same number of  colors  as  the  current
    resolution. (St medium pics must be 256x128).

  Configuration:
    Here you can set some specific features,  such as the border of  the
    disc.  With  a  dark bacground picture it is good to  have  a  white
    border around the black discs.

    Show  possible moves.  When this option is set,  the  mouse  changes
    form  whenever it crosses a position where it is possible  to  move.
    When  no moves are possible it changes to a "P" for  pass.  Continue
    playing   by  pressing  the  left  mouse  button  with  the   cursor
    positioned  over  the board.  Also pressing the right  mouse  button
    when  the cursor is placed over the board,  displayes  all  possible
    moves."Fast  move" sets whether or not there are a flashing disc  to
    indicate  where  there  was  moved.   Animation  turns  on/off  disc
    animation.  Sound turns on/off the sound.  Background picture  turns
    on/off the background picture.  Notation determinates which notation
    is  used.  3D  buttons  switches between  the  old  interface  style
    buttons,  and  the  new  3D buttons.  (Doesn't show  on  Falcon  and
    Multitos)

  Language:
    Switch  the language.  Currently supported are English,  German  and
    Danish.

  Save configuration:
    Saves   the  current   configuration.   Windows   positions,   size,
    backgroundpicture are saved.  The settings under "configuration" are
    saved,  and  level  of play is saved.  Different  configurations  is
    saved  for different screen resolutions,  which means you  can  save
    one  configuration  for  mono  and one  for  VGA  ect.  The  program
    determinates at startup which one it must use.

Future:

  Current plans for Stello 2.0 is

    - support drag an drop protocol
    - load a game by clicking it
    - implement the zerowidth alfa-beta mini-max algorithm for the
      normal search (already implemented in the endgame search)
    - implement hash tabels if it gives anything
    - improving the brain (it can always get better can't it 8-)
    - better output for the printer
    - support for transcripted games
    - whatever you suggests

  The  implementation of these improvements really is in your  hands,  i
  must  have a satisfactory response before i can find the time to  make
  them. A man must earn a living ;-). If there is enough of responses, i
  would  even  consider making other strategic games  such  as  chekers,
  five in a row or what you most would like, see REGISTER.TXT

Thanks and gretting too:

    Klaus Pedersen for beta testing.
    The players on the socker team.
    Helle Demant, Søren Warberg, Lone Poulsen and
    Henrik Jensen for moral support.
    Paul Rosenblaum for his excellent articel about Iago.
    Sylvain Quin, Bruno de la Boisserie and Jean-Jacques Michel
    for producing the excellent program Thor.
    All my friends in Veflinge.
    The twins. (Nobody can party like them.)
    My parents and my brother.

Shareware:

  STELLO  is  Shareware.  The program may only  be  distributed  without
  charge.  For example,  commercial public domain libraries,  magazines,
  publishing  companies  and software companies may only  spread  Stello
  with my prior written permission.  Stello may be uploaded to BBSs that
  do  not charge for downloads.  Both the program and the  documentation
  must  remain  together and unchanged.  The stello CFG  file  must  NOT
  under  any  circumstances  be distributed as  the  registered  version
  contains your personal key details.  It is very easy to register, just
  fill the formular in the file REGISTER.TXT,  and send it to me. I will
  then  send you a key,  which will free you from the annoying  register
  dialog that keeps popping up.

Bugs/comments:

  If you find a bug, or have any suggestions concerning the program, you
  are welcome to send me a letter.

  My adress is as follows:

          Claus J. Pedersen
          Vædevej 42
          5462 Morud
          Denmark

  Or you can reach me on internet by E-mail at

          [e-mail]

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

                Hate has a reason for everything
                But love is unreasonable.

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