/*  wally.c
From: newman@tcgould.TN.CORNELL.EDU (Bill Newman)
Subject: another simple-minded PD go-playing program

Before gnu-go was announced, I used the ideas in the BYTE article by J.K.
Millen (April 1981) to make a go-playing program ("wally") of my own.
Wally's only advantage over gnugo is that it plays better than the
early gnugo versions that I saw (pulling ahead even before gnugo made its
random self-destructive moves in the endgame).
Wally uses explicit array addressing instead of pointer
arithmetic, so it is slower than it should be, but otherwise I'm
not too embarrassed by the details of the code.  (though constructive
criticism is always appreciated)

The program is documented only by comments inside; the only features which may
not be obvious are command-line options to create a game record,
and to play on a range of board sizes, with or without handicap stones.

As noted in the comments, the program is copyrighted but freely available
for not-for-profit use, such as anyone can find for it.
The program is unlikely to hold the interest of a human opponent very long,
especially since it plays an obnoxious endgame, singlemindedly throwing in
to the enemy's territory whenever it sees the opportunity to keep the
opponent from making the maximum number of eyes.  However, it
might be of interest
to programmers wondering how far you can get with a simple pattern-matching
program, or just looking for more patterns for their tables; most of the
patterns in the program's table (all those not in Millen's article) are 
original with me; I started with Millen's shape table,
then spent several hours playing against the program (mostly on a 9x9 
board with 4-stone handicap) and changing the table to keep the program
from doing unnecessarily stupid things.  

The source code to the program follows the dotted line, and
continues to the end of the file.  The program compiles and
runs with cc under SunOS 4.0.3 and and with Mark Williams C 3.0 on
an Atari 520 ST.

  Bill Newman
  newman@tcgould.tn.cornell.edu

------------------------------------------------------------------------  
*/

/*
wally.c, a go playing program
Copyright (c) 1988 by William H. Newman and distributed as shareware:
 permission is granted for all non-profit use of the program as
 long as this notice is included.
Send comments to box 172 Cornell U, Ithaca NY 14850, or e-write
 to newman@batcomputer.tn.cornell.edu.  
This program was inspired by ideas published by Jonathan K. Millen in BYTE,
 April 1981.  Because an Atari ST is somewhat more powerful than a KIM-1,
 I have been able to make the program somewhat more sophisticated.
 However, it still plays very naive go.  (30 kyu?)

Notable flaws:
  no lookahead
  no knowledge of live or dead shape
  takes advantage of a series of opponent's passes @ the start of the game
    rather poorly; this points up flaws in the shape table
  no rules to stop the program from making obnoxious but pointless moves
    in the endgame; it ought not to once it has passed once.  Maybe turn
    off pattern matching completely after the program's first pass move.

#ifdef  ADDED
  Three new options:

  -d  turns on debugging output
  -mgt  writes the output record in a form suitable for mgt
  -cat  writes the output record in a form suitable for cat ... | wally

  The game score is printed even in the case of a resignation.

  <-xtx-*>	cc -o wally -O -DADDED wally.c

  Added by Kevin Stock, kstock@encore.fr, 12th July 1990
#endif

*/


#include <stdio.h>
/* #include <string.h>  */
#include <strings.h>

#ifdef  ADDED
# define  PATCHLEVEL	2

# define  WALLY_OUTPUT  0
# define  MGT_OUTPUT    1
# define  CAT_OUTPUT    2

# define  M_LETTER(x)	\
	((x < 8) ? lettercol(x) : ((x == 8) ? 'i' : lettercol(x - 1)))

  int outputmode = WALLY_OUTPUT;
#endif

#define ASSERT 1	/*flag for whether assert() macros should be */
			/* expanded*/

#define BIGU 10000	/*a number higher than any meaningful "urgency" */
			/* or move importance*/

#define RESIGN (-2)	/*codes for resigning */
#define PASS (-1)	/* passing moves*/
#define BOTHPASS (-3)	/*code for both sides passed, game is over*/

#define EDGE 23		/*max # intersections on the edge of a go board*/
int edge= 9;		/*the number of intersections which we are using (a */
			/* command line parameter)*/

#define NPLAYERS 2	/*# players (hence # copies to keep of score &c.)*/

int debugattack= 0;	/*flag for printing debugging messages in attack()*/

/*Return the absolute value of i.*/
#define abs(i) ((i)>=0?(i):-(i))

/*Return TRUE if (x,y) corresponds to a point on the board.*/
#define on1board(x) (0<=(x)&&(x)<edge)
#define onboard(x,y) (on1board(x)&&on1board(y))

/*Return TRUE if (x,y) is on the edge of the board.*/
#define onedge1(x) (0==(x)||edge-1==(x))
#define onedge(x,y) (onedge1(x)||onedge1(y))

/*codes for players; and a code for something (e.g. a point on the board) */
/* which belongs to neither*/
#define BLACK 0
#define WHITE 1
#define EMPTY 2
/*flags in shape table entries for types of points*/
#define F_BLACK 1	/*the point has a black stone*/
#define F_WHITE 2	/*the point has a white stone*/
#define F_EMPTY 4	/*the point is empty*/
#define F_OFF   8	/*the point is off the board*/
int flookup[]=	/*sets of flags corresponding to codes*/
{ F_BLACK, F_WHITE, F_EMPTY };

int evenmode= 0;	/*Are we (against our better judgment) to play */
			/* an even game?*/

/*Return TRUE if a move violates ko.*/
#define ko(x,y) (thegame.kox==(x)&&thegame.koy==(y))

/*Return the code for the other player, who is the next to play.*/
#define nextp(p) (BLACK==(p)?WHITE:WHITE==(p)?BLACK:\
	panic("illegal input to nextp()"))

/*Return a letter corresponding to column x; 'i' is omitted from letter */
/* sequence by tradition.*/
#define lettercol(x) (							\
	  (0<=(x)&&(x)<=7) ? 'a'+(x) : (7<(x)&&(x)<edge) ? 'a'+(x)+1 :	\
	  panic("illegal lettercol()") )

/*Convert any uppercase letter to lowercase.*/
#define lowercase(c) ('A'<=(c)&&(c)<='Z'?(c)-'A'+'a':(c))

/*Return a string naming BLACK or WHITE.*/
char whitename[]="white", blackname[]="black";
#define pname(c) (BLACK==(c)?blackname:WHITE==(c)?whitename:\
	(panic("illegal input to pname()"),""))

/*Return TRUE if a move would leave the group it creates or attaches to */
/* in atari or dead.*/
#define intoatari(x,y) (subj_lib(x,y)<=1)

/*a macro to abort the program if a test is not successful*/
#if ASSERT
#define assert(q) ((q)?1:(fprintf(stderr, \
"\n?!panic--failed assert() @ %s %d.\n", \
 __FILE__, __LINE__), fflush(stderr),exit(1)))
#else
#define	assert(q)
#endif

/*ASCII character codes*/
#define TAB 8


/*name of and pointer to output file*/
char *ofname;
FILE *ofile= 0;

/*name program uses for itself*/
char *progname= "Wally";
char version[]= "2.1";

/*a struct for holding information on every square of the board*/
typedef int board[EDGE][EDGE];

/*current position of stones on the board*/
board theboard;

/*other information about the game*/
struct thegame
{ int kox, koy;		/*coords of current ko, or negative for none*/
  int pla;		/*code for next player to play*/
  int tur;		/*the number of this move*/
  int qpa;		/*flag for the last move was a pass, so that if this */
			/* move is a pass, that's all folx*/
} thegame;

typedef struct group
{ int	color,		/*the color of stones in this group*/
	nliberties,	/*the number of liberties that this group has*/
	nstones,	/*the number of stones in this group*/
	x, y;		/*one point in this group*/
} group;
group groups[EDGE*EDGE]; /*(EDGE*EDGE is a lazy bound; the number of groups */
			/* of groups must be less than number of points)*/
int ngroups;

/*handicap stones for the 3 common board sizes*/
int handi9[]= { 2, 2,	6, 2,	2, 6,	6, 6 } ;
int handi13[]= { 2, 2,	2, 6,	2, 10,	
		 6, 2,	6, 6,	6, 10,
		10, 2,	10, 6, 	10, 10 } ;  
#if 0
int handi19[]= { 15, 3, 15, 6,	15, 9,	15, 12,	15, 15,
		 12, 3,				12, 15,
		 9,  3,		9, 9,		9, 15,
		 6, 3, 				6, 15,
		 3, 3,	3, 6,	3, 9,	3, 12,	3, 15 } ;
#else
int handi19[]= { 15, 3, 	15, 9,		15, 15,
		 9,  3,		9, 9,		9, 15,
		 3, 3,		3, 9,		3, 15 } ;
#endif

