Essay on computer go by David Fotland

                    Computer Go Design Issues
                       David Fotland

Here is a brief summary of the key design issues facing a computer go programmer, and some of the possible solutions:

The highest level components of a go program are strategic evaluation, move selection, full board evaluation, and search strategy.

A good full board evaluator is very difficult to write, and will be very slow. Since evaluation is slow, a full width search is impractical, so a good move selector is essential. People can look many moves ahead in go, so a program must be prepared to look 5 to 10 moves deep before evaluation in a fight. In a quiet position, move selection is dominated by strategic considerations, and one move lookahead may be fine.

There will always be uncertainty in the results of any evaluation or reading. Strong programs can handle uncertainty, and represent the difference between a high confidence and low confidence result.

In many positions strategic considerations dominate the move choices, and the full board evaluations of the resulting positions will be very similar. So it is important to decide on the strategic goal, and do move selection with that in mind.

The general approach is:

First, do a stratgic evaluation of the position and choose your goals. Second select moves and do some full board searching. Evaluate the moves according to the goals, or evaluate the resulting positions. Third, make the best move.

In most go positions there are many good moves available of similar value. Two important considerations when choosing moves are:

Don't throw away a big group - this will usually lose the game. Accurate life and death reading is important a few times in every game. Misevaluating the security of a connection or eye space loses lots of games.

Don't waste moves. Each completely wasted move is worth about one rank in strength. Adding a move to your own group when it is not needed, or spending an extra move capturing a small enemy group, or wasting a move trying to attack a strong enemy group are common problems.

1) The first key decision is how to choose the best move.

  A) some programs follow the computer chess approach of using a full board
     evaluation function, and doing searching to find the move that
     maximizes the evaluation function. Go4++, SmartGo
  B) some programs just evaluate moves according to some decision tree and
     strategic considerations, choosing the move that meets the highest
     priority goal. Nemesis, Go Intellect?
  C) most programs use some combination of these approaches.
     MFGO?

2) Strategic evaluation:

  A) are you ahead, even, or behind?  Play aggressive and risky moves when
     behind, and safe moves when ahead.
  B) what is the phase of the game (opening, middle game, endgame)
     1) in the opening, big moves are worth about 20 points
     2) in the middle game, the focus is on attack/defense of weak groups
     3) in the endgame, the focus is on size of moves
  C) how much is sente worth
     1) varies from move to move
     2) about 12-15 points on empty board
  D) where are the weak groups?  should you try to kill a group, chase it
     around, or surround it and make it live in gote?  should you pull out
     your own weak group or sacrifice it?
  E) do you do life and death reading as part of strategic evaluation, or
     as part of full board evaluation?
  F) do you remember strategic considerations from move to move for more
     consistent play?
  G) try to figure out the purpose of the enemy's last move and counter it.
  H) what if I pass - what is worst damage enemy can do to me, and where.

3) Move selection:

  A) Joseki libraries
     1) a few basic sequences are enough
     2) better to have program play joseki or near joseki from its other
        knowledge
     3) big libraries possible - how to encode data
        a) about 40,000 moves published in English
        b) about 500,000 moves published in Japanese/Chinese/Korean
     4) graphics data entry
     5) learning from games
     6) edge effects - how wide is the corner, when do moves down the edge
        affect the joseki
     7) organized as tree, acyclic graph, or hash table of positions
     8) how to handle transpositions
  B) fuseki libraries
     1) not very useful beyond fist 5 moves or so
     2) easy to generate, tens of thousands of pro, over 100,000 IGS games available
     3) if library only contains moves played in more than one game, then
        each new game adds an average of one new move to the library.
  C) attack weak groups
     1) decide between trying to kill, trying to surround, trying to force
        the group to run away
  D) defend weak groups
     1) decide between living or running
  E) extensions, invasions, reducing moves
  F) moyo making moves and jumps in the center
  G) endgame moves
     1) mathematical endgame analysis (Berlekamp?s Sum of Games)can give exact values or priority order Explorer?
  H) pattern databases
     1) hand generated and tuned, about 3000 patterns typical
     2) automatically generated from games - not very useful
     3) size of patterns (5x5 Goliath, 8x8 MFGO, Ego?, 11x11,
        arbitrary Explorer?)
     4) how to store and match patterns
        a) bitmaps Goliath, MFGO, Ego?
	4 or 8 values (B, W, Empty, don?t care), or add ?black or empty?, etc.
        b) pattern description language NEMESIS
        c) decision tree Explorer?
     5) attributes of points in pattern
        a) number of liberties
        b) strength of group
        c) tactical stability of group
        d) position of edge/corner of board
     6) graphical pattern editor, how to organize
  I) ko threats
     1) atari's
     2) threats to kill
     3) threats to live
  J) safety moves (when ahead)
     1) answer opponent's move (even if seems bad, like adidng stone to
        dead group)
     2) secure capture of enemy group
     3) secure big area from invasion
  K) unreasonable moves (when behind)
     1) try to kill surrounded group with one big eye
     2) try to save dead group with some potential
     3) make unreasonable invasion
  L) neural nets
  M) other learning techniques ? bayesian pattern extraction from games
  N) how many moves to look at (5 Intellect?, 20 MFGO? to 50 Go4++)
  O) sort moves by size, or priority, or combination
  P) filtering out bad moves
  Q) making obvious big move quickly to save time
  R) do you look at local responses to opponents last move first, or just
     always look at the whole board?

