InfoMagic Source Code 1993 July/THE_SOURCE_CODE_CD_ROM.iso/gnu/gnugo/Documentation

Text File | 1989-03-07 | 11.1 KB | 292 lines

               GNU GO - the game of Go (Wei-Chi)
               Version 1.1   last revised 3-1-89
         Copyright (C) Free Software Foundation, Inc.
                    written by Man L. Li
                    modified by Wayne Iba
                   documented by Bob Webber

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation - version 1.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License in file COPYING for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

Please report any bug/fix, modification, suggestion to

mail address:   Man L. Li
                Dept. of Computer Science
                University of Houston
                4800 Calhoun Road
                Houston, TX 77004

e-mail address: [e-mail]         (Internet)
                [e-mail]   (BITNET)
                70070,404               (CompuServe)


value 0 always used to mark empty square
value 1 always used to indicate white
value 2 always used to indicate black

main()
    Shows instructions.

    If old game then read in information otherwise
    Initializes the board stored in the board array p to zero.

    Requests handicap (stored in local variable i.)

    Displays board.

    Asks which side you want to play (stored in local variable ans)
    mymove and umove indicate color played by computer and user, respectively.

    if user black in handicap game or white in even game, computer goes first.

    making a move means updating the board with the numeric value for color
    of player.  genmove takes board indices i & j as reference parameters
    and returns the ones that correspond to a new move for the computer,
    it does not update the board.  the routine examboard then clears
    of dead pieces (of the color passed as its parameter).  after the board
    has been updated, showboard displays board.

    routine getmove convert the string the user types in into a valid
    move i,j pair.

    getmove manipulates global variable stop to indicate when game is
    done.

    the game stop after both pass, the user want to quit and save game
    or the user stop the game

    at the end of game, if the user types y to ``count score'' prompt,
    then endgame is invoked, otherwise the program exits.


showboard()
    displays go board with algebraic notation on borders.  special logic
    to make sure handicap markers are displayed appropriately done by
    brute force.


getmove(move, i, j)
    if move = "stop" then global variable play changed to 0 exiting loop

    if move = "save" then write game information to file and exit by
    setting global variable to -1

    if move = "pass" then increment global variable pass
    otherwise, clear pass flag getij is invoked to convert move into i and j
    coordinates.
    if the board position is not empty, the last piece captured by
    computer, or suicide predicate is true, then the move is flagged as
    illegal and getmove recurses.


getij(move, i, j)
    move string converted to board coordinates.


genmove(i, j)
    generates computers move and returns it in pointers i & j.
    invoke eval(umove) to re-evaluate liberty of opponent pieces

    findwinner looks for pieces of user that only have 3 or less liberties.
    findsaver looks for pieces of computer that only have 3 or less liberties.
    findpat looks for a pattern in stored database that can be used here.

    STRATEGY:
       choose move with maximum value from the followings:

       find opponent piece to capture or attack with less than four liberties
       save any piece if threaten with less than four liberties
       try to match local play pattern for new move

       no urgent move then do random move
          when generating random move, bias row and column x
          by rejecting the first x that satisfies
          ((x < 2) || (x > 16) || ((x > 5) && (x < 13)))
          and on second try, reject an x that satisfies
          ((x < 2) || (x > 16))
          on third try, take what you get.  done independently for
          i and j.
          invoke countlib to count liberties, if spot already taken
            or liberties (taken off global lib) 0 or 1 or fill in own eye then
            reject.

          if number of try equals to MAXTRY then pass

    after following STRATEGY to determine move, print it.


seed(i)
   sets up a seed.  two versions depending on whether Sun (which uses
   gettimeofday to set seed) or IBM PC (which uses interrupt 21 to get system
   time).


random(i)
  simple conguence random number generator.  only used for making ``random''
  moves, either in genmove() or in opening().


eval(color)
  evaluate liberties of pieces of a particular color using countlib.
  result stored in global array l.


examboard(color)
  invokes eval(color)
  remove pieces with zero liberties, updating count of pieces captured
  in variables mk and uk for computer and user respectively.


suicide(i, j)
  check to see if new move is suicide via countlib().  if it is, check to
  see if it kills computer's pieces via eval() or if Ko takes place
  returns 0 if move is good.


countlib(m, n, color)
    initializes global array ml to 1's and then uses routine count() to
    count liberties at each square.