int nhandicap[]=
{ 0, 0, 0, 0, 0,
  0, 0, 0, 0, sizeof(handi9)/(2*sizeof(int)),
  0, 0, 0, sizeof(handi13)/(2*sizeof(int)), 0,
  0, 0, 0, 0, sizeof(handi19)/(2*sizeof(int))
} ;
int *handicap[]=
{ 0, 0, 0, 0, 0,
  0, 0, 0, 0, handi9,
  0, 0, 0, handi13, 0, 
  0, 0, 0, 0, handi19
} ;

/*a table of moves which seem to make "good shape" for the computer, */
/* or which defend against a particularly common threat that the program */
/* can't understand without lookahead, or which act as primitive joseki*/
#define PATTERN 12345	/*This integer should appear at the start of each */
		/* pattern.  If it doesn't, someone has made a typographical */
		/* error.*/
#define PATTEND 7171	/*This integer should appear at the end of the table.*/
int patterns[]=
{  PATTERN,	/*a code for the beginning of a pattern*/
   4, 24,	/*Three points, basic urgency 24.  Urgency is highest */
		/* for lower numbers.  Original values: */
		/*   capturing an enemy group=16, */
		/*   defending one of ours= 20, */
		/*   atariing an enemy group= 32 */
  -1, 0, F_BLACK|F_OFF, /*Recognize the pattern by black stone at (x-1, y+0) */
		/* or that point off the board, */
   1, 0, F_BLACK,  /* a black stone at (x+1, y+0), and */
   0, -1, F_WHITE, /* a white stone at (x+0, y-1), and */
   0, 1, F_EMPTY|F_WHITE, /* a white stone or space at (x, y+1), */
	/* that is: */	/*   ~   */
			/* ~ $ # */
			/*   O   */

  PATTERN, 3, 22,	/* # $   */
  -1, 0, F_BLACK,	/*   O # */
   1, -1, F_BLACK,
   0, -1, F_WHITE,

  PATTERN, 5, 26,	/* # O # */
  -1, 1, F_BLACK|F_OFF,	/*   $ . */
   1, 1, F_BLACK,	/*       */
   0, 1, F_WHITE,	/*   ~   */
   1, 0, F_EMPTY,
   0, -3, F_EMPTY|F_WHITE,	/*This so that we don't get trapped in */
			/* an extremely common pattern against the edge */
			/* of the board, or in a shicho.*/

  PATTERN, 4, 26,	/* # O # */
  -1, 1, F_BLACK|F_OFF,	/*   $ # */
  1, 1, F_BLACK,
  1, 0, F_BLACK,
  0, 1, F_WHITE,

  PATTERN, 6, 24,	/*   ~     */
  -1, 0, F_BLACK,	/* # $ . # */ 
  0, -1, F_WHITE,	/*   O     */
  1, 0,  F_EMPTY,
  1, -1, F_EMPTY,
  2, 0,  F_BLACK,
  0, 1, F_EMPTY|F_WHITE,

  PATTERN, 5, 27,	/*   ~     */
  -1, 0, F_BLACK,	/* # $ . ~ */ 
  0, -1, F_WHITE,	/*   O     */
  1, 0,  F_EMPTY,
  2, 0,  F_OFF,
  0, 1, F_EMPTY|F_WHITE,

  PATTERN, 5, 24,	/* # . $ . # */
  -2, 0, F_BLACK,	/*     O     */
  -1, 0, F_EMPTY,
  0, -1, F_WHITE,
  1,  0, F_EMPTY,
  2,  0, F_BLACK,

  PATTERN, 5, 30,	/*  # . $ . ~  */
  -2, 0, F_BLACK,	/*      O      */
  -1, 0, F_EMPTY,
  0, -1, F_WHITE,
  1,  0, F_EMPTY,
  2,  0, F_OFF,

  PATTERN, 7, 26,		/*    ~ .    */
   -1, 0, F_BLACK,		/*  # $ # O  */
   1, -1, F_WHITE,		/*    ~ O    */
   1, 0, F_BLACK,
   2, 0, F_WHITE,
   1, 1, F_EMPTY,
   0, 1, F_EMPTY|F_WHITE,
   0, -1, F_EMPTY|F_WHITE,

  PATTERN, 8, 26,		/*  ~ # O  */
  -1, -1, F_BLACK|F_EMPTY,	/*  # . $  */
  -2, 0, F_BLACK,		/*  ~ ~ ~  */
  -1, 0, F_EMPTY,
  -1, 1, F_BLACK,
   0, 1, F_WHITE,
   0, -1, F_BLACK|F_EMPTY,
  -2, -1, F_BLACK|F_EMPTY,  
  -2, 1, F_BLACK|F_EMPTY,

  PATTERN, 4, 26,	/*   .   */
  0, 2,  F_EMPTY,	/* #   # */
  -1, 1, F_BLACK,	/*   $ O */
  1, 1,  F_BLACK,
  1, 0,  F_WHITE,

  PATTERN, 4, 24,	/*   .   */
  0, 1, F_EMPTY,	/*   $   */
  -1, -1, F_WHITE,	/* O # O */
  0, -1, F_BLACK,
  1, -1, F_WHITE,

  PATTERN, 4, 24,	/*   .   */
  0, 1, F_EMPTY,	/*   $ O */
  -1, -1, F_WHITE,	/* O #   */
  0, -1, F_BLACK,
  1, 0, F_WHITE,

  PATTERN, 4, 26,	/*   O   */
  0, 1, F_EMPTY,	/* O . O */
  -1, 1, F_WHITE,	/*   $   */
  1, 1, F_WHITE,
  0, 2, F_WHITE,

  PATTERN, 8, 24,	  /*     O   */
  -2, 0, F_EMPTY|F_BLACK, /* ~ $ # O */
  0, -1, F_EMPTY,	  /*   . . . */
  1, -2, F_OFF,		  /*     ~   */
  1, -1, F_EMPTY,
  1, 0, F_BLACK,
  1, 1, F_WHITE,
  2, -1, F_EMPTY,
  1, 0, F_WHITE,

  PATTERN, 8, 28,	/* . # O   */
  -1, 0, F_EMPTY,	/* . $ # O */
  0, -1, F_EMPTY,	/*   . .   */
  0, 1, F_BLACK,
  1, 0, F_BLACK,
  1, 1, F_WHITE,
  2, 0, F_WHITE,
  -1, 1, F_EMPTY,
  1, -1, F_EMPTY,

  PATTERN, 8, 23,	/*   # #   */
  0, 2, F_BLACK,	/*   .   # */
  1, 2, F_BLACK,	/* ~ $ . # */
  2, 0, F_BLACK,	/*   ~     */
  2, 1, F_BLACK,
  1, 0, F_EMPTY,
  0, 1, F_EMPTY,
  -1, 0, F_EMPTY|F_BLACK|F_WHITE,
  0, -1, F_EMPTY|F_WHITE,

  PATTERN, 8, 24,	/*   O O   */
  0, 2, F_WHITE,	/*   .   O */
  1, 2, F_WHITE,	/* ~ $ . O */
  2, 0, F_WHITE,	/*   ~     */
  2, 1, F_WHITE,
  1, 0, F_EMPTY,
  0, 1, F_EMPTY,
  -1, 0, F_EMPTY|F_WHITE|F_BLACK,
  0, -1, F_EMPTY|F_BLACK,

  PATTERN, 8, 34,	/* ~ # # */
  -1, 1, F_BLACK,	/* # . # */
  -1, 0, F_BLACK,	/* # $   */
  0, 2, F_BLACK,	/*   ~   */
  0, 1, F_EMPTY,
  1, 1, F_BLACK,
  1, 2, F_BLACK,
  -1, 2, F_BLACK|F_EMPTY,
  0, -1, F_WHITE|F_EMPTY,

  PATTERN, 7, 34,		/* ~ # ~ */
  -1, 1, F_BLACK,		/* # . # */
  -1, 0, F_BLACK|F_EMPTY,	/* ~ $   */
  -1, 2, F_BLACK|F_EMPTY,
  0, 2, F_BLACK,
  0, 1, F_EMPTY,
  1, 1, F_BLACK,
  1, 2, F_BLACK|F_EMPTY,

  PATTERN, 10, 27,	/*   . . .   */	/*(This is Wally's fuseki for */
  -2, 0, F_BLACK,	/* # . $ . # */	/* a 9 x 9 board with 4 handicap */
  2, 0, F_BLACK,	/*   . . .   */	/* stones.)*/
  -1, 0, F_EMPTY,
  1, 0, F_EMPTY,
  -1, 1, F_EMPTY,
  0, 1, F_EMPTY,
  1, 1, F_EMPTY,
  -1, -1, F_EMPTY,
  0, -1, F_EMPTY,
  1, -1, F_EMPTY,

  PATTERN, 6, 25,	/*     # . #   */
  -1, 1, F_BLACK,	/*   ~ . $     */
  -1, -1, F_BLACK,	/*     #       */
  1, 1, F_BLACK,
  0, 1, F_EMPTY,
  -1, 0, F_EMPTY,
  -2, 0, F_EMPTY|F_BLACK|F_OFF,
 
  PATTERN, 5, 35,	/*     O #   */
  -1, 0, F_EMPTY,	/*   . $ ~   */
  0, 1, F_WHITE,	/*     ~     */
  1, 1, F_BLACK,
  0, -1, F_OFF,
  0, 1, F_BLACK|F_EMPTY,

  PATTERN,  5, 40,	/*   O #     */
  -1, 0, F_EMPTY,	/*   . $ ~   */
  -1, 1, F_WHITE,	/*     ~     */
  0, 1, F_BLACK,
  0, -1, F_OFF,
  1, 0, F_WHITE|F_EMPTY,

  PATTERN, 6, 38,	/*   O . #   */
  -1, 1, F_WHITE,	/*     $ .   */
  1, 1, F_BLACK,	/*     .     */
  0, 1, F_EMPTY,	/*     ~     */
  1, 0, F_EMPTY,
  0, -1, F_EMPTY,
  0, -2, F_OFF|F_BLACK,

  PATTERN, 6, 38,	/*     . #   */
  -1, 0, F_WHITE,	/*   O $ .   */
  1, 1, F_BLACK,	/*     .     */
  0, 1, F_EMPTY,	/*     ~     */
  1, 0, F_EMPTY,
  0, -1, F_EMPTY,
  0, -2, F_OFF|F_BLACK,

/*
some patterns for a 19 x 19 board, which is a little different from
the high handicap 9 x 9 game this program originally played
*/

  PATTERN, 11, 29,	  /*     O   */
  -2, 0, F_EMPTY|F_BLACK, /* ~ $ # O */
  0, -1, F_EMPTY,	  /*   . . . */
  1, -2, F_OFF,		  /*   ~ ~ ~ */
  1, -1, F_EMPTY,	  /*     ~   */
  1, 0, F_BLACK,
  1, 1, F_WHITE,
  2, -1, F_EMPTY,
  -1, -2, F_EMPTY|F_OFF,
  0, -2, F_EMPTY|F_OFF,
  1, -2, F_EMPTY|F_OFF,
  1, 0, F_WHITE,

  PATTERN, 12, 38,	/*     ~ #   */
  -1, 0, F_WHITE,	/*   O $ ~ ~ */
  1, 1, F_BLACK,	/*     ~ ~ ~ */
  0, 1, F_EMPTY|F_BLACK,/*     ~ ~ ~ */
  1, 0, F_EMPTY|F_WHITE,/*     ~     */
  0, -3, F_OFF,
  0, -1, F_EMPTY|F_BLACK,
  0, 2,  F_EMPTY|F_BLACK|F_OFF,
  1, -1, F_EMPTY|F_BLACK|F_OFF,
  2, -1, F_EMPTY|F_BLACK|F_OFF,
  0, -2, F_EMPTY|F_BLACK|F_OFF,
  1, -2, F_EMPTY|F_BLACK|F_OFF,
  2, -2, F_EMPTY|F_BLACK|F_OFF,

  PATTERN, 12, 38,	/*     # ~   */
  -1, 0, F_WHITE,	/*   O $ ~ ~ */
  0, 1, F_BLACK,	/*     ~ ~ ~ */
  1, 1, F_EMPTY|F_BLACK,/*     ~ ~ ~ */
  1, 0, F_EMPTY|F_WHITE,/*     ~     */
  0, -3, F_OFF,
  0, -1, F_EMPTY|F_BLACK,
  0, 2,  F_EMPTY|F_BLACK|F_OFF,
  1, -1, F_EMPTY|F_BLACK|F_OFF,
  2, -1, F_EMPTY|F_BLACK|F_OFF,
  0, -2, F_EMPTY|F_BLACK|F_OFF,
  1, -2, F_EMPTY|F_BLACK|F_OFF,
  2, -2, F_EMPTY|F_BLACK|F_OFF,

/*
Let's not just pass when confronted by
an empty 19 x 19 board.. hence the following patterns
*/

  PATTERN, 15, 25,	/*           ~     */
  0, 1, F_EMPTY,	/*           ~ ~   */
  0, 2, F_EMPTY,	/*     . . .       */
  1, 0, F_EMPTY,	/*   . . . . 	   */
  1, 1, F_EMPTY,	/*   . $ . . 	   */
  1, 2, F_EMPTY,	/*     . .	   */
  2, 0, F_EMPTY,
  2, 1, F_EMPTY,
  2, 2, F_EMPTY,
  4, 3, F_OFF,
  3, 4, F_OFF,
  -1, 0, F_EMPTY,
  -1, 1, F_EMPTY,
  0, -1, F_EMPTY,
  1, -1, F_EMPTY,
  3, 3, F_EMPTY|F_WHITE|F_BLACK,

  PATTERN, 10, 29,
  -1, 0, F_EMPTY,	/*         ~     */
  -1, 1, F_EMPTY,	/*         ~ ~   */
  0, -1, F_EMPTY,	/*   . . .  	 */
  1, -1, F_EMPTY,	/*   . $ .  	 */
  0, 1, F_EMPTY,	/*     . .	 */
  1, 0, F_EMPTY,
  1, 1, F_EMPTY,
  2, 2, F_EMPTY|F_WHITE|F_BLACK,
  3, 2, F_OFF,
  2, 3, F_OFF,

  PATTERN, 17, 29,	/*     . . .          */
  0, 1, F_EMPTY,	/*     . . .          */
  0, -1, F_EMPTY,	/*   ~ . $ .   ~ ~    */
  1, 0, F_EMPTY,	/*     . . .          */
  -1, 0, F_EMPTY,	/*     . . .          */
  1, 1, F_EMPTY,
  1, -1, F_EMPTY,
  -1, 1, F_EMPTY,
  -1, -1, F_EMPTY,
  -1, 2, F_EMPTY,
  0, 2, F_EMPTY,
  1, 2, F_EMPTY,
  -1, -2, F_EMPTY,
  0, -2, F_EMPTY,
  1, -2, F_EMPTY,
  3, 0, F_WHITE|F_BLACK|F_EMPTY,
  4, 0, F_OFF|F_BLACK,
  -2, 0, F_WHITE|F_EMPTY,
  

  PATTERN, 12, 31,	/*     . . .     */
  0, 1, F_EMPTY,	/*     . $ .     */
  0, -1, F_EMPTY,	/*   ~ . . . ~   */
  1, 0, F_EMPTY,	/*	 ~	 */
  -1, 0, F_EMPTY,	/*       ~       */
  1, 1, F_EMPTY,
  1, -1, F_EMPTY,
  -1, 1, F_EMPTY,
  -1, -1, F_EMPTY,
  -2, -1, F_EMPTY|F_BLACK,
  2, -1, F_EMPTY|F_BLACK,
  0, -2, F_EMPTY|F_BLACK|F_WHITE,
  0, -3, F_OFF,

  PATTERN, 22, 33,	/*   ~ ~ #       */
  0, 1, F_EMPTY,	/*   . . . . .   */
  0, -1, F_EMPTY,	/*   . . $ . .   */
  1, 0, F_EMPTY,	/*   . . . . .   */
  -1, 0, F_EMPTY,	/*   . . . . .   */
  1, 1, F_EMPTY,
  1, -1, F_EMPTY,
  -1, 1, F_EMPTY,
  -1, -1, F_EMPTY,
  2, -2, F_EMPTY,
  -2, -2, F_EMPTY,
  0, 2, F_BLACK,  
  0, -2, F_EMPTY,  
  2, 0, F_EMPTY,  
  -2, 0, F_EMPTY,  
  2, 1, F_EMPTY,
  2, -1, F_EMPTY,
  -2, 1, F_EMPTY,
  -2, -1, F_EMPTY,
  1, -2, F_EMPTY,
  -1, -2, F_EMPTY,
  -1, 2, F_EMPTY|F_WHITE,
  -2, 2, F_EMPTY|F_WHITE,

  PATTEND
};

