[gnugo-devel] pattern-based reading spinoffs (27.7)

[Trevor Morris]

http:/www.public32.com/games/go/trevor_1_27.7
 - KOMASTER_SCHEME 4 introduced
 - Tree-based pattern matching introduced.
 - pattern-base reading code supports defense by pattern.
 - new command-line switches "(attack|defend)-by-pattern"
 - OPT enums re-based to 127, to avoid conflict w/ ASCII values.
 - reformatted transform.c to look like matrices.
 - DRAGON_WEAK implemented in a function and checks array bounds.
 - improved fastlib().
 - DRAGON2 macro checks array bounds.
 - for non-variadic, non-VC compilers, add trace_dummy assignment

Almost all of this was inspired by the pattern-base reading
code that I continue to tweek.  The rest inspired by the VC
crashes and enhancements of late.

Here's an extract of the comments from the tree-based pattern
matcher.  For owl, it's about as fast as the DFA, though I've tested
it very very little outside of the reading-based pattern code,
where it gives a 20% improvement:
 * Conceptually, each node of the tree corresponds to either
 * ATT_dot, ATT_X, or ATT_O, with an x and y coordinate relative
 * to the anchor.  When the pattern matcher is run, if 
 * board[POS(node.x, node.y)] == node.att, then proceed to the
 * next node.  If you find a node with a match_node pointer,
 * then a pattern has matched (with a given orientation).

Here's a bit of the komaster scheme 4 comments:
/* (IV) A different komaster approach.
 * As of 3.1.27 it's quite slow, and has been tested primarily
 * in the context of pattern-based reading, where the other 
 * komaster schemes weren't sufficient.  It does eliminate all
 * tested cyclic ko problems, but still fails a few regressions.
 *
 * If kom_pos == PASS, then there is no ko restriction in place.
 * This allows us to forgo an empty komaster status.  The extra
 * 1/2 bit gives us room to track some more information.
 *
 * 1. Komaster_pos is PASS:
 *   Move always allowed.
 *   If it's a legal ko capture, then komaster becomes KOMASTER_{OX}_legal, 
 *     and komaster_pos set to (pos). OX determined by color parameter.
 *   If it's an illegal ko capture, komaster becomes KOMASTER_{OX}_illegal,
 *     and komaster_pos set to (pos). OX determined by color parameter.
 *     If !consider_conditional_ko, the move is not allowed.
 *   If it's not a ko, komaster_pos remains PASS.
 *
 * The treatment of KOMASTER_O and KOMASTER_X are always identical,
 * simply with the player to move switched.  Below, only one of the
 * two identical cases is given.
 *
 * 2. Komaster_pos is (pos), komaster is KOMASTER_O_legal:
 * 2a X to play:
 *    if pos takes same ko as komaster_pos:
 *      if legal, komaster becomes KOMASTER_X_illegal (!).
 *      if illegal (ko threat required),
 *        if consider_conditional_ko
 *          komaster becomes KOMASTER_X_illegal.
 *    X may make any other legal move, including kos, and the komaster
 *      does not change.
 * 2b O to play:
 *    O may resolve this ko, or take a related ko.
 *      if it's a related ko, the komaster_pos changes to this related ko.
 *    O may not take an unrelated ko.  He must resolve this one first.  This
 *      avoids triple ko problems.
 *
 * 3. Komaster_pos is (pos), komaster is KOMASTER_O_illegal:
 * 3a X simply resolves to a trymove(), since O's already made a conditional
 *      capture, X may not make a conditional capture too.
 * 3b O's play is identical to the legal case.
 */