count(i, j, color)
    count liberties at given square. zero out value of that square.
    if neighbor is still unmarked and its value on the board is still zero,
     then it is marked as zero and lib count is updated,
    if neighbor is same color and unmarked, then count is recursively called.
    this is done for all four neighbors, then the routine returns.

    essentially this does a connected component search on region connected
     to location i & j.


findnextmove(m, n, i, j, val, minlib)
   used by findsaver() to find next move for defense.
   find new move i, j from group containing m, n
   uses global array ma to keep track of where it has been.
   for each neighbor, checks to see if it is empty.  If so, then it
       calculate the new liberty and the relative value of the move.
       Otherwise recurses on that neighbor.  After new move is found compare
       it with other move and use the one with higher value.
   returns 0 if couldn't find move.


findwinner(i, j, val)
   looks for an opponents piece to capture or attack with 1 to 3 liberties.
   for each cell, check to see if its liberties are minlib and if so
     invoke initmark.  evaluate move via findopen.  if findopen returns
     1, then assign value to possible move.
   select new move with highest value and return 1.
   returns 0 if findopen never succeeded.


initmark()
   initialize ma array to zero.


findopen(m, n, i, j, color, minlib, ct)
   called by findwinner to find all open spaces for opponent's piece.
   marks m,n entry in ma array.
   for each neighbor, if neighbor is empty spot and not last place captured,
     then count till all spaces are found and return 1 and move in i and j.
     else if spot is color and not marked, then recurse returning 1 if
             any subinvocation returns 1.


findsaver(i, j, val)
   find move if any pieces of 1 to 3 liberties is threatened
   count how many pieces have minlib liberties.
   if none, return 0.
   else, for each cell, if one of computer's pieces and liberty is minlib,
             then initmark(), and look for move via findnextmove.  if succeeds
             then assign value for possible move.  decrement count of pieces
                  threatened and select next move with maximum value and return
                  1.
  If no new move can be found then return zero and exit.

findpatn(i, j)
       if previous invocation of findpatn marked, then invoke opening
           in that corner.  if opening can find a move on a vacant square,
           then mark this invocation and return value.  if not, then
           clear mark and investigate corners.
       for each marked corner (all corners initially marked), look to see if
           opening can find a move by calling opening() twice.  if it can,
           mark invocation and return that move.
       for each side, look to see if a particular large empty region exists,
           if it does, make a particular move into that region.
       use mathpat on each board location looking for pattern-moves to make
       and select move with maximum value.
       if none of these find something, return 0.


matchpat(m, n, i, j, val)
      for each given pattern, try all ways of placing them down with a corner
      at m,n.  return recommended i,j and value if match found.  pattern
      notation specifies cells that should be empty, where pieces of both sides
      should be, whether must be on edge, and recommended move.  patterns
      consist of at most 16 specified locations.  Try all patterns for each
      piece and select the one with highest value.  Adjust value for patterns
      to expand territories in favor of move at third and fourth line. Reduce
      value for move at first and second line. Return 1 if pattern found else
      return zero.


openregion(i1, j1, i2, j2)
       checks to see if rectangular region is all empty.


opening(i, j, cnd, type)
     type keeps track of which corner, move is reflected thru corner and
       chosen without actually looking at board.
     cnd indicates which move to make this time.  a move consists of a
       location relative to a corner and a count of how many useful
       different followup moves there all.  the useful followups are listed
       by index into the same structure -- the one recommended for next
       move is chosen randomly among possible moves.
     first time in, location -1,-1 is returned. this value is always ignored.


sethand(i)
   setup handicap stones by brute force analysis.


endgame()
   keeps count of captures removed by user cleaning up board, keeps track
   of dame placed by user cleaning up board, and uses findcolor to classify
   territories.  final count presented with updated board showing how
   everything was classified.


findcolor(i, j)
      determines what color to label empty squares when counting up score
      at end of game.  algorithm is to check both north and south neighbors
      until run into occupied square or end of board.  if both are vacant
      then east and west neighbors checked same way.  if both are vacant
      return zero.  if one neighbor zero and other nonzero, return color
      of nonzero neighbor.  if both neighbors nonzero and same, then return
      that color. if both neighbors nonzero but differ, then return zero.


showinst()
     shows program header and a list of instructions to user.


fioe(i, j)
     check if new move (i, j) will fill in own eye at center and edge.  Only
     single hole eye is checked.


fval(newlib, minlib)
     used in findnextmove in findnext.c.  Calculate relative value for new
     move having newlib liberties with old pieces having minlib liberties.