/*a variable for debugging -- records the number of the pattern the */
/* program thinks it has matched, so when the program makes a bizarre */
/* move and claims that this helps it make shape, I can see what pattern */
/* has gone wrong*/ 
int patnum;

/*Where did the enemy last move?  This is used to help decide which patterns */
/* are most important (try to leech off enemy's greater expertise).*/
int lex, ley;

/*
a table of moves the heuristics are ambivalent about, for 
random selection
*/
int goodmoves[2*EDGE*EDGE];
int *pgoodmoves;	/*&next free space in goodmoves[]*/

fatal(message) char *message;
/*Print an error message and abort program.*/
{ fprintf(stderr, "\n?!fatal error--%s\n", message);
  /* *(int*)3; *//*Force a bus error so that Mark Williams C debugger works.*/
  exit(1);
}


panic(message) char *message;
/*Fatal error routine reserved for error conditions that ought not happen.*/
{ fprintf(stderr, "\n?!panic--%s\n", message);
  exit(1);
}


int rng(n)  int n;
/*Return a (slightly) random number from 0 to n-1.*/
/*(This is a really crummy rng, it just keeps the 
/*program's moves from all lying in a trivial pattern.)*/
{ static int seed= 0x1231;
  int r;
  seed= (seed*11+15) & 0x7FFF;
  r= (((long)seed)*n)/(0x7FFF+1);
  return r;
}


