From f03dc55e273effe36c76d27c0e78888d0ab30a88 Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Sat, 31 Jul 2010 10:38:33 +0200 Subject: [PATCH] Introduce Joseki Scanner aux engine --- HACKING | 13 +++- Makefile | 4 +- joseki/Makefile | 12 ++++ joseki/README | 18 +++++ joseki/base.c | 11 +++ joseki/base.h | 16 +++++ joseki/joseki.c | 191 +++++++++++++++++++++++++++++++++++++++++++++++++++ joseki/joseki.h | 8 +++ joseki/sgfvar2gtp.pl | 54 +++++++++++++++ zzgo.c | 5 ++ 10 files changed, 328 insertions(+), 4 deletions(-) create mode 100644 joseki/Makefile create mode 100644 joseki/README create mode 100644 joseki/base.c create mode 100644 joseki/base.h create mode 100644 joseki/joseki.c create mode 100644 joseki/joseki.h create mode 100644 joseki/sgfvar2gtp.pl diff --git a/HACKING b/HACKING index 2831311..4be377e 100644 --- a/HACKING +++ b/HACKING @@ -53,10 +53,11 @@ Pachi consists of the following components: replay/ example "playout move generator" engine montecarlo/ simple treeless Monte Carlo engine, quite bitrotten uct/ the main UCT-player engine, see below - patternscan/ auxiliary engine for harvesting patterns from - existing games distributed/ "meta-engine" for distributed play by orchestrating several UCT engines on different computers + patternscan/ auxiliary engine for harvesting patterns from + existing games + joseki/ auxiliary engine for generating joseki patterns * "playout" policy is asked to generate moves to play during the Monte Carlo simulations, and to provide rough evaluation of moves feasibility for @@ -240,3 +241,11 @@ The UCT engine allows external plugins to be loaded and provide external knowledge for various heuristics - currently just biasing the MCTS priors, but more can be added easily. The plugins should follow the API in - see that file for details. + + +Joseki Patterns +=============== + +Joseki patterns can be generated from variations of a SGF file. Josekis +are matched per-quadrant, no other move must be within the quadrant. See +joseki/README for details on usage of the auxiliary engine. diff --git a/Makefile b/Makefile index 6bca0c9..e31ea68 100644 --- a/Makefile +++ b/Makefile @@ -34,11 +34,11 @@ INCLUDES=-I. OBJS=board.o gtp.o move.o ownermap.o pattern3.o pattern.o patternsp.o playout.o probdist.o random.o stone.o tactics.o timeinfo.o network.o -SUBDIRS=random replay patternscan montecarlo uct uct/policy playout t-unit distributed +SUBDIRS=random replay patternscan joseki montecarlo uct uct/policy playout t-unit distributed all: all-recursive zzgo -LOCALLIBS=random/random.a replay/replay.a patternscan/patternscan.a montecarlo/montecarlo.a uct/uct.a uct/policy/uctpolicy.a playout/playout.a t-unit/test.a distributed/distributed.a +LOCALLIBS=random/random.a replay/replay.a patternscan/patternscan.a joseki/joseki.a montecarlo/montecarlo.a uct/uct.a uct/policy/uctpolicy.a playout/playout.a t-unit/test.a distributed/distributed.a zzgo: $(OBJS) zzgo.o $(LOCALLIBS) $(call cmd,link) diff --git a/joseki/Makefile b/joseki/Makefile new file mode 100644 index 0000000..b1a8a1c --- /dev/null +++ b/joseki/Makefile @@ -0,0 +1,12 @@ +INCLUDES=-I.. +OBJS=joseki.o base.o + +all: joseki.a +joseki.a: $(OBJS) + +clean: + rm -f *.o *.a +clean-profiled: + rm -f *.gcda *.gcno + +-include ../Makefile.lib diff --git a/joseki/README b/joseki/README new file mode 100644 index 0000000..ddeb0fb --- /dev/null +++ b/joseki/README @@ -0,0 +1,18 @@ +This is a joseki pattern scanner. At the beginning, you should +have a SGF file with various joseki as variations; they are assumed +to be laid out in the upper right corner; only variations leading +to a comment containing the word "GOOD" are considered. All variations +should be tagged as real moves, not move placement. + +This pattern scanner works with the Kogo joseki dictionary. You need +to just preprocess the file with this script: + + perl -ple 's/\w+\[\]//g; s/PL\[\d\]//g;' + +Then, use the ./sgfvar2gtp.pl script to convert the SGF to a GTP stream, +one game per good variation. + +Then, feed that GTP stream to ./zzgo -e joseki to get a pattern datafile +on the output - the file contains list of quadrant positions (identified +by their zobrist hashes) and the associated w-to-play and b-to-play +joseki followups. diff --git a/joseki/base.c b/joseki/base.c new file mode 100644 index 0000000..28c6c40 --- /dev/null +++ b/joseki/base.c @@ -0,0 +1,11 @@ +#include +#include +#include + +#include "board.h" +#include "debug.h" +#include "move.h" +#include "joseki/base.h" + + +struct joseki joseki_pats[1 << joseki_hash_bits]; diff --git a/joseki/base.h b/joseki/base.h new file mode 100644 index 0000000..36d00e7 --- /dev/null +++ b/joseki/base.h @@ -0,0 +1,16 @@ +#ifndef ZZGO_JOSEKI_BASE_H +#define ZZGO_JOSEKI_BASE_H + +#include "board.h" + +/* Single joseki situation - moves for S_BLACK-1, S_WHITE-1. */ +struct joseki { + /* moves[] is a pass-terminated list or NULL */ + coord_t *moves[2]; +}; + +#define joseki_hash_bits 20 // 8M w/ 32-bit pointers +#define joseki_hash_mask ((1 << joseki_hash_bits) - 1) +extern struct joseki joseki_pats[]; + +#endif diff --git a/joseki/joseki.c b/joseki/joseki.c new file mode 100644 index 0000000..5137c5a --- /dev/null +++ b/joseki/joseki.c @@ -0,0 +1,191 @@ +#include +#include +#include + +#include "board.h" +#include "debug.h" +#include "engine.h" +#include "move.h" +#include "joseki/joseki.h" +#include "joseki/base.h" + + +/* Internal engine state. */ +struct joseki_engine { + int debug_level; + int size; + + struct board *b[16]; // boards with reversed color, mirrored and rotated +}; + +/* We will record the joseki positions into incrementally-built + * joseki_pats[]. */ + + +static char * +joseki_play(struct engine *e, struct board *b, struct move *m) +{ + struct joseki_engine *j = e->data; + + if (!b->moves) { + /* Reset boards. */ + j->size = board_size(b); + for (int i = 0; i < 16; i++) { + board_resize(j->b[i], j->size - 2); + board_clear(j->b[i]); + } + } + + assert(!is_resign(m->coord)); + if (is_pass(m->coord)) + return NULL; + //printf("%s %d\n", coord2sstr(m->coord, b), coord_quadrant(m->coord, b)); + /* Ignore moves in different quadrants. */ + if (coord_quadrant(m->coord, b) > 0) + return NULL; + + //printf("%"PRIhash" %"PRIhash"\n", j->b[0]->qhash[0], b->qhash[0]); + assert(j->b[0]->qhash[0] == b->qhash[0]); + + /* Record next move in all rotations and update the hash. */ + for (int i = 0; i < 16; i++) { +#define HASH_VMIRROR 1 +#define HASH_HMIRROR 2 +#define HASH_XYFLIP 4 +#define HASH_OCOLOR 8 + int quadrant = 0; + coord_t coord = m->coord; + if (i & HASH_VMIRROR) { + coord = coord_xy(b, coord_x(coord, b), board_size(b) - 1 - coord_y(coord, b)); + quadrant += 2; + } + if (i & HASH_HMIRROR) { + coord = coord_xy(b, board_size(b) - 1 - coord_x(coord, b), coord_y(coord, b)); + quadrant++; + } + if (i & HASH_XYFLIP) { + coord = coord_xy(b, coord_y(coord, b), coord_x(coord, b)); + if (quadrant == 1) + quadrant = 2; + else if (quadrant == 2) + quadrant = 1; + } + enum stone color = m->color; + if (i & HASH_OCOLOR) + color = stone_other(color); + + coord_t **ccp = &joseki_pats[j->b[i]->qhash[quadrant] & joseki_hash_mask].moves[color - 1]; + + int count = 1; + if (*ccp) { + for (coord_t *cc = *ccp; !is_pass(*cc); cc++) { + count++; + if (*cc == coord) { + //printf("(%"PRIhash", %d) !+ %s\n", j->b[i]->qhash[0], count, coord2sstr(coord, b)); + goto already_have; + } + } + } + + *ccp = realloc(*ccp, (count + 1) * sizeof(coord_t)); + //printf("(%"PRIhash", %d) + %s\n", j->b[i]->qhash[quadrant], count, coord2sstr(coord, b)); + (*ccp)[count - 1] = coord; + (*ccp)[count] = pass; + +already_have: { + struct move m2 = { .coord = coord, .color = color }; + board_play(j->b[i], &m2); + } + } + + return NULL; +} + +static coord_t * +joseki_genmove(struct engine *e, struct board *b, struct time_info *ti, enum stone color, bool pass_all_alive) +{ + fprintf(stderr, "genmove command not available in joseki scan!\n"); + exit(EXIT_FAILURE); +} + +void +joseki_done(struct engine *e) +{ + struct joseki_engine *j = e->data; + struct board *b = board_init(); + board_resize(b, j->size - 2); + board_clear(b); + + for (hash_t i = 0; i < 1 << joseki_hash_bits; i++) { + for (int j = 0; j < 2; j++) { + static const char cs[] = "bw"; + if (!joseki_pats[i].moves[j]) + continue; + printf("%" PRIhash " %c", i, cs[j]); + coord_t *cc = joseki_pats[i].moves[j]; + int count = 0; + while (!is_pass(*cc)) { + printf(" %s", coord2sstr(*cc, b)); + cc++, count++; + } + printf(" %d\n", count); + } + } + + board_done(b); +} + + +struct joseki_engine * +joseki_state_init(char *arg) +{ + struct joseki_engine *j = calloc2(1, sizeof(struct joseki_engine)); + + for (int i = 0; i < 16; i++) + j->b[i] = board_init(); + + j->debug_level = 1; + + if (arg) { + char *optspec, *next = arg; + while (*next) { + optspec = next; + next += strcspn(next, ","); + if (*next) { *next++ = 0; } else { *next = 0; } + + char *optname = optspec; + char *optval = strchr(optspec, '='); + if (optval) *optval++ = 0; + + if (!strcasecmp(optname, "debug")) { + if (optval) + j->debug_level = atoi(optval); + else + j->debug_level++; + + } else { + fprintf(stderr, "joseki: Invalid engine argument %s or missing value\n", optname); + exit(EXIT_FAILURE); + } + } + } + + return j; +} + +struct engine * +engine_joseki_init(char *arg, struct board *b) +{ + struct joseki_engine *j = joseki_state_init(arg); + struct engine *e = calloc2(1, sizeof(struct engine)); + e->name = "Joseki Engine"; + e->comment = "You cannot play Pachi with this engine, it is intended for special development use - scanning of joseki sequences fed to it within the GTP stream."; + e->genmove = joseki_genmove; + e->notify_play = joseki_play; + e->done = joseki_done; + e->data = j; + // clear_board does not concern us, we like to work over many games + e->keep_on_clear = true; + + return e; +} diff --git a/joseki/joseki.h b/joseki/joseki.h new file mode 100644 index 0000000..0f688de --- /dev/null +++ b/joseki/joseki.h @@ -0,0 +1,8 @@ +#ifndef ZZGO_JOSEKI_JOSEKI_H +#define ZZGO_JOSEKI_JOSEKI_H + +#include "engine.h" + +struct engine *engine_joseki_init(char *arg, struct board *b); + +#endif diff --git a/joseki/sgfvar2gtp.pl b/joseki/sgfvar2gtp.pl new file mode 100644 index 0000000..5b05b6b --- /dev/null +++ b/joseki/sgfvar2gtp.pl @@ -0,0 +1,54 @@ +#!/usr/bin/perl +# Convert SGF file to a sequence of GTP games, one game per each variation +# that ends with /GOOD/ comment. + +use warnings; +use strict; + +sub printgame +{ + my ($sgf) = @_; + my $pt = $sgf->getAddress(); + + my @moves; + do { + my ($b, $w) = ($sgf->property('B'), $sgf->property('W')); + if ($b) { push @moves, ['b', $_] foreach @$b; } + if ($w) { push @moves, ['w', $_] foreach @$w; } + } while ($sgf->prev()); + + print "boardsize 19\nclear_board\n"; + for my $move (reverse @moves) { + my ($sx, $sy) = @{$move->[1]}; + my @abcd = split(//, "abcdefghjklmnopqrstuvwxyz"); + my $x = $sy + 1; my $y = $abcd[18 - $sx]; + if ("$y$x" eq "z20") { + $y = "pass"; $x = ""; + } + print "play ".$move->[0]." $y$x\n"; + } + + $sgf->goto($pt); +} + +sub recurse +{ + my ($sgf) = @_; + my $c = $sgf->property('C'); + if ($c and $c->[0] =~ /GOOD/) { + printgame($sgf); + } + for (0 .. $sgf->branches()-1) { + $sgf->gotoBranch($_); + recurse($sgf); + $sgf->prev(); + } +} + +use Games::SGF::Go; +my $sgf = new Games::SGF::Go; + +$sgf->readFile($ARGV[0]); + +$sgf->gotoRoot(); +recurse($sgf); diff --git a/zzgo.c b/zzgo.c index db07747..b8ce54f 100644 --- a/zzgo.c +++ b/zzgo.c @@ -14,6 +14,7 @@ #include "montecarlo/montecarlo.h" #include "random/random.h" #include "patternscan/patternscan.h" +#include "joseki/joseki.h" #include "t-unit/test.h" #include "uct/uct.h" #include "distributed/distributed.h" @@ -35,6 +36,7 @@ enum engine_id { E_MONTECARLO, E_UCT, E_DISTRIBUTED, + E_JOSEKI, E_MAX, }; @@ -45,6 +47,7 @@ static struct engine *(*engine_init[E_MAX])(char *arg, struct board *b) = { engine_montecarlo_init, engine_uct_init, engine_distributed_init, + engine_joseki_init, }; static struct engine *init_engine(enum engine_id engine, char *e_arg, struct board *b) @@ -98,6 +101,8 @@ int main(int argc, char *argv[]) engine = E_UCT; } else if (!strcasecmp(optarg, "distributed")) { engine = E_DISTRIBUTED; + } else if (!strcasecmp(optarg, "joseki")) { + engine = E_JOSEKI; } else { fprintf(stderr, "%s: Invalid -e argument %s\n", argv[0], optarg); exit(1); -- 2.11.4.GIT