home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / rec / games / abstract / 365 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  3.3 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: rec.games.abstract
  4. Subject: Re: Othello: static board evaluation
  5. Message-ID: <1992Nov17.131442.14679@odin.diku.dk>
  6. Date: 17 Nov 92 13:14:42 GMT
  7. References: <C89MIKHO.92Nov13154747@odal23.IDA.LiU.SE>
  8. Sender: torbenm@freke.diku.dk
  9. Distribution: rec.games.abstract
  10. Organization: Department of Computer Science, U of Copenhagen
  11. Lines: 58
  12.  
  13. c89mikho@IDA.LiU.SE (Mikael Hovmoller) writes:
  14.  
  15. >I plan to implement a minimax algorithm with alpha-beta cutoffs. This
  16. >works good enough, as this is a minor project for school, and not an
  17. >olympic winner-to-be. However, I find it hard to implement a good
  18. >static board evaluation. The one I'm currently using gives every
  19. >position on the board a specific value if the computer occupies
  20. >it, minus that same value if the player has it, and 0 if it's
  21. >currently empty.
  22.  
  23. >This seems reasonable to me, but in reality doesn't play very good.
  24.  
  25. This is the method used by most "beginners" trying to make an
  26. evaluation function, and as you said it isn't very good. In my program
  27. I use these factors:
  28.  
  29.   1) How many legal moves does the opponent have. A small number is
  30.      good.
  31.  
  32.   2) I have built a table of all possible combinations of pieces on an
  33.      edge (there are only about 6500) and assigned each of these a
  34.      value. This is (of course) not done by hand, but by a program
  35.      that makes an exhaustive search of all plays on the edge. A legal
  36.      move is is of course one that flips pieces on the edge, but in
  37.      addition to these I have considered three different lines of
  38.      play: in the first, the opponent is able to move in any empty
  39.      square except corners, but you only by flipping. In the second,
  40.      it is opposite and in the third both are able to move anywhere
  41.      except corners. At the point where no further moves are
  42.      possible, the number of safe (unflippable) pieces are counted,
  43.      with the corner counting extra. The values of the different lines
  44.      of play are added using weights that reflect playing strategy. A
  45.      high weight on the case where the opponent has the advantage
  46.      gives a defensive play, where a high weight on your own advantage
  47.      gives a more aggresive play. Once the table is made, it is fairly
  48.      quick to look up any edge position in the table.
  49.  
  50.   3) I look at the control of the diagonals. If the diagonal space
  51.      next to a corner is occupied and the corner itself isn't, the
  52.      values of the neighbouring edges after a move by the opposite
  53.      colour in the corner are used to modify the value of the
  54.      position. If a move to the corner is immediately possible, the
  55.      effect of it counts more than if not, especially near the end of
  56.      the game.
  57.  
  58. Note that I nowhere use a weighted sum of the occupied squares.
  59. However, near the end of the game all remaining moves are explored
  60. fully, and a simple sum is used as value. The program plays reasonably
  61. well, though nowhere near as good as the program Colin Springer is
  62. coauthor of.
  63.  
  64. Other things you can consider is to make extra deep search of forced
  65. moves and passes, counting safe pieces not on the corners, counting
  66. the number of "good" moves rather than the total number of moves when
  67. counting mobility. A good move could be defined as one that does not
  68. move next to an empty corner.
  69.  
  70.     Torben Mogensen (torbenm@diku.dk)
  71.