printgame()
/*
Output the game board theboard (with ko info from thegame) to the console.
Currently the style is:

   a b c d e f g h j
 1 . . . . . . . . . 1
 2 . . . . . O O . . 2
 3 . . O . . . # . . 3
 4 . . O . . . # . . 4
 5 O O ^ O . . . . . 5
 6 . # O # . # # . . 6
 7 . # # # . . . . . 7
 8 . . . . . . . . . 8
 9 . . . . . . . . . 9
   a b c d e f g h j

where '^' is a ko, '#' is black, 'O' is white.
*/
{ register int x, y;

  printf("\n  ");
  for(x=0; x<edge; ++x)
    printf(" %c", lettercol(x));
  printf("\n");
  for(y=0; y<edge; ++y)
  { printf("%2d ", 1+y);
    for(x=0; x<edge; ++x)
    { register int here= theboard[x][y];
      printf( x!=(edge-1)?"%c ":"%c", 
		(thegame.kox==x&&thegame.koy==y) ? '^' :
		(EMPTY==here) ? '.' :
		(WHITE==here) ? 'O' :
		(BLACK==here) ? '#' :
		panic("illegal board type in printboard()"));
    }
    printf(" %-2d\n", 1+y);
  }
  printf("  ");
  for(x=0; x<edge; ++x)
    printf(" %c", lettercol(x));
  printf("\nGame turn= %d.  %s to play.\n",
	thegame.tur, pname(thegame.pla));
}


initgame()
{ register int x, y, j, *h;

/*Clear the board.*/
  for(x=0; x<edge; ++x)  for(y=0; y<edge; ++y)  
    theboard[x][y]= EMPTY;

/*Initialize miscellaneous other stuff.*/
  thegame.kox= thegame.koy= (-1);
  thegame.tur= 1;
  if(edge<sizeof(nhandicap)/sizeof(int) && nhandicap[edge]) 
    thegame.pla= WHITE;
  else
    thegame.pla= BLACK;
  thegame.qpa= 0;
  lex= ley= (-1000);	/*nothing is near the enemy's last move*/

  if(edge<=sizeof(nhandicap)/sizeof(int)) /*If handicap defined for this board*/
  { if(ofile&&nhandicap[edge])
#ifdef  ADDED
    switch (outputmode)
    {
    case WALLY_OUTPUT:
#endif
      fprintf(ofile, "handicap= %d:  ", nhandicap[edge]);
#ifdef  ADDED
      break;

    case MGT_OUTPUT:
      fprintf(ofile, "AddBlack");
      break;

    /* nothing to send for CAT_OUTPUT */
    }
#endif
    for(h=handicap[edge],j=nhandicap[edge]; j; --j)
    { x= *h++;
      y= *h++;
      assert(onboard(x,y));
      assert(EMPTY==theboard[x][y]);
      theboard[x][y]= BLACK;
#ifdef  ADDED
      if (ofile)
      {
        switch (outputmode)
        {
        case WALLY_OUTPUT:  /* should agree with #else below */
          fprintf(ofile, "%c%d ", lettercol(x), 1+y);
          break;

        case MGT_OUTPUT:
          fprintf(ofile, "[%c%c]", M_LETTER(x), M_LETTER(y));
          break;

        /* nothing to send for CAT_OUTPUT */
        }
      }
#else
      if(ofile) fprintf(ofile, "%c%d ", lettercol(x), 1+y);
#endif
    }
#ifdef  ADDED
    if (ofile)
    {
      switch (outputmode)
      {
      case WALLY_OUTPUT:  /* should agree with #else below */
        fprintf(ofile, "\nboard= %d x %d\n", edge, edge);
        break;

      case MGT_OUTPUT:
        fputc('\n', ofile); /* boardsize sent earlier */
        break;

      /* nothing to send for CAT_OUTPUT */
      }
    }
#else
    if(ofile) fprintf(ofile, "\nboard= %d x %d\n", edge, edge);
#endif
  }

}


sremove(x, y)  register int x, y;
/*
Recursively sremove the stone at (x,y) and all stones in the same group
from the board.
*/
{ register int color;
  assert(onboard(x,y));
  color= theboard[x][y];
  assert(BLACK==color||WHITE==color);
  theboard[x][y]= EMPTY;

  if(onboard(x, y+1) && color==theboard[x][y+1])
    sremove(x, y+1);
  if(onboard(x, y-1) && color==theboard[x][y-1])
    sremove(x, y-1);
  if(onboard(x+1, y) && color==theboard[x+1][y])
    sremove(x+1, y);
  if(onboard(x-1, y) && color==theboard[x-1][y])
    sremove(x-1, y);
}


int capture(p, capx, capy)  int p, *capx, *capy;
/*
Remove all of player p's dead stones (as implied by results of makegroups())
from the board.  Return # stones removed.  If any stones are removed, 
theboard[][] is left inconsistent with groups[].
*capx and *capy are set to the coordinates of a captured stone, if any, 
so that if only one stone is captured, they may be used to set ko.
*/
{ register int j, rv=0;
  register group *g;
  for(g=groups,j=0; j<ngroups; ++g,++j)
    if(p==g->color&&0==g->nliberties)
    { rv += g->nstones; 
      *capx= g->x; 
      *capy= g->y;
      sremove(g->x, g->y);
    }
  return rv;
}


int colletter(letter)  register int letter;
/*
Return the column # (0 to edge-1) which corresponds to letter.
Due to perversity of tournament organizers etc., 'i' or 'I' is 
omitted, leading to an increase in complexity of this routine.
Return (-1) on illegal input.
*/
{ register int result;

  if('a'<=letter&&letter<='z') 
    result= letter-'a';
  else if('A'<=letter&&letter<='Z') 
    result= letter-'A';
  else
    return (-1);

  if(8>result)
    ;
  else if(8==result)
    return (-1);
  else
    --result;
  
  if(result>=edge)
    return (-1);
  else
    return result;
}


int getnb()
/*Read and return the first nonblank character from the standard input.*/
{ int c;
  do
    c= getchar();
  while(' '==c||'\n'==c||TAB==c);
  return c;
}


int scanfcoo(x, y)  int *x, *y;
/*
Read a coordinate from the standard input and write it to *x and *y.  Like
scanf, return 1 for success, 0 for failure, negative numbers for special
moves, e.g. PASS and RESIGN. 
On any input error, the function eats input up to the next newline.
*/
{
  int xx, yy, c1, c2;

/*Get first nonblank character of input, normally a letter code for a column.*/
  c1= getnb();

/*Check for possible resignation (a '.' at the start of the input).*/
  if('.'==c1)
  { while('\n'!=getchar())	/*Skip to end of line.*/
      ;
    return RESIGN;
  }

/*Check for possible "pass".*/
  if('p'==lowercase(c1))
  { c2= getchar();
    if('a'!=lowercase(c2))
      ungetc(c2, stdin);
    else
    { if((c2=getchar(),'s'!=lowercase(c2))||(c2=getchar(),'s'!=lowercase(c2)))
      { ungetc(c2, stdin);
	goto skipquit;
      }
      else
        return PASS;
  } } 
  xx= colletter(c1);
  if(1!=scanf("%d", &yy))
  {
skipquit:	/*Skip to the next newline and return failure.*/
    while('\n'!=getchar()) 
      ;
    return 0;
  }
  if(0==onboard(xx,yy-1))	/*The -1 converts between C arrays starting */
				/* at 0 and human boards counting from 1.*/
    goto skipquit;
  else
  { *x= xx;
    *y= yy-1;
    return 1;
  }
}


movedone()
/*
Do everything which must be done to complete a move after the stone is 
placed.
*/
{ thegame.pla= nextp(thegame.pla);  ++thegame.tur; }


count(x, y, thisgroup, scratch, mark)  
register int x, y;  register group *thisgroup;  board scratch;  int mark;
/*
Recursively group together connected stones.  Three things must be done:
  (1) count liberties in thisgroup->nliberties,
  (2) count stones in thisgroup->nstones, and
We set scratch[][]= mark for each point and liberty of this group, 
  so that we only count each only once.  The calling routine must
  see to it that scratch[][]!=mark for all points and liberties that
  it wants counted.
*/
{ register int *bxy, *sxy; /*Common subexpressions to reduce array */
  		/* arithmetic; they point to theboard[x][y] and scratch[x][y].*/

endrecurse:
  assert(onboard(x,y));
  assert(thisgroup->color==theboard[x][y]);
  assert(thisgroup->nstones>=0);
  assert(thisgroup->nliberties>=0);
  assert(mark!=scratch[x][y]);

	/*Set common subexpressions.*/
  bxy= &(theboard[x][y]);
  sxy= &(scratch[x][y]);

	/*Count the point (x,y) and make it a member of the group.*/
  ++(thisgroup->nstones);
  *sxy= mark;

	/*"Process" (x, y-1): should it be in the group, or a liberty, or */
	/* nothing?*/
  y= y-1;
  bxy -= 1;
  sxy -= 1;
  assert(&theboard[x][y]==bxy);
  assert(&scratch[x][y]==sxy);
  if(y>=0)
    if(thisgroup->color==*bxy)
    { if(*sxy!=mark)
        count(x, y, thisgroup, scratch, mark);
    }
    else if(EMPTY==*bxy)
    { if(*sxy!=mark)
      { *sxy=mark;
	++(thisgroup->nliberties);
    } }

	/*Process (x, y+1).*/
  y= y+2;
  bxy += 2;
  sxy += 2;
  assert(&theboard[x][y]==bxy);
  assert(&scratch[x][y]==sxy);
  if(y<edge)
    if(thisgroup->color==*bxy)
    { if(*sxy!=mark)
        count(x, y, thisgroup, scratch, mark);
    }
    else if(EMPTY==*bxy)
    { if(*sxy!=mark)
      { *sxy=mark;
	++(thisgroup->nliberties);
    } }

	/*Process (x-1, y).*/
  y= y-1;
  x= x-1;
  bxy -= EDGE+1;
  sxy -= EDGE+1;
  assert(&theboard[x][y]==bxy);
  assert(&scratch[x][y]==sxy);
  if(x>=0)
    if(thisgroup->color==*bxy)
    { if(*sxy!=mark)
        count(x, y, thisgroup, scratch, mark);
    }
    else if(EMPTY==*bxy)
    { if(*sxy!=mark)
      { *sxy=mark;
	++(thisgroup->nliberties);
    } }

	/*Process (x+1, y).*/
  x= x+2;
  bxy += 2*EDGE;
  sxy += 2*EDGE;
  assert(&theboard[x][y]==bxy);
  assert(&scratch[x][y]==sxy);
  if(x<edge)
    if(thisgroup->color==*bxy)
    { if(*sxy!=mark)
        goto endrecurse;
    }
    else if(EMPTY==*bxy)
    { if(*sxy!=mark)
      { *sxy=mark;
	++(thisgroup->nliberties);
    } }

}


makegroups()
/*Analyzes groupings of stones on board; sets groups[].*/
{ 
  register int x, y;	/*coords of point we are now assigning to a group*/
  board scratch;	/*scratch for count() to use to say if a point is */
			/* already counted*/

	/*Clear old groups[] table and scratch[][].*/
  ngroups= 0;
  { register int *s;
    for(s=scratch[0],x=0; x<EDGE*EDGE; ++x)
      *s++= 0;
  }

	/*Go through board[][] point by point.  Group any stone which has not */
	/* already been grouped (as indicated by negative scratch[][]).*/
  { register int *bxy= (int*)theboard, *sxy= (int*)scratch;
    register group *thisgroup=groups; 
    for(x=0; x<edge; ++x,bxy+=EDGE-edge,sxy+=EDGE-edge)  
      for(y=0; y<edge; ++y,++bxy,++sxy)
      { assert(&(theboard[x][y])==bxy);
	assert(&(scratch[x][y])==sxy);
	assert(&(groups[ngroups])==thisgroup);
        if((BLACK==*bxy||WHITE==*bxy) && 0==*sxy)
        { thisgroup->color= *bxy;
          thisgroup->x= x;
          thisgroup->y= y;
          thisgroup->nliberties= 0;
          thisgroup->nstones= 0;
          count(x, y, thisgroup, scratch, 1+thisgroup-groups);
          ++thisgroup;
          ++ngroups;
        } 
      }
  }
}


placestone(x, y, p)  int x, y, p;
/*
Put a stone for player p at (x,y) and sremove all the captures which result.
Update ko information.
*/
{ int ncap, capx, capy;
  assert(onboard(x, y));
  assert(BLACK==p||WHITE==p);
  assert(EMPTY==theboard[x][y]);

  theboard[x][y]= p;
  makegroups();				/*Group all stones and count libs.*/
  ncap= capture(nextp(p), &capx, &capy);/*Remove p's opponent's dead stones.*/
  thegame.kox= thegame.koy= (-1);	/*Cancel any old ko.*/
  if(1==ncap)	/*If exactly one stone was captured, check for new ko.*/
  { register int j, *ip;  group g;
    board scratch;
    for(ip=(int*)scratch,j=EDGE*EDGE; j--; ) *ip++= 0;
    g.color= theboard[x][y];
    g.nstones= 0;
    g.nliberties= 0;
    g.x= x;
    g.y= y;
    count(x, y, &g, scratch, 1); /*Count stones and libs for capturing group.*/
    if(1==g.nstones && 1==g.nliberties)	/*If c.g. is a single stone in atari */
    { thegame.kox= capx; thegame.koy= capy; } /* then ko, so mark it.*/
  }
  if(ncap)		/*If any enemy stones were removed, */
    makegroups();	/* recalculate the board.*/
  ncap= capture(p, &capx, &capy);/*Remove any still-trapped stones (suicide).*/
  assert(WHITE==p||0==ncap);	/*Wally knows not to make suicides.*/
}



sortv(p, n)  group **p;  int n;
/*
Sort the table p[] or pointers to groups in order of vulnerability, 
most vulnerable first.
Currently this is the slow simple bubble sort we all know.
*/
{ register int uns;	/*flag that an unsorted pair was found last pass*/
  register group *t,	/*exchange temporary*/
		 **ip;	/*pointer through p[]*/
  register int j;	/*loop index through p*/

  do
  { uns= 0;
    for(j=0,ip=p; j<n-1; ++j,++ip)
    { t= ip[1];
      if( t->nliberties< (*ip)->nliberties ||
	 (t->nliberties==(*ip)->nliberties && t->nstones>(*ip)->nstones) )
      { uns= 1;
        ip[1]= *ip;
	*ip= t;
      }
    }
  } while(uns);

}


int subj_lib(x, y)  int x, y;
/*
Return the subjunctive liberties of the group created by a BLACK move at x, y,
 that is, how many liberties would it have after the move was made?
This is done shoddily, without considering the liberties created by 
 the disappearance of any groups captured by the move.
*/
{ board scratch;	/*parameter array of flags for count()*/
  group t;		/*parameter group for count()*/

  assert(onboard(x,y));
  assert(EMPTY==theboard[x][y]); /*Make sure we can undo by restoring EMPTY.*/

  theboard[x][y]= BLACK;	/*Temporarily place the stone in question.*/

/*Clear scratch[][] so count() works properly.*/
  { register int *s, j;
    for(j=EDGE*EDGE,s=(int*)scratch; j--; )
      *s++= 0;
  }

/*Make a fake group for the new stone to be part of -- this is */
/* a necessary parameter for count().*/
  t.color= BLACK;
  t.x= x;
  t.y= y;
  t.nliberties= 0;
  t.nstones= 0;

/*Show this little Potemkin village to the count().*/
  count(x, y, &t, scratch, 1);

/*Undo the temporary move (x,y).*/
  theboard[x][y]= EMPTY;

/*Return the result from count().*/
  return t.nliberties;

}


pattern1(u, masks, movehere)  int *u;  board masks, movehere;
/*
A routine called by pattern() to match possible moves to
tabulated patterns of specific orientation.  
*u gives the urgency of the best move found so far; we
are to ignore moves which are inferior to this.

If this move has not already been found (compare to the 
urgency value in movehere[]) then we set its urgency
value in *u and in movehere[], and put it into the table
goodmoves[].  If the move is better than any found before,
we put it at the beginning of the table; otherwise we
put it in at the pointer pgoodmoves.

masks[][] is an array which represents the pieces on the board, 
translated into bit masks by lookup in flookup[].

A late-breaking modification is that only the EMPTY points which have
movehere[][] set are tested, so that pattern() can be called to look for
contact plays or possibly other restricted sets which make good patterns.
An even later modification permits the use of movehere[][] to
tell the urgency of the best move which has been made to that
point.
*/
{ register int *is, *iis;/*pointers into patterns[]; or scratch*/
  register int j;	/*& into a particular pattern, # points remaining*/
  register int x, y;	/*current position we're trying to match pattern to*/
  register int xs, ys;	/*position of a point from a pattern*/
  int ua;		/*urgency and adjustment for this move*/
  int thispat;		/*which pattern in the table are we currently */
			/* trying to match?*/


  for(is=patterns,thispat=0; PATTERN==*is; is+= 3+3*(is[1]),++thispat)
  { for(x=0; x<edge; ++x)
      for(y=0; y<edge; ++y)
      { if(F_EMPTY==masks[x][y] && 0==ko(x,y) 
         &&(thegame.kox!=x||thegame.koy!=y) )
        { for(iis=is+1,j= *iis++,ua= *iis++; j; --j)
	  { xs= *iis++;
	    ys= *iis++;
	    if(onboard(x+xs,y+ys))
	    { if(0==(masks[x+xs][y+ys]&*iis++)) goto mismatch; }
	    else
	    { if(0==(F_OFF&*iis++)) goto mismatch; }
	  }
	  /*If we fall through here, then we matched a pattern.*/
	  /*Compute adjusted urgency.*/
	  if(abs(x-lex)<=1&&abs(y-ley)<=1) 
	    ua-=4;	            /*Important to oppose enemy's last move.*/
	  for(xs=(-2); xs<=2; ++xs)  
	    for(ys=(-2); ys<=2; ++ys)
	      if(onboard(x+xs,y+ys))/*Important to move to */
	        ++ua;		    /* uncrowded parts of the board.*/
	  if( ua<*u &&		    /*If this pattern is most urgent so far */
	      0==intoatari(x, y) )  /* and the move is not futile */
	  { *u= ua;	 	    /*Replace old */
	    movehere[x][y]= ua;     /* urgency values.*/
	    patnum= thispat;	    /*Record pattern # for debugging.*/
	    pgoodmoves= goodmoves;  /*Reinit goodmoves[].*/
	    goto intogoodmoves;
	  }
	  else if( ua==*u &&	    /*If there's no better pattern */
	           ua<movehere[x][y] /* and it's the best move here */
		   && !intoatari(x,y)) /*and not futile*/
	  { movehere[x][y]= ua;	/*Mark as best move here.*/
	  intogoodmoves: ;	/*Put it into goodmoves[].*/
	    *pgoodmoves++= x;  *pgoodmoves++= y;
	  }
        }
	mismatch: ;
      }
  }
  if(PATTEND!=*is)
  { fprintf(stderr, "?error in pattern table, pattern # %d\n", thispat);
    panic("programmer error in pattern table");
  }
}


