home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / fish / 811-820 / ff811 / whitelion / whitelion.doc < prev    next >
Text File  |  1993-02-14  |  13KB  |  231 lines
  1. -----------------------------------------------------------------------------
  2. ----     WhiteLion 1.2     --------------------------------------------------
  3. -----------------------------------------------------------------------------
  4. ---- Program Documentation --------------------------------------------------
  5. -----------------------------------------------------------------------------
  6.  
  7. -----------------------------------------------------------------------------
  8. ---- getting started --------------------------------------------------------
  9. -----------------------------------------------------------------------------
  10.  
  11. To play, just doubleclick on the WhiteLion_FD_gb icon, and on the [?] gadget
  12. in the program window. It should work fine on all Amigas with Kickstart 1.2
  13. or higher. Try a game and don't be disappointed if you lose. You'll soon get
  14. used to it... :^>
  15. On Hires Laced Screens, you need the Topaz 11 Font.
  16. Insert your Workbench Fonts disk into DF0:, open a Shell and type:
  17.   Copy DF0:Fonts/Topaz#? SYS:Fonts ALL
  18.  
  19. -----------------------------------------------------------------------------
  20. ---- for german-only speaking users                 -------------------------
  21. ---- (there might still be some, you never know...) -------------------------
  22. -----------------------------------------------------------------------------
  23.  
  24. Zum Start klicken Sie bitte zweimal schnell auf das WhiteLion_FD_d Icon, und
  25. im Programm auf das [?] Gadget.
  26. Sie benötigen den Topaz 11 Font, um auf Hires Laced Screens zu spielen.
  27. Legen Sie die Workbench Fonts Diskette in DF0:, starten Sie die Shell und
  28. geben Sie ein:
  29.   Copy DF0:Fonts/Topaz#? SYS:Fonts ALL
  30.  
  31. -----------------------------------------------------------------------------
  32. ---- background information -------------------------------------------------
  33. -----------------------------------------------------------------------------
  34.  
  35. Always being fascinated by artificial intelligence, I started to write this
  36. program in 1991, when I still worked in an old people's home in Hanover.
  37. In Germany you have to fulfil a social civil service if you don't go to the
  38. german army.
  39. My first idea was to use a very quick, move-oriented evaluation of the game
  40. positions to let the program calculate many moves ahead. But the result was
  41. a quite weak, silly playing game which looked four or five moves ahead,
  42. evaluated the resulting positions wrong and tried to reach one of the wrong-
  43. valued new positions.
  44.  
  45. So I implemented the standard AI alpha-beta pruning algorithm and a position-
  46. oriented evaluation after a while.
  47. In 1992 I found a very useful article by Paul S. Rosenbloom in the Paderborn
  48. University library called 'IAGO - A World Championship Level Othello
  49. Program', published in 'Artificial Intelligence, vol. 19 (1982)'.
  50. This is where I got most of the Minimum Disk Strategy and the Mobility
  51. measurement inspirations from. I then decided to write my own functions for
  52. the border and inner-room evaluation.
  53. The idea of AI games is the following:
  54. Let's assume the computer has to move and there are 12 possible moves in this
  55. position. He executes the possible moves internally, i.e. builds up all 12
  56. new board positions, and saves them. Then he calls an evalutation function
  57. for all saved boards, and the one which gets the highest number is chosen.
  58. If you want the computer to think ahead, let it compute the 12 following
  59. boards ('sons') first, and then for each of the 12 sons compute all following
  60. boards ('grandsons') again. Then evaluate the grandsons, and choose that one
  61. of your sons for play which gives you the best value if the human finds the
  62. best grandson afterwards.
  63. For three moves ahead, compute all grandgrandsons...
  64. This method is called MINIMAX.
  65. In fact, you needn't compute all of them. There is a heuristic search
  66. algorithm called 'alpha-beta pruning' which will give you exactly the same
  67. (MINIMAX) result, but will create less boards:
  68. If the average number of moves per board position is called 'b', and the
  69. search depth 'd', it will only use ca. 2*b^[d/2] instead of b^d moves.
  70.  
  71. The FD version provides different strategies on the 4 available levels:
  72. Level 0 will play pure Maximum Disk strategy, i.e. it will count the disks
  73. and return the difference as an evaluation result. But the search depth is
  74. three moves to make it not too easy. However, you'll soon find out that the
  75. computer plays a bit silly, and I'm sure you'll figure a simple strategy to
  76. beat it after some games yourself.
  77. Level 1 adds a border evaluation and changes the count evaluation as the game
  78. proceeds. The search depth is 1.
  79. Level 2 also uses border and count, but adds an inner-room evaluation only in
  80. the opening game, to make it more difficult for you to get to the border. It
  81. also adds a mobility measure evaluation which counts the moves you have, the
  82. moves the computer would be able to make and the moves both of you have. It
  83. returns a number which shows the mobility of each player. The search depth is
  84. 1 again.
  85. Level 3 uses the same evaluation as Level 2, but the search depth is 2. This
  86. should be quite strong already for beginners.
  87.  
  88. You'll see that the evaluation function, not the search depth, is essential
  89. for the strength. If the machine looks eight moves ahead, but evaluates the
  90. occuring boards wrong, it will try to get to a wrong position. If it gets
  91. good values near to the real ones, one (halve-)move ahead will be strong
  92. already. If you take a greater search depth then, the game will soon become
  93. unbeatable. But note, in general a computer will never play perfect if it
  94. does not search up to the very end. If you've got only endboards to evaluate,
  95. you've just got to detect who has won. You may then force a win by simply
  96. moving to a position wherefrom all endboards are victories, if it is at all
  97. possible. Currently WhiteLion searches for endgame positions from move
  98. (55-LevelNr/2) on, (56-LevelNr) in the registered version.
  99.  
  100. If you like the game so far, and you did already beat it on level 3, please
  101. consider sending me the Shareware fee. Then you'll receive the source code
  102. with more explanations on the algorithms (GB and D) and the executable
  103. programs. The source is in C and has been compiled with DICE, a freely
  104. distributable C compiler from Fish Disk 491. I also tried Manx Aztec C 5.0a,
  105. but DICE was both faster and created the smaller executable. Thanks, Matt!
  106. The source was originally written in German. I translated the comments
  107. afterwards, but the variables are still a german/english mixture. Should be
  108. no problem, though. Next time I'll write the source completely in English,
  109. that's for sure.
  110. You'll also receive the (D and GB) registered versions of WhiteLion 1.2.
  111. They look similar, but WhiteLion now plays a very strong and mysterious
  112. strategy, which is called the Minimum Disk Strategy. The idea is, WhiteLion
  113. tries to get as few disks as possible in the opening game, to reduce the
  114. number of moves you may choose from. You'll find that if you've got less
  115. moves, the bad ones are still there, while the good ones seem to have
  116. disappeared. While the game continues, WhiteLion gets into a strong position
  117. and catches all disks back in the endgame. You'll see! Here the level number
  118. is equal to the number of halvmoves WhiteLion calculates ahead.
  119.  
  120. The Shareware fee is 10 DM, 7 US$ or 4 british £ in banknotes. I presume it
  121. is not too much if you consider how much time I invested to write the game.
  122. Especially those goodlooking new 5 DM-bills are welcome. Wrap it into a paper
  123. sheet to protect it from curious eyes on its journey, and simply send it in a
  124. standard envelope letter, asking for the registered version of WhiteLion.
  125. I'd be interested in your basic computer model and your Kickstart/Workbench
  126. version. If you've got any suggestions on how to strengthen the evaluation or
  127. want a user interface feature or if you found a bug (i.e. weird behaviour),
  128. I'd be glad to hear from you. But if you don't want to, you needn't write a
  129. letter. I promise I'll send back the disk as soon as possible, in general the
  130. next working day. If you've got an EMail address, I can also send you the
  131. game over the wire, packed with lha and uuencoded. This will usually be even
  132. faster and saves me the expenses for disk and stamps. Just let me know.
  133. When I receive the first letter from Japan, I'll be glad to send back the
  134. money. I know that Othello is very popular there (next to Go, of course...),
  135. and I'd especially like any measurement on WhiteLion's strength from there.
  136.  
  137. I'll keep the right to develop a major new version of Othello even if I get
  138. less then 20 registrations, but it is quite unlikely. I don't want to write
  139. complex programs if noone is interested in them afterwards.
  140.  
  141. Plans for WhiteLion 2.0 include:
  142.  
  143. - complete new user interface according to the Style Guide, including Menus,
  144.   MenuHelp, 2D/3D board display, OS 2 style cycle and slider gadgets, and
  145.   special OS 3 features like 256 colour display and localization. As a result,
  146.   this major new version will require OS 2.04 as a minimum platform to run.
  147.   I'm definitely not going through this 'have to keep it 1.2 compatible'
  148.   problems again. I might consider putting the stronger algorithms described
  149.   below into the OS 1.2 version, if there is enough interest. I might also
  150.   give away a licence and the necessary sources instead if someone asks.
  151.  
  152. - ARexx and Library implementation so you may try out your own strategy by
  153.   remixing and weighting the evaluation components. You will be able to
  154.   easily simulate the whole search process using the library calls so you'll
  155.   need ARexx only to supply the result. This ensures it will still be fast.
  156.  
  157. - replacement of the a-ß algorithm with the faster SSS*; replacement of SSS*
  158.   with SCOUT in the endgame, when the number of possible moves gets lower;
  159.   replacement of SCOUT with SOLVE when the computer begins to search to the
  160.   very end.
  161.  
  162. - tournament mode to play against clocks. Implementation of time-dependant
  163.   search depth and time usage strategy.
  164.  
  165. - rewriting of the mobility evaluation. Spreading of the mobility evaluation
  166.   over the search tree to save time, i.e. counting the moves while building
  167.   up the tree.
  168.  
  169. - your suggestions. Just tell me.
  170.  
  171. -----------------------------------------------------------------------------
  172. ---- legal stuff ------------------------------------------------------------
  173. -----------------------------------------------------------------------------
  174.  
  175. In the following context, 'This Program' means the whole WhiteLion1.2 package
  176. as described below. If any part of the following context should be illegal
  177. under a country's law, the whole rest remains valid nevertheless.
  178.  
  179. This Program is © (c) MXMII, MXMIII by me, Martin Grote, born 25.04.1970.
  180. All Rights Reserved Worldwide.
  181.  
  182. This Program must not be changed by anyone except written permission by me or
  183. for personal use only.
  184.  
  185. This Program is Shareware. Only the version with the disabled [4] gadget may
  186. be freely redistributed. It may be distributed only as the whole package, a
  187. directory containing the following files:
  188.  
  189.   WhiteLion_FD_gb        size: 50608 Bytes
  190.   WhiteLion_FD_d         size: 48452 Bytes
  191.   WhiteLion.doc          size: 12730 Bytes
  192.   WhiteLion_FD_gb.info   size:  1614 Bytes
  193.   WhiteLion_FD_d.info    size:  1614 Bytes
  194.   WhiteLion.doc.info     size:   842 Bytes
  195.  
  196. The whole package may be packed with a program like 'lha', and be redistri-
  197. buted as such, if no extra charge is applied for this. It must unpack to
  198. This Program then.
  199.  
  200. I would be glad if Mr. Fred Fish, Amiga Library Disks, would consider placing
  201. This Program on one of his AmigaLibDisks. He may distribute it for whatever
  202. he assumes necessary then.
  203. In no case may anyone else redistribute This Program for more than 5 US$,
  204. five US dollars, without written permission from the author.
  205. In Germany This Program must not be distributed for more than 5 DM; in our
  206. words:
  207.  
  208. »»»» Dieses Programm darf in Deutschland nicht für mehr als 5 (fünf) DM  ««««
  209. »»»» vertrieben werden, falls keine schriftlich Erlaubnis von mir,       ««««
  210. »»»» Martin Grote, vorliegt. Dies gilt insbesondere für alle deutschen   ««««
  211. »»»»                        »»» PD-Händler! «««                          ««««
  212.  
  213. This Program or any part of it may not be included in a commercial program
  214. package without written permission from the author. Just ask me.
  215.  
  216. No warranty is given that This Program serves for any special purpose. Use it
  217. on your own risk. No damage is intended, but the author can not be made
  218. reliable for any damage caused by This Program nevertheless.
  219.  
  220. -----------------------------------------------------------------------------
  221.  
  222. Nordborchen, 20th of January, 93.
  223.  
  224. Martin Grote
  225. Wegelange 66
  226. 4799 Nordborchen
  227. Germany, EC
  228.  
  229. EMail: chandler@uni-paderborn.de
  230.  
  231.