4) Full board Evaluation:

  A) components of an evaluation function
     1) Strings of touching stones - easy to do incrementally
     2) liberties - count and list
     3) tactical stability of strings
        A) a very fast tactical search engine is required
     4) connections between strings
        A) one point jumps are hard to evaluate accurately
        B) often cut is possible, but bad - effectively a connection
        C) A connected to B, B connected to C does not imply that
           A is connected to C.
        D) connection pattern database.
     5) groups of connected (or nearby) strings
     6) eyes and secure eye space
        A) static evaluation of large, partially surrounded eyes is hard
           1) size of eye
           2) shape of eye
           3) minimim size and shape after all hane, pushing moves from
              outside are answered Bruce Wilcox
           4) control of outside diagonals
           5) internal vital points
        B) eye shape pattern database
        C) perimeter heuristic Mark Boon - classify eye shapes by
           size and perimeter - lower perimeter means fewer eyes.
        D) limited number of eye values, can be added up, but simple
           integer values like .5, 1, 1.5, 2 eyes is not accurate enough.
           The values 0, 1/2, 3/4, 1, 1*, 1 1/4, 1 1/2, 2 cover all big
           eyespaces that do not involve a ko or seki (from Howard Landman).
           For multiple eyes, these values can be added, provided that
           there is no move that affects two eyespaces simultaneously.
     7) running ability, or degree of surroundedness
        A) access to big open areas
        B) relative thickness of nearby enemy groups
     8) strength of groups
        A) in middle game, typical stable group does not have two small eyes
        B) depends on relative strength of nearby enemy groups
        C) ability to make two eyes if surrounded
        D) ability to run away somewhere useful if denied two eyes
        E) ability to capture nearby enemy if can make two eyes or run away
     9) aji, thick vs thin positions
     10) moyo, or potential territory
     11) secure territory
        A) radiate influence from live stones, compare friendly and
           unfriendly influence at each point.  Many possible influence
           functions.
           1) influence falls as 1/dist (sum from all stones) MFGO?
           2) influence falls as 1/dist^2 (sum from all stones) Intellect?
           3) assign high value to points with stone, iteratively bump
              each point with majority of influence on nearby points
              Goliath
           4) expand boundary from stones to linkages or enemy, then
              contract
        B) find secure linkages between stones, find inside/outside of area
           surrounded by linkages Nemesis
        C) at each point ask question - can enemy place a living stone here?
           Go4++
     12) Chinese style MFGO? or Japanese style of counting
  B) how much of the evaluation is incremental, for speed?
     1) most programs are mostly incremental
     2) how to keep track of what needs reevaluation, rereading
  C) does the evaluation depend on who moves next
  D) is life/death reading part of evaluation
  E) how do strategic considerations and move selection goals modify
     the evaluation function
  F) how to combine territory, potential territory, and group strength into
     a single number, or how to search if you choose not to combine these
     into a single number.
  H) evaluate actual score, or difference between local black,
     local white move.
  I) Minimax to try to maximize the score, or to maximize the probability
     of winning the game?  How to determine probability of winning from
     the usual evaluation components (territory, potential, group strength,
     good/bad shape, etc).

5) search strategies

  A) at the full board, to choose move to make
     1) move sequences from database (joseki/fuseki/pattern)
     2) continuing the goal of the original move
     3) resolving contact fights, urgent shape moves
     4) searching for quiet positions
     5) depth first, alpha beta
     6) deep and narrow
      7) how to use iterative deepening and widening in a highly pruned search
  B) for life/death reading
     1) Kind of searching
        a) depth first with alpha/beta MFGO?
        b) PN (proof number) search New Goliath?
        c) best first MFGO?
     2) killer/history heuristics
     3) enemy's key point is your own heuristic
     4) read deep and narrow, many moves forced
     5) bushy tree near root
     6) find all moves that work at 1st ply, not just first
     7) hash/transposition tables
        a) Zobrist hashing (random value per point to add/xor)
        b) 32 bit or 64 bit hash value or 32 bit W and 32 bit B
     8) dan level performance is possible Gotools
     9) move generation/sorting essential
     10) store the trees from move to move MFGO? or not
     11) expected size of search
        a) 10's of nodes for 10 kyu
        b) 100's of nodes for 1-5 kyu
        c) 1000's of nodes for dan level
     12) detect absolute life as early as possible
     13) handle running/surrounding/capturing neighbor as well as making
         eyes
  C) for string tactics
     1) how many liberties to escape (3, 4, or 5)
     2) focus on removing and gaining liberties
     3) attack and defense of nearby enemy strings
     4) very deep searching: 50 moves or more for ladders
     5) must understand two point eyes and simple seki
     6) generate pass move for seki
     7) bushy tree near root
     8) move generation/sorting essential, and not very hard
  D) for connections
     1) fixed sequences to check
     2) use tactician to check status of cutting stones
  E) how to limit search for time control
     1) constant search per computer move selection
     2) constant search per fight - play slower in complex positions
        MFGO?
  F) dealing with uncertainty

6) Learning:

  A) Extract patterns from strong player?s games
     1) get all patterns of all sizes, then find best predictors of next move
     2) what attributes to include beyond stone locations (liberties, stability, etc.
  B) Neural nets
     1) simple architecture based on stone locations doesn?t work
     2) use many nets (connections, eyes, etc)
     3) input higher level attributes ? liberty count, stability
     4) still need search
  C) Learn from opponent each game
     1) avoid repeating losing postions
     2) in future games with this opponent, search his likely moves