pattern(chosenx, choseny, urgency, movehere)
int *chosenx, *choseny, *urgency;  board movehere;
/*
Try to find a good black move by matching to a table of patterns.  
Returns the urgency of the move; returns BIGU if no match found.

In order to match the patterns in all orientations, we 
reflect the entire table eight times, checking for a match each time.  
The reflections are
  (1)   y <-> edge-1-y	(across a mirror plane parallel to x-axis)
  (2)	x <-> edge-1-x	( " y-axis)
  (3)   y <-> edge-1-y	( " x-axis)
  (4)   x <-> y		( " the line y=x)
  (5)   y <-> edge-1-y	(across a mirror plane parallel to x-axis)
  (6)	x <-> edge-1-x	( " y-axis)
  (7)   y <-> edge-1-y	( " x-axis)
  (8)   x <-> -y	( " the line y=(-x))
Draw pictures if necessary to see how this works.
*/
{ 
  register int x, y, t, j, *is;
  board scratch;


/*Translate the board to flags for easy comparison with pattern table.*/
  for(x=0; x<edge; ++x) 
    for(y=0; y<edge; ++y)
      scratch[x][y]= flookup[theboard[x][y]]; 

  *urgency= BIGU;		/*No big move so far.*/
  pgoodmoves= goodmoves;	/*No moves so far.*/
  patnum= (-1);			/*For debugging: no pattern # so far.*/

  pattern1(urgency, scratch, movehere); 
				/*Find matches to untransformed table.*/

/*Invert y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { is += 1;
      *is= (-*is);
      is += 2;
    }
  }
  assert(PATTEND==*is);
 

  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Invert x coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { ;
      *is= (-*is);
      is += 3;
    }
  }
  assert(PATTEND==*is);

  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Invert y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { is += 1;
      *is= (-*is);
      is += 2;
    }
  }
  assert(PATTEND==*is);
    
  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Exchange x and y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { t= *is;
      *is= is[1];
      is[1]= t;
      is += 3;
    }
  }
  assert(PATTEND==*is);
    
  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Invert y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { is += 1;
      *is= (-*is);
      is += 2;
    }
  }
  assert(PATTEND==*is);
    
  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Invert x coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { ;
      *is= (-*is);
      is += 3;
    }
  }
  assert(PATTEND==*is);

  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Invert y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { is += 1;
      *is= (-*is);
      is += 2;
    }
  }
  assert(PATTEND==*is);
    
  pattern1(urgency, scratch, movehere); 
				/*Find matches to transformed table.*/

/*Exchange x and -y coordinates in pattern table.*/
  for(is=patterns; PATTERN==*is; )
  { for(j= *++is,is+=2; j--; )
    { t= (-*is);
      *is= (-is[1]);
      is[1]= t;
      is += 3;
    }
  }
  assert(PATTEND==*is);

/*Try to pick a move from the table of equally good ones.*/
  { int nmoves= (pgoodmoves-goodmoves)/2;
    if(0==nmoves) return;
    else
    { int whichmove= rng(nmoves);
      *chosenx= goodmoves[2*whichmove];
      *choseny= goodmoves[2*whichmove+1];
    }
  }

/*We'd better not have decided on an illegal move.*/
#if ASSERT
  if( *urgency<BIGU )
    if( EMPTY!=theboard[*chosenx][*choseny] || ko(*chosenx,*choseny) )
      panic("illegal move selected in pattern()");
#endif

}


int attack(g, rx, ry, ml)  group *g;  int *rx, *ry, ml;
/*
Set *rx and *ry to a move which attacks group *g and still has
at least ml liberties.

This routine tries to return the "best" contact play if several are possible.
This is currently implemented as the one as close to the 
 (2.9)-th line as possible, that is, one on the third line is best,
 then one on the fourth, then one on the second, then one on the fifth,
 then etc.

Return TRUE on failure.
*/
{ int bestx, besty;	/*best contact move found so far*/
  int edist;		/*10*distance of this play from (2.9)-st line*/
  register int x, y;
    
  board scratch;

/*Clear scratch[][] so that count() can work.*/
  { register int j, *is;
    for(j=EDGE*EDGE,is=(int*)scratch;  j--; )
      *is++= 0;
  }

/*Set scratch[][] again for the stones of the group, and recalculate the */
/* number of liberties of the group.  Also set scratch[][] for all the EMPTY */
/* points which are contact moves.*/
  g->nstones= 0;	/*Clear these before */	
  g->nliberties= 0;	/* passing to count, which increments them.*/
  count(g->x, g->y, g, scratch, 1);

/*Print out scratch[][] as 9x9 table.*/
  if(debugattack) {
    printf("$In attack after count(), board and scratch are:\n");
    for(y=edge-1; y>=0; --y)
    { printf("$");
      for(x=0; x<edge; ++x)
      { register int c, t=theboard[x][y];
        if(EMPTY==t) c= '.';
        else if(BLACK==t) c= '#';
        else if(WHITE==t) c= 'O';
        else c= '?';
        printf("%c%d ", c, scratch[x][y]);
      }
      printf("\n");
    }
  }

/*Check that there are enough liberties to find a contact play.*/
  assert(g->nliberties>=0);

/*Look for the best adjacent point.*/
  edist= edge*10;	/*We haven't found a point near the (2.9)-th line yet.*/
  for(x=0; x<edge; ++x)  			/*For */
    for(y=0; y<edge; ++y)			/* all */
      if(EMPTY==theboard[x][y] && scratch[x][y]	/*  contact points*/
       && (thegame.kox!=x||thegame.koy!=y) )	/*   which don't violate ko */
        if(subj_lib(x,y)>=ml)			/*    if not too suicidal*/
	{ register int toedge= x;	/*distance to edge of board*/
	  if(toedge>edge-1-x) toedge= edge-1-x;
          if(toedge>y) toedge= y;
          if(toedge>edge-1-y) toedge= edge-1-y;
          if(debugattack)
            fprintf(stderr, "$Looking at %d,%d, toedge=%d, abs=%d.\n", 
		x, y, toedge, abs(10*toedge-21));
	  if(abs(10*toedge-19)<edist)	/*If closer to 2.9th line than before*/
          { edist= abs(10*toedge-21);	/* record */
            if(debugattack) fprintf(stderr, "$Replacing edist.\n");
	    bestx= x;  besty= y;	/*  as the new best so far.*/
          }
          else
	    if(debugattack) fprintf(stderr, "$Not replacing edist=%d.\n", edist);
        }

  if(debugattack) fprintf(stderr, "$Edist= %d.\n", edist);

/*Return best result, if any.*/
  if(edist<edge*10)			/*If some good contact play found */
  { *rx= bestx;  *ry= besty;  		/* return it */
    if(debugattack) fprintf(stderr, "$Returning 0.\n");
    return 0;				/*  and success */
  }
  else
  { if(debugattack) fprintf(stderr, "$Returning 1.\n");
    return 1;
} }


int escape(g, rx, ry)  group *g;  int *rx, *ry;
/*
Set *rx and *ry to a play which lets group *g escape from atari.
*/
{ register int x, y;
    
  board scratch;

/*Clear scratch[][] so that count() can work.*/
  { register int j, *is;
    for(j=EDGE*EDGE,is=(int*)scratch;  j--; )
      *is++= 0;
  }

/*Set scratch[][] again for the stones of the group, and recalculate the */
/* number of liberties of the group.  Also set scratch[][] for all the EMPTY */
/* points which are contact moves.*/
  g->nstones= 0;	/*Clear these before */	
  g->nliberties= 0;	/* passing to count, which increments them.*/
  count(g->x, g->y, g, scratch, 1);

/*Check that there are enough liberties to find a contact play.*/
  assert(g->nliberties>=0);

/*Return any point which succeeds.*/
  for(x=0; x<edge; ++x)  			/*For */
    for(y=0; y<edge; ++y)			/* each */
      if(EMPTY==theboard[x][y] && scratch[x][y] /*  contact point */
       &&(thegame.kox!=x&&thegame.koy!=y) )	/*   which is not ko */
        if(0==intoatari(x,y))			/*    if not into atari */
	{ *rx= x;  *ry= y;  return 0; }		/*     then return it.*/

/*Otherwise return failure.*/
  return 1;
}


mymove()
/*Calculate and execute and print out the computer's move.*/
{
  register int j;  register group *g; /*index and pointer through groups[]*/
  int x, y;			/*coords of the move selected*/
  group *gt[EDGE*EDGE];		/*table of &groups in order of vulnerability*/
  group **fs, **es;		/*pointers into gt: start of friendly and */
				/* enemy tables*/
  register group **igt;		/*scratch pointer through gt[]*/
  int nf, ne;			/*number of enemy and friendly groups*/
  int upattern, patternx, patterny;
  board scratch;

/*Find the most urgent move to improve our shape.*/
/*First say that all moves are to be considered.*/
  { register int *ip;
    for(ip=(int*)scratch,j=EDGE*EDGE; j--; )
      *ip++= BIGU;
  }
/*Then call pattern search.*/
  pattern(&patternx, &patterny, &upattern, scratch);

/*Make tables of friendly and enemy groups in gt[] at *fs and *es.*/
  for(j=0,g=groups,nf=0,fs=igt=gt; j<ngroups; ++j,++g)
    if(BLACK==g->color)
    { ++nf;
      *igt++= g;
    }
  for(j=0,g=groups,ne=0,es=igt; j<ngroups; ++j,++g)
    if(WHITE==g->color)
    { ++ne;
      *igt++= g;
    }

/*Sort the tables in order of vulnerability to attack.*/
  sortv(fs, nf);
  sortv(es, ne);

/*Consider extremely urgent pattern moves.*/
  if(upattern<16)
  { 
  movepattern:
    if(debugattack)
      printf("$making pattern, pattern #=%d, urgency=%d.\n", patnum, upattern);
    x= patternx;
    y= patterny;
    goto movexy;
  }    
/*Capture the enemy!*/
  while(ne && 1==(*es)->nliberties)
  { if(0==attack(*es, &x, &y, 0))
    { if(debugattack) printf("$Capturing the enemy.\n");
      goto movexy;
    }
    else /*(This case comes up if we can't capture because of ko.)*/
    { ++es; --ne; }		/*Go on to next most vulnerable group.*/
  }
  if(upattern<24) goto movepattern;
/*If we can't do that, then try to protect ourself.  But as per Dr. Millen, */
/* don't risk everything crawling along the edge without lookahead.*/
/*However, we have a more powerful computer than the good doctor, so we */
/* can afford to check another condition: if crawling connects to a healthy */
/* group immediately (as when the program makes a pattern match with */
/*	O O #	*/
/*	. . O .	*/
/*	~ ~ ~ ~ */
/* where '~' is off the board, then is attacked with */
/*	O O #   */
/*	. . O # */
/*	~ ~ ~ + */
/* it seems to make no sense to prohibit the program from defending with */
/*	O O #   */
/*	. O O # */
/*	~ ~ ~ ~ */
/* ..  so we *don't* prohibit it.*/
  while(nf && 1==(*fs)->nliberties)
  { if(escape(*fs, &x, &y))	/*If we can't see how to escape */
    { ++fs; --nf; }		/* go on to next friendly group, */
    else			/*  otherwise */
    { if((0==x||edge-1==x||0==y||edge-1==y) && /* if crawling */
	 (2>=subj_lib(x,y)) )	/* and not connecting to strong group */
      { ++fs; --nf;  continue; } /* this is probably not a good move */
      else			/* but if not crawling or connecting to */
				/* a strong group, go for it.*/
      if(debugattack)
        printf("$Protecting a friendly group from imminent capture.\n");
      goto movexy;
    }
  }
  if(upattern<34) goto movepattern;
/*Try putting the enemy in atari.*/
  while(ne && 2==(*es)->nliberties)	/*For all vulnerable enemy groups */
  { if(attack(*es, &x, &y, 2))		/* if we can't see how to attack */
    { ne--; ++es; }			/*  go on to the next enemy group, */
    else				/*   otherwise */
    { if(debugattack)
        printf("$Putting an enemy group into atari.\n");
      goto movexy;			/*    attack the group.*/
    }
  }
  if(upattern<BIGU) goto movepattern;
/*Try to harass the most vulnerable enemy group.*/
  while(ne)				/*For all remaining enemy groups */
  { if(attack(*es, &x, &y, 3))	/* if we can't see how to attack safely */
    { --ne; ++es; }			/*  go on to next enemy group*/
    else				/*   otherwise*/
    { if(debugattack)
        printf("$Harassing the most vulnerable enemy group.\n");
      goto movexy;			/*    attack it*/
    }
  }
#if 0 /*This seems to lose points.  Lets see how we do without it.*/
/*Move randomly adjacent to no stones or edges.*/
  for(x=1; x<edge-1; ++x)  for(y=1; y<edge-1; ++y)
    if( EMPTY==theboard[x][y] &&
	EMPTY==theboard[x][y-1] && EMPTY==theboard[x][y+1] && 
        EMPTY==theboard[x-1][y] && EMPTY==theboard[x+1][y] )
    { if(debugattack)
        printf("$Moving randomly to fill space.\n");*/
      goto movexy;
    }
#endif
/*If nothing else comes to mind, pass.*/
  printf("%s passes.\n", progname);
  if(ofile)
#ifdef  ADDED
   switch (outputmode)
   {
   case WALLY_OUTPUT:
#endif
    fprintf(ofile, "%d: pass\n", thegame.tur);
#ifdef  ADDED
    break;

   case MGT_OUTPUT:
    fprintf(ofile, ";\nComment[Black passes]\n");
    break;

   /* nothing to do for CAT_OUTPUT */
   }
#endif
  thegame.kox= thegame.koy= (-1);
  movedone();
  if(thegame.qpa) return BOTHPASS;
  else
  { thegame.qpa= 1;
    return PASS;  
  }

movexy:
  printf("%s moves to %c%d.\n", progname, lettercol(x), y+1);
  fflush(stdout);
  if(ofile)
#ifdef  ADDED
   switch (outputmode)
   {
   case WALLY_OUTPUT:
#endif
    fprintf(ofile, "%d: %c%d\n", thegame.tur, lettercol(x), y+1);
#ifdef  ADDED
    break;

   case MGT_OUTPUT:
    fprintf(ofile, ";\nComment[%d: Black: %c%d]\nBlack[%c%c]\n",
	thegame.tur, lettercol(x), y+1, M_LETTER(x), M_LETTER(y));
    break;

  /* nothing for CAT_OUTPUT as it will be recalculated */
  }
#endif
  placestone(x, y, BLACK);
  thegame.qpa= 0;
  movedone();
  return 0;
}


enemymove()
/*Read and execute opponent's move.*/
{ int x, y;	/*coordinates of move*/
  int s;	/*return value of scanfcoo()*/
endrecurse:
  printgame();
  printf("Please input your move (%s #%d): ", pname(thegame.pla), thegame.tur);
  s= scanfcoo(&x, &y);	/*Try to get a move.*/
  if(RESIGN==s)		/*If opponent resigns*/
#ifdef  ADDED
  {
    if (ofile)
    {
      switch (outputmode)
      {
      case WALLY_OUTPUT:  /* should agree with #else below */
        fprintf(ofile, "%d: resigns\n", thegame.tur);
        break;

      case MGT_OUTPUT:
        fprintf(ofile, ";\nComment[White resigns]\n");
        break;

      case CAT_OUTPUT:
        fprintf(ofile, ".\n");
        break;
      }
    }
#else
  { if(ofile)  fprintf(ofile, "%d: resigns\n", thegame.tur);
#endif
    return RESIGN;
  }
  if(PASS==s)		/*If opponent passes*/
#ifdef  ADDED
  {
    if (ofile)
    {
      switch (outputmode)
      {
      case WALLY_OUTPUT:  /* should agree with #else below */
        fprintf(ofile, "%d: pass\n", thegame.tur);
        break;

      case MGT_OUTPUT:
        fprintf(ofile, ";\nComment[White passes]\n");
        break;

      case CAT_OUTPUT:
        fprintf(ofile, "pass\n");
        break;
      }
    }
#else
  { if(ofile)  fprintf(ofile, "%d: pass\n", thegame.tur);
#endif
    movedone();
    thegame.kox= thegame.koy= (-1);
    ley= ley= (-1000);	/*'way off the board*/
    if(thegame.qpa) return BOTHPASS;
    else
    { thegame.qpa= 1;
      return PASS;
  } }
  if( 0==s )
  { printf("Please try again.  Input your move as a letter for the column, \n");
    printf(" followed by a number for the row number.\n");
    goto endrecurse;
  }
  if( 0==onboard(x,y) )
  { printf("Only moves which are on the board are legal.  Please try again.\n");
    goto endrecurse;
  }
  if( EMPTY!=theboard[x][y] ) 
  { printf("You cannot stack a stone on another.  ");
pleasetryanothermove:
    printf("Please try another move.\n");
    goto endrecurse;
  } 
  if(ko(x,y))
  { printf("That move would violate the rule of ko.  ");
    goto pleasetryanothermove;
  }
  placestone(x, y, thegame.pla);
  thegame.qpa= 0;
  if(ofile)
#ifdef  ADDED
   switch (outputmode)
   {
   case WALLY_OUTPUT:
#endif
    fprintf(ofile, "%d: %c%d\n", thegame.tur, lettercol(x), y+1);
#ifdef  ADDED
    break;

   case MGT_OUTPUT:
    fprintf(ofile, ";\nComment[%d: White: %c%d]\nWhite[%c%c]\n",
	thegame.tur, lettercol(x), y+1, M_LETTER(x), M_LETTER(y));
    break;

   case CAT_OUTPUT:
    fprintf(ofile, "%c%d\n", lettercol(x), y+1);
    break;
   }
#endif
  movedone();
  return 0;  
}


fscore(file, territory)  FILE *file;  int territory[NPLAYERS];
{
  register int j;

  fprintf(file, "(the end of the game)\n");
  fprintf(file, "Final score is:\n");
  for(j=0; j<NPLAYERS; ++j)  
    fprintf(file, "%s has %d territory.\n", 
            BLACK==j?"Black":"White", territory[j]);
  j= territory[BLACK]-territory[WHITE];
  if(0==j)
    fprintf(file, "(a tie)\n");
  else if(j>0)
    fprintf(file, "(Black wins.)\n");
  else
    fprintf(file, "(White wins.)\n");

}


int ist(x, y, n, scratch)  register int x, y, n;  board scratch;
/*This is the recursive part of isterritory().*/
{
  assert(onboard(x,y));
  assert(EMPTY==theboard[x][y]);
  assert(0==scratch[x][y]);
  scratch[x][y]= 1;

  x= x+1;
  if(onboard(x,y))
  { if(EMPTY==theboard[x][y])
    { if(0==scratch[x][y] && 0==ist(x, y, n, scratch))
        return 0;
    }
    else if(n==theboard[x][y])
      return 0;
  } 

  x= x-2;
  if(onboard(x,y))
  { if(EMPTY==theboard[x][y])
    { if(0==scratch[x][y] && 0==ist(x, y, n, scratch))
        return 0;
    }
    else if(n==theboard[x][y])
      return 0;
  } 

  x= x+1;
  y= y+1;
  if(onboard(x,y))
  { if(EMPTY==theboard[x][y])
    { if(0==scratch[x][y] && 0==ist(x, y, n, scratch))
        return 0;
    }
    else if(n==theboard[x][y])
      return 0;
  } 

  y= y-2;
  if(onboard(x,y))
  { if(EMPTY==theboard[x][y])
    { if(0==scratch[x][y] && 0==ist(x, y, n, scratch))
        return 0;
    }
    else if(n==theboard[x][y])
      return 0;
  } 

  return 1;

}


int isterritory(x, y, p)  register int x, y, p;
/*
Return TRUE if the EMPTY point x, y is to be counted as territory for
player p.  This is only called at the end of the game, and I see no
reason why it can't be slow.

I don't understand the (Ing?) fractional point rules, so I don't implement them.
 An empty point counts as territory only if only one player has stones adjacent
 to the block of empty spaces to which it belongs.
*/
{
  board scratch;

  assert(onboard(x,y));
  assert(EMPTY==theboard[x][y]);

/*Clear scratch[].*/
  { register int x, y;
    for(x=0; x<edge; ++x)  for(y=0; y<edge; ++y)
      scratch[x][y]= 0;
  }

/*Decide recursively.*/
  return ist(x, y, nextp(p), scratch);

}


score()
/*Compute and output the final game score.  Use Chinese rules, of course.*/
{
  register int x, y, p;
  int territory[NPLAYERS];	/*each player's territory*/

/*Count territories.*/
  for(p=0; p<NPLAYERS; ++p) 
  { territory[p]= 0;
    for(x=0; x<edge; ++x)  for(y=0; y<edge; ++y)
      if(p==theboard[x][y]||EMPTY==theboard[x][y]&&isterritory(x,y,p))
	++territory[p];
  }

/*Output results.*/
  fscore(stdout, territory);
  if(ofile)
#ifdef  ADDED
   switch (outputmode)
   {
   case WALLY_OUTPUT:
#endif
    fscore(ofile, territory);
#ifdef	ADDED
    break;

   case MGT_OUTPUT:
    fprintf(ofile, ";\nComment[");
    fscore(ofile, territory);
    fprintf(ofile, "]\n");
    break;

   /* nothing to write for CAT_OUTPUT */
   }
#endif

}


main(argc, argv)  int argc;  char *argv[];
{ int maybe= 0;	/*possible input board size*/
  int rvalue;	/*return values from enemymove() and mymove()*/

#ifdef	ADDED
  long secs, time();
  char hname[80], *ctime();
#endif

/*Process command line arguments.*/
  argv++;	/*Skip argv[0]; Mark Williams C doesn't seem to set it.*/
  for( ; --argc; ++argv)
  { if(1==sscanf(*argv, "%d", &maybe))
    { if(maybe<7 || maybe>EDGE) fatal("board size out of range on input line");
      edge= maybe;
    }
    else if(0==strcmp(*argv,"-even"))	/*if we are to play an even game*/
      evenmode= 1;
#ifdef  ADDED
    else if (strcmp(*argv, "-d") == 0)
      debugattack = 1;
    else if (strcmp(*argv, "-mgt") == 0)
      outputmode = MGT_OUTPUT;
    else if (strcmp(*argv, "-cat") == 0)
      outputmode = CAT_OUTPUT;
#endif
    else
#ifdef	ADDED
    {
#else
    { char hname[80];
#endif
      if(0!=ofname) fatal("duplicate filenames in command line");
      ofname= *argv;
      ofile= fopen(ofname, "w");      
      if(0==ofile) fatal("unable to open output file");
#ifndef ADDED
      printf("What is the name of my opponent? (for the game record)\n");
      gets(hname);
      fprintf(ofile, "%s (black) vs. %s (white)\n", progname, hname);
#endif
    }
  }
#ifdef  ADDED
  if (ofile == 0)
  {
    if (outputmode != WALLY_OUTPUT)
    {
      fprintf(stderr, "%s: output file needed for -mgt or -cat\n", progname);
      exit(1);
    }
  }
  else
  {
    if (outputmode != CAT_OUTPUT)
    {
      printf("What is the name of my opponent?  ");
      gets(hname);
    }

    switch (outputmode)
    {
    case WALLY_OUTPUT:  /* should match that in #ifndef above */
      fprintf(ofile, "%s (black) vs. %s (white)\n", progname, hname);
      break;

    case MGT_OUTPUT:
      time(&secs);
      fprintf(ofile, "(\n;\nGaMe[1]\nSize[%d]\nVieW[]\nBlackSpec[1]\n", edge);
      fprintf(ofile, "WhiteSpec[1]\nFileFormat[1]\nPLayer[]\n");
      fprintf(ofile, "Comment[Black: %s\nWhite: %s\n\nDate:  %s",
	progname, hname, ctime(&secs));
      fprintf(ofile, "Size:  %d x %d]\n", edge, edge);

    /* CAT_OUTPUT doesn't require any of this */
    }
  }
#endif
  if(evenmode) nhandicap[edge]= 0;

/*Make a brief explanation.*/
  printf("%s\n%s\n",
	"This program plays (poorly) the oriental game of Go, also",
	"known as wei-chi.");

/*Play the game.*/
  initgame();
  do
    if(BLACK==thegame.pla)
      rvalue=mymove();
    else if(WHITE==thegame.pla)
      rvalue=enemymove();
    else 
      panic("illegal thegame.pla in main() loop");
  while(rvalue!=BOTHPASS && rvalue!=RESIGN);
#ifndef	ADDED
  if(BOTHPASS==rvalue)
#endif
    score();

/*Close the output file.*/
  if(ofile)
#ifdef  ADDED
  {
    if (outputmode == MGT_OUTPUT)
      fprintf(ofile, ")\n");
#endif
    if(fclose(ofile)) fatal("unable to close output file");
#ifdef  ADDED
  }
#endif

  exit(0);
}