games@tekred.TEK.COM (10/18/88)
Submitted by: "James D. Allen" <jamesa@sun.com>
Comp.sources.games: Volume 5, Issue 71
Archive-name: c4/Part01
[This game is actually a game solver. Given a starting position
in a "Connect Four" game, the program finds the winner and prints
various statistics along with the solution tree. -br]
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 2)."
# Contents: README MANIFEST Game.E Makefile Tree.E anal.h c4.c
# do_conn4 parameters.h predinit.h showtree.c
# Wrapped by billr@saab on Mon Oct 17 10:12:50 1988
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(8566 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
X
X*** General information about this software ***
X
XFiles in this distribution:
X README = you are READing ME now
X c4.c anal.h predinit.h parameters.h = source for `c4'
X showtree.c = source for `showtree'
X do_conn4 = a simple "frontend" script for c4
X Dictionary = previously solved positions to get you started
X Game.E = sample input
X Tree.E = output from the sample input
X(The sample input is interesting. It's a common "expert" opening.
XThere is only one winning move. Try to find the winning move
Xbefore "peeking.")
X
X`c4' is compiled with a "-O" option; naturally you will
Xwant to replace this with the most powerful optimizing option
Xavailable to you, but any speed improvement will be totally
Xinsignificant compared with the benefits of even minor tuning of
Xthe heuristic parameters. The memory requirement is determined in
X`parameters.h'. You just have to adjust "SSS" downward to run with
Xsmaller memory.
X
X"Red" = first player, "White" = second player.
X
XThis is being distributed AS IS. Caveat emptor.
X
XIt produces LOTS of lint errors. It assumes
X . that sizeof (long) == 4 (see "KEY")
X . all pointer types are represented the same
X . that functions can be variadic without <varargs.h>;
X this is only assumed by some "printf" covers.
XIt runs on Sun-3 and Sun-4; that was good enough for me.
XIt MIGHT run on an Intel-based configuration, but I'll bet
Xsome modifications will be necessary.
X
XI would have done a lot of things better (or at least differently)
Xif I had been paid to develop this, or even if I had known I might
Xpost it. I'm sure there are many things that will seem too
X"tricky." This was not intentional. I should mention that there
Xare many things (like the values in "plymode[]") that will seem
Xto be mysterious magic, but in fact are just near-random and
Xalmost totally untuned heuristics.
X
XThe software runs on Unix. You *might* be able to port it to another
Xenvironment without *major* problems but I don't encourage that.
XMy runs were with a cache-size of 4 megabytes or more. (It may run
Xnearly as fast with a much smaller cache). You may compress the
Xformat of the cache-entry somewhat; I didn't because that would be
Xa tedious effort.
X
XThere are two C programs:
X c4.c anal.h predinit.h parameters.h ---> c4
Xand
X showtree.c ---> showtree
X (showtree is invoked inside c4 with a `popen()'.)
X
Xand a simple script (do_conn4) similar to the alias I always used.
X
XThe usage `do_conn4 2 foo' will read a file "Game.foo" for its input
Xand produce a file "Info.foo" as its output. The `2' indicates how
Xfar down you want the complete Game_Tree to be printed. Each
Xincrement to this value will slow the program down by a factor of
Xabout 2.5. `1' is the minimum value and is used to solve the game;
Xa value of `4' gets you a nice game tree printout.
X
Xc4 produces output on 4 streams:
X "Facts" contains the "bottom-line" synopsis of each
X input position in human-readable form.
X "Dict.out" contains the result of each 9- and 12-stone
X position examined in an ascii but not particularly
X readable format.
X <treeshow> gets piped to `sort -r | showtree' to display
X the "game tree" for the input position.
X <stderr> contains statistics about the run; `tail -f' on
X this stream also gives a very crude progress report.
X
XThe filtered <treeshow> is renamed to "The_Game_Tree". If the above
Xscript is used it and the <stderr> statistics end up in "Info.foo".
X
XIf `c4 -v N' is the command, with N > 1, then "important" information
Xwill show up in "The_Game_Tree" which is NOT placed in "Facts."
X
XThe pieces of the "game tree" are computed in postorder, but need
Xto be printed in preorder. I accomplished this by inverting the
Xentire <treeshow> with the ugly "sort -r" mechanism. You will need
Xto know this to fully understand certain ambiguities in the printed
Xgame tree.
X
XControl-C (or "kill -2") will terminate `c4' but give you the
Xstatistics and a partial game-tree. The work done is not completely
Xwasted; it's saved in "Dict.out" as it's computed.
X
XThe program contains lots of garbage to generate the stderr
Xstatistics, and most of the statistics are not particularly
Xinteresting. In general I printed statistics easy to gather
Xrather than useful statistics :-(
X
XI've "#ifdef"ed the statistics out unless you define "BORING".
XNo real harm in defining BORING, but I thought it more readable
Xto ifdef the junk to help distinguish functional and non-functional
Xcode. Warning: I added the BORING ifdefs just for this posting.
XI've retested the program since, but Murphy may strike anyway.
X
XOn startup, the program reads "Dictionary" to fill its cache
Xwith previously examined 9- and 12-stone positions. This is
Xnecessary if you need to kill and restart the program without
Xlosing all prior work. The "Dictionary" is now over a megabyte
Xso I have selected only some of the 9-stone positions for
Xthis posting. The "Dd" opening is covered fairly well.
X"Dictionary" should normally be the same file as "Dict.out", ie:
X % ln Dictionary Dict.out
XBut having two distinct files will simplify certain experiments.
X
X<stdin> looks like this:
X DdDd=
XHere, the first four moves are up the central ("D") column, and
Xthe program is asked for a complete solution ("="). You can
Xalso ask just for Red wins ("+") or White wins ("-") which will be
Xsomewhat faster. Full search is in any event forced when 9-
Xand 12-stone positions are solved to simplify the Dict.out database.
X
XMultiple games can be solved in one run with input like:
X DdDd=
X c=
X b=
X =
X .
X =
X(whitespace irrelevant)
X
XThis would be equivalent to five runs:
X DdDd=
X DdDc=
X DdDb=
X DdD=
X D=
XThis is not fully supported, however, since the "Dictionary" filtering
Xis done only once.
X
XOccasionally after you do something unusual, the program may complain
Xabout "Duplicate in Dictionary". Recover with:
X % sort Dictionary | uniq > foo
X % mv foo Dictionary
X
XSince the program does *exhaustive* search, there are only three
Xpossible "values" a game can have (Red win, White win, Draw). The
Xcode does not take full advantage of this simplicity because I
Xmight want to convert it to a non-exhaustive search.
X
XThe first time I compiled this program it was close to this final
Xform except for "Dictionary", some of the statistics gathering,
Xand the "restricted search." I had no idea what the execution speed
Xwould be. In turned out to be a very *tantalizing* speed: not
Xquite fast enough to solve the game with the single workstation at
Xmy disposal, yet not so slow as to rule out the possibility of solution
Xif another order-of-magnitude speedup could be found. How I
Xhappened on "restricted search" is an interesting story:
X
XI was running a 5-stone position. The run was killed and restarted
Xevery several hours for various reasons. I felt that the 12-stone
Xdictionary would "preserve" prior work. But this did not seem to
Xbe working. Eventually the position was solved. Now I thought that
XI should be able to rerun that input and get the solution very quickly
Xsince all the necessary 12-stone positions were in the "Dictionary".
XBut it still took several hours to solve, during which more (obviously
Xunnecessary) 12-stone solutions were appended to the "Dictionary."
XOnly after rerunning the input several times did solution become rapid.
X
XThe problem was the dynamic nature of the killer-move prediction
Xtables. As the starting cache varied, the order in which subtrees
Xwere searched varied. Hence, although the cache contained enough
Xinformation to solve the game, the software failed to utilize this
Xsince it searched the subtrees in the "wrong" order. I therefore
Xdeveloped the "restricted search" mechanism and this gave me the
Xorder-of-magnitude speedup I needed. I don't know if this is a
Xwell-known technique; I haven't seen it explicitly discussed in
Xthe literature I've read.
X
XI'm sure there are still ways to speed up the program. I have
Xspent little time trying to "tune" the tunable parameters already
Xbuilt in. (I felt that only long runs would be meaningful
Xexperiments, but "Dict.out" has to be disabled for such experiments
Xand I wanted to spend the machine time solving the game ASAP.)
XOne important improvement would be to give each ply its own
Xkiller-move prediction table. Right now, killer move prediction is
Xprobably rather poor at early plys.
X
XThere must be some way to get another order-of-magnitude
Xspeedup. Please write me if you find it (USMail, don't try E-mail).
X
XI'm too lazy to discuss the details of the implementation. But
Xthe software is worth every penny I'm charging for it.
X :-}
X
X James D. Allen
X jamesa@sun.com
END_OF_FILE
if test 8566 -ne `wc -c <'README'`; then
echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(588 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X File Name Archive # Description
X-----------------------------------------------------------
X Dictionary 2 List of previously examined positions
X Game.E 1 Sample input game
X MANIFEST 1 This shipping list
X Makefile 1
X README 1
X Tree.E 1 Sample output from sample input
X anal.h 1
X c4.c 1
X do_conn4 1 Sample run script
X parameters.h 1
X predinit.h 1
X showtree.c 1
END_OF_FILE
if test 588 -ne `wc -c <'MANIFEST'`; then
echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test -f 'Game.E' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Game.E'\"
else
echo shar: Extracting \"'Game.E'\" \(18 characters\)
sed "s/^X//" >'Game.E' <<'END_OF_FILE'
XDdDdDeEeEbBbBbDg=
END_OF_FILE
if test 18 -ne `wc -c <'Game.E'`; then
echo shar: \"'Game.E'\" unpacked with wrong size!
fi
# end of 'Game.E'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(390 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X# simple makefile for c4
XPROGS = c4 showtree
X
XCFLAGS = -O
X
Xall: $(PROGS) Dict.out
X
Xrun: all
X @echo Running sample input
X ./do_conn4 3 E
X diff Tree.E The_Game_Tree
X @echo If only the dates differ, the program worked
X
Xc4: c4.c anal.h parameters.h predinit.h
X cc -o c4 $(CFLAGS) c4.c -lm
X
Xshowtree: showtree.c
X cc -o showtree $(CFLAGS) showtree.c
X
XDict.out: Dictionary
X ln Dictionary Dict.out
END_OF_FILE
if test 390 -ne `wc -c <'Makefile'`; then
echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'Tree.E' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Tree.E'\"
else
echo shar: Extracting \"'Tree.E'\" \(585 characters\)
sed "s/^X//" >'Tree.E' <<'END_OF_FILE'
X
XOct 4 23:21 1988 Page 1
X
X
X c+ B+
X e+ B+
XInput: ---X---
X -O-X---
X -X-OX--
X -O-XO--
X -X-OX--
X -O-XO-O
X
X
X
X
X A- a+ A+
X f+ F+
X g= A=
X G=
X C=
X B=
X e= A=
X G=
X C=
X B=
X c+ B+
X b-
X G- a= A=
X G=
X C=
X B=
X f= F=
X g= A=
X G=
X C=
X B=
X c= A=
X G=
X B=
X b-
X e= A=
X G=
X C=
X B=
X B+ f+ F+
X g+ C+
X a+ C+
X c+ E+
X e+ C+
X C- a+ B+
X f+ F+
X g+ B+
X b-
X e+ B+
X c+ B+
X E- a+ B+
X f+ F+
X g+ B+
X b-
X
X
X
X
X
END_OF_FILE
if test 585 -ne `wc -c <'Tree.E'`; then
echo shar: \"'Tree.E'\" unpacked with wrong size!
fi
# end of 'Tree.E'
fi
if test -f 'anal.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'anal.h'\"
else
echo shar: Extracting \"'anal.h'\" \(14031 characters\)
sed "s/^X//" >'anal.h' <<'END_OF_FILE'
X
X/*
X * This software is copyright (c) 1988 by
X * James D. Allen
X * 1866 Silvana Lane
X * Santa Cruz CA 95062
X *
X * This notice must not be removed.
X * This software must not be sold for profit.
X * You may redistribute if your distributees have the
X * same rights and restrictions.
X */
X
X/*
X * This routine is the real guts of the program.
X * This routine is two routines ("ranal()" and "wanal()"); that's
X * just because "#ifdef" seemed more convenient than "if"
X *
X * "reduced" search means "alpha-beta" is reduced.
X * "restricted" search means a limit is placed on maximum depth.
X *
X * The routine is passed a position for evaluation and does the
X * following:
X * 1) Generate all legal moves. Immediate victory and
X * immediate draw cause immediate termination.
X * 2) Dispose of certain positions judged redundant by symettry.
X * 3) Look up each resultant position in the Table. If a
X * killer is found we can exit immediately. Or if all
X * positions are solved in the Table we will exit
X * with "RED?beta:alpha"; this is important for "leafs"
X * 4) Exit (with UNK) if at the "leaf" of a restricted search.
X * 5) Determine a likely order for searching the subtrees.
X * 6) Search the subtrees in order until a killer is found.
X * Sometimes a "quick" prescan is attempted.
X * Output new book positions when appropriate;
X * do alpha-beta adjustments. A "IMMWIN/needx"
X * heuristic is done pointlessly. Table entries are sent
X * either to the beginning or to the end of an LRU list.
X * Pure alpha-beta is trivial to code; 90% of the junk is just
X * for minor add-on kicks.
X * 7) If an "interesting" killer is found, adjust the prediction
X * table using an algorithm similar to USCF ratings.
X * A killer is interesting only when:
X * a) it wasnt found in the Table,
X * b) the gameboard isn't almost filled up,
X * c) it isn't in the same column as the opponent's prior move,
X * d) it didnt stop an immediate win, AND
X * e) there were at least two other legal moves.
X * 8) Periodically stabilize the prediction table by calling
X * predreduce().
X * 9) Return any unused Table entries to an LRU list.
X * 10) Estimate whether the position was "easy". If so,
X * prevent it from using Table space.
X * 11) Pass the game value back to the caller.
X *
X * Steps 3,9 are omitted unless the ply is a "hashed ply."
X * Step 10 is omitted unless the parent ply is a "hashed ply."
X * (Step 10 is "#if 0" 'ed out since it was a no good idea.)
X *
X * Alpha/beta reduction is suppressed when developing the
X * game_tree book or the dictionary book.
X */
X
X#ifdef RED
X
X#define MYANAL ranal
X#define HISANAL wanal
X#define QPred rpred
X#define THMAX 3
X#define FOU(Q) (Four[t->Q.red[y] |= 1 << x])
X#define MYIMMX rimmx
X#define HISIMMX wimmx
X
X#else
X
X#define MYANAL wanal
X#define HISANAL ranal
X#define QPred wpred
X#define THMAX -3
X#define FOU(Q) (Four[t->Q.whi[y] |= 1 << x])
X#define MYIMMX wimmx
X#define HISIMMX rimmx
X
X#endif
X
X#ifndef DO_ALL
X#define DO_ALL (vflag && verbose > 1)
X#endif
X
XMYANAL(pos, alpha, beta, verbose, xl)
X struct pos *pos;
X int alpha; /* max (for red) interesting value */
X int beta; /* min (for red) interesting value */
X int verbose; /* level of output Game Tree */
X int xl; /* accounting ply if small, else maxdepth */
X{
X struct pos new[7];
X register struct pos *t;
X u_long ixp[7];
X short *lp;
X int arg5, totalpbet;
X int levy, i, val, needx;
X int oldcost;
X register int x, y;
X static int predit = 0;
X int alpbet = AB_TRIT;
X float flwork;
X int unknown = FALSE;
X#ifdef RED
X int fval = beta;
X#else
X int fval = alpha;
X#endif
X#ifdef PSUCC
X int scexist = 1;
X#endif
X
X if ((vlevel - verbose) < 3)
X fprintf(stderr, "%s move %c\n",
X vlevel - verbose == 2 ? "\t\tExamining" :
X vlevel - verbose == 1 ? "\tExamining" : "Input",
X#ifdef RED
X pos->pcolum + 'a');
X#else
X pos->pcolum + 'A');
X#endif
X
X levy = levty[i = pos->plytot];
X#ifdef BORING
X oldcost = cost;
X examined[i]++;
X if (xl >= MINDEPTH)
X qxamined[i]++;
X#endif
X
X for (x = i = 0, t = new; x < 7; x++, t++, i += 7) {
X t->p_hp = NULL;
X y = pos->hei[x];
X t->ppred = QPred[t->move = i + y];
X if (!(VALID(t)))
X continue;
X if (pos->vth[x] == THMAX)
X goto win;
X/*
X * FYI: #define fldoff(str, fld) ((int)&(((struct str *)0)->fld))
X */
X memcpy(t, pos, (int)&(((struct pos *)0)->p_hp));
X t->asymetric = 1;
X t->plytot++;
X t->hei[x] = y + 1;
X if (FOU(hori))
X goto win;
X if ((y = x - y + 2) >= 0 && y < 6 && FOU(dext))
X goto win;
X if ((y += 6 - x - x) >= 0 && y < 6 && FOU(sini))
X goto win;
X if (levy == ENDED)
X return DRAW;
X#ifdef RED
X t->vth[x] = (y = t->vth[x]) > 0 ? y + 1 : 1;
X#else
X t->vth[x] = (y = t->vth[x]) < 0 ? y - 1 : -1;
X#endif
X }
X if (!(pos->asymetric)) {
X new[3].asymetric = 0;
X/*
X * The red vs white silliness which follows became irrelevant
X * when setupdic() was modified to put mirror-images of
X * dictionary positions into the cache.
X */
X#ifdef RED
X DONE(new+0);
X DONE(new+2);
X DONE(new+5);
X#else
X DONE(new+1);
X DONE(new+4);
X DONE(new+6);
X#endif
X }
X if (levy > 0) for (t = new; t < new + 7; t++) if (VALID(t)) {
X register struct he *hp, **hpp;
X
X if (!(hp = *(hpp = gethe(t)))) {
X hp = newhe(levy - 1);
X /*
X * Check for rare collision:
X */
X if (hp == (struct he *)hpp) {
X rarein++;
X hpp = gethe(t);
X }
X t->p_hp = *hpp = hp;
X/* next relies on 'red' first in struct ... need smarter union */
X memcpy(hp->h.he_d, t->hori.red, 12);
X hp->cback = (struct he *)hpp;
X unknown = TRUE;
X } else {
X t->p_hp = hp;
X /*
X * The table entry must be "locked"
X * until we dispose of it below.
X * This is done with "htop" or "Hrm"
X * htop() may be called more than once this way,
X * but that's harmless.
X */
X if (hp->abflag & alpbet) {
X val = hp->valu;
X/* temporary for debug: */
X if (val != RWIN && val != WWIN && val != DRAW)
X fatal("Garbage in cache");
X htop(hp, levy-1);
X DONE(t);
X if (verbose > 0) {
X fprintf(treeshow,
X"%07d %d %d %d\n", seq++,
X vlevel - verbose,
X t - new, val);
X }
X#ifdef RED
X if (DO_ALL) {
X if (val > fval)
X fval = val;
X } else if (val > beta)
X if (val >= alpha)
X goto killed;
X else {
X beta = val;
X alpbet = AB_TRIT;
X }
X else;
X#else
X if (DO_ALL) {
X if (val < fval)
X fval = val;
X } else if (val < alpha)
X if (val <= beta)
X goto killed;
X else {
X alpha = val;
X alpbet = AB_TRIT;
X }
X else;
X#endif
X } else {
X unknown = TRUE;
X /*
X * Crude heuristic:
X */
X if (hp->refcnt > 1)
X htop(hp, levy-1);
X else
X Hrm(hp);
X }
X }
X } else ; else
X unknown = TRUE; /* protect against unhashed quick ply */
X/*
X * last should be unneccessary becuz programmer "should" have followed
X * his own instructions and Tablized the ply at QUICK_PLY+DEPTH+1 :-}
X */
X
X if (xl == MINDEPTH)
X goto fini;
X
X if (levy >= 0) {
X t = &new[pos->pcolum];
X if (VALID(t))
X t->kweight += SCKICK;
X#ifdef PSUCC
X else
X scexist = 0;
X#endif
X jsort(ixp + 6, new);
X } else {
X for (y = 0; y < 7; y++)
X ixp[y] = new[y].ppred;
X }
X
X needx = -1;
X unknown = FALSE;
X for (y = 0; y < 7; y++) {
X
X if (unknown) {
X /*
X * Next is rather arbitrary
X */
X if (xl == MINDEPTH + 1 && y > 3)
X break;
X if (xl == MINDEPTH + 2 && y > 1)
X break;
X if (xl == MINDEPTH + 3 && y > 2)
X break;
X if (xl == MINDEPTH + 4 && y > 3)
X break;
X if (xl > MINDEPTH + 4 && y > 2)
X break;
X }
X/* select a move; mark it "done"; continue if it already was. */
X x = ixp[y];
X DONE(new + (x & 15));
X if (!(x & 0xf000)) /* need better "unions", etc. */
X continue;
X x &= 15;
X t = new + x;
X
X/* save a microsecond if it can't stop an immediate win */
X if (needx != -1)
X if (needx != x)
X continue;
X else
X y = 6; /* too tricky */
X else ;
X
X/* set arg5 to a large value if we should do a quick prescan */
X arg5 = quikdepth[t->plytot];
X if (arg5 && xl < MINDEPTH && ! DO_ALL) {
X#ifdef BORING
X qs_did[t->plytot]++;
X#endif
X arg5 += MINDEPTH;
X } else
X arg5 = levy;
X
X/* we come here again if the prescan fails: */
X rescan:
X
X/*
X * alpbet is first set to reflect the logical alpha/beta;
X * then reduced if possible due to a cache hit.
X * totalpbet will be the new abflag for the cache
X */
X if (plymode[t->plytot] & PM_DICOUT)
X alpbet = AB_BOTH;
X else
X alpbet = AB_TRIT;
X
X if (t->p_hp && t->p_hp->abflag) {
X if (alpbet & t->p_hp->abflag) {
X /*
X * Curious but unimportant change of state.
X * Just make a mark on the wall.
X */
X abfunny++;
X val = t->p_hp->valu;
X goto onlyprint;
X } else {
X alpbet = (t->p_hp->abflag == AB_RED)
X ? AB_WHI : AB_RED;
X totalpbet = AB_BOTH|AB_RED|AB_WHI;
X }
X } else
X totalpbet = alpbet == AB_BOTH
X ? (AB_BOTH|AB_RED|AB_WHI) : alpbet;
X
X/* if we're in the middle of a quick search, continue it */
X if (xl > MINDEPTH) {
X val =
XHISANAL(t, alpbet == AB_WHI ? DRAW : RWIN,
X alpbet == AB_RED ? DRAW : WWIN, verbose-1, xl-1);
X if (val == UNK) {
X unknown = TRUE;
X continue;
X } else
X goto analfin;
X }
X
X/* next eliminates a little confusion: */
X if (DO_ALL)
X goto do_all;
X
X if (alpbet == AB_BOTH) {
X if (PM_REDUCE & plymode[t->plytot]) {
X/* apply a heuristic to speed up alpha-beta */
X if (absame[t->plytot] > 2) {
X if (ablast[t->plytot] == RWIN) {
X val =
XHISANAL(t, RWIN, DRAW, verbose-1, arg5);
X if (val == DRAW)
X alpbet = AB_WHI;
X } else {
X val =
XHISANAL(t, DRAW, WWIN, verbose-1, arg5);
X if (val == DRAW)
X alpbet = AB_RED;
X }
X } else {
X val =
XHISANAL(t, RWIN, WWIN, verbose-1, arg5);
X }
X if (val != IMMWIN && val != UNK) {
X if (val == ablast[t->plytot])
X absame[t->plytot]++;
X else {
X absame[t->plytot] = 0;
X if (val != DRAW)
X ablast[t->plytot]=val;
X }
X }
X } else {
X do_all:
X val =
XHISANAL(t, RWIN, WWIN, verbose-1, arg5);
X }
X }
X
X/* alpbet can change above so don't optimize "if" into "else if" */
X if (alpbet == AB_RED)
X val =
XHISANAL(t, RWIN, DRAW, verbose-1, arg5);
X else if (alpbet == AB_WHI)
X val =
XHISANAL(t, DRAW, WWIN, verbose-1, arg5);
X
X/* dispose of unsuccessful quick scan */
X if (val == UNK) {
X arg5 = levy;
X#ifdef BORING
X qs_didnt[t->plytot]++;
X#endif
X goto rescan;
X }
X
X/*
X * save the game-value in the cache.
X * Immediate wins are usually not cached, but we may make an exception
X * at the last ply of a quick-search section.
X */
X analfin:
X if (val != DRAW)
X totalpbet = AB_BOTH|AB_RED|AB_WHI;
X if (t->p_hp) {
X if (val != IMMWIN) {
X htop(t->p_hp, levy-1);
X t->p_hp->valu = val;
X t->p_hp->abflag = totalpbet;
X } else if (PM_IMMOK & plymode[t->plytot]) {
X htop(t->p_hp, levy-1);
X#ifdef RED
X t->p_hp->valu = WWIN;
X#else
X t->p_hp->valu = RWIN;
X#endif
X t->p_hp->abflag = AB_BOTH|AB_RED|AB_WHI;
X }
X }
X
X/* sometimes output to the position dictionary and/or the game book: */
X onlyprint:
X if (PM_DICOUT & plymode[t->plytot] && val != IMMWIN) {
X fprintf(Dic, "%x %x %x %x\n",
X KEY(t)[0], KEY(t)[1], KEY(t)[2], val);
X }
X if (verbose > 0) {
X fprintf(treeshow, "%07d %d %d %d\n", seq++,
X vlevel - verbose, x, val);
X }
X
X/* dispose of immediate wins */
X if (val == IMMWIN) {
X if (x == HISIMMX) ;
X else
X if (needx == -1)
X needx = HISIMMX;
X else
X break;
X continue;
X }
X
X/* and finally, update the real alpha and beta: */
X#ifdef RED
X if (DO_ALL) {
X if (val > fval)
X fval = val;
X } else if (val > beta) {
X if (val >= alpha)
X goto killer;
X else
X beta = val;
X }
X#else
X if (DO_ALL) {
X if (val < fval)
X fval = val;
X } else if (val < alpha) {
X if (val <= beta)
X goto killer;
X else
X alpha = val;
X }
X#endif
X }
X goto fini;
X killed:
X unknown = FALSE;
X#ifdef RED
X beta = alpha;
X#else
X alpha = beta;
X#endif
X fini:
X if (levy > 0) for (t = new; t < new + 7; t++) {
X if (t->p_hp && UNLISTED(t->p_hp))
X hbot(t->p_hp, levy-1);
X }
X
X#ifdef BORING
X /*
X * Update the "accounting" data.
X * (dont come here for immediately-analyzed positions)
X */
X x = pos->plytot;
X i = (cost += COST_ANAL) - oldcost;
X Acc[x].ahits++;
X flwork = i; /* i is too big to be squared as integer */
X Acc[x].amom1 += flwork;
X Acc[x].amom2 += flwork * flwork;
X#endif
X
X#if 0
X if (pos->p_hp /* if we're cached ... */
X && xl < MINDEPTH /* (and not doing quick-search) */
X && i < mincost[xl-1] /* .. but inexpensive ... */
X && !(pos->p_hp->abflag) /* and without prior data */ ) {
X
X /* then lru the cache entry and tell caller to ignore */
X hbot(pos->p_hp, xl - 1);
X pos->p_hp = NULL;
X costfree[xl - 1]++;
X }
X#endif
X
X#ifdef RED
X if (DO_ALL)
X return fval > alpha ? alpha : fval;
X return unknown ? UNK : beta;
X#else
X if (DO_ALL)
X return fval < beta ? beta : fval;
X return unknown ? UNK : alpha;
X#endif
X win:
X MYIMMX = x;
X return IMMWIN;
X
X killer:
X if (needx != -1 || levy < 0)
X goto killed;
X y = t->move;
X for (i = 0; i < 7; i++) {
X if (new[ixp[i] & 15].move == y)
X break;
X }
X if (i == 8)
X fatal("where is killer?");
X if ((ixp[i] & 15) == pos->pcolum) {
X#ifdef PSUCC
X i ? ks3++ : ks0++;
X#endif
X /* apply the reduced awards */
X goto norating; /* temp */
X } else {
X#ifdef PSUCC
X if (scexist)
X (ixp[0] & 15) == pos->pcolum ? ks1++ : ks4++;
X else
X ks2++;
X for (y = i + 1; y < 7; y++)
X if (!(ixp[y] & 0xf000))
X break;
X if (i == 0) ksuccess[y].win++;
X else if (i == 1) ksuccess[y].place++;
X else if (i == 2) ksuccess[y].show++;
X else ksuccess[y].other++;
X#endif
X if (i > 2) {
X if ((QPred[new[ixp[i] & 15].move] += GCBIG << 16)
X & FirstBit)
X fixpred();
X i = 3;
X }
X }
X lp = Rating + 3 * i;
X if (0xf000 & ixp[2]) {
X/*
X * Next MAY be a good idea ... it gives SLIGHT improvement
X * if perfectly tuned, but very bad if not.
X */
X if (++predit >= 10000) {
X predit = 0;
X reducepred(QPred);
X }
X
X for (i = 0; i < 3; i++)
X if ((QPred[new[ixp[i] & 15].move]
X += ((int)(*lp++)) << 16) & FirstBit)
X fixpred();
X } else ; /* otherwise only at most 2 legal moves */
X norating:
X goto killed;
X}
X
X#undef MYANAL
X#undef HISANAL
X#undef QPred
X#undef THMAX
X#undef FOU(Q)
X#undef HISIMMX
X#undef MYIMMX
END_OF_FILE
if test 14031 -ne `wc -c <'anal.h'`; then
echo shar: \"'anal.h'\" unpacked with wrong size!
fi
# end of 'anal.h'
fi
if test -f 'c4.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'c4.c'\"
else
echo shar: Extracting \"'c4.c'\" \(19626 characters\)
sed "s/^X//" >'c4.c' <<'END_OF_FILE'
X
X/*
X * This software is copyright (c) 1988 by
X * James D. Allen
X * 1866 Silvana Lane
X * Santa Cruz CA 95062
X *
X * This notice must not be removed.
X * This software must not be sold for profit.
X * You may redistribute if your distributees have the
X * same rights and restrictions.
X */
X
X#include <stdio.h>
X#define FALSE 0
X#define TRUE 1
X
Xtypedef unsigned char u_char;
Xtypedef unsigned short u_short;
Xtypedef unsigned int u_int;
Xtypedef unsigned long u_long;
X
Xint seq, rarein, abfunny;
Xint vflag;
Xint vlevel, st_kluge = 9999999;
X
X#define FirstBit 0x80000000
X
X#define DIC_PLY_IN 11
XFILE *Dic;
XFILE *treeshow;
X
Xstruct occ {
X u_char red[6], whi[6];
X};
X
X#define ENDED -2
Xint levty[43] = { /* levty set up in main */
X /* 00 01 02 03 04 05 06 07 08 09 */
X 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
X /* 10 11 12 13 14 15 16 17 18 19 */
X 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
X /* 20 21 22 23 24 25 26 27 28 29 */
X 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
X /* 30 31 32 33 34 35 36 37 38 39 */
X 0, 0, 0, 0, 0, 0, 0, 0, -99, -99,
X /* 40 41 42 */
X -99, ENDED, 0,
X};
X
X#define MINDEPTH 1000 /* arbitrary big number */
X
X#include "parameters.h"
X
Xint cursize[NUMT], totsize;
Xint poflow, plydump;
Xint absame[43], ablast[43];
X
X#ifdef BORING /* define this to get various statistics */
X#define PSUCC /* this prints killer prediction success rate */
Xdouble sqrt();
X
Xint reused[NUMT], lostref[NUMT], costfree[NUMT];
Xint examined[43], qxamined[43];
Xint qs_did[43], qs_didnt[43];
Xint nrecy;
X
X/*
X * New statistics about caching:
X */
Xint je_recycled;
Xint je_reaped;
Xint je_refreap;
Xint je_overref;
Xint je_remembered;
X#endif
X
X
X/* The possible "values" of a position: */
X#define RWIN 768
X#define DRAW 512
X#define WWIN 256
X#define IMMWIN 1
X#define INVAL 2
X#define UNK 3
X
X/*
X * The 64 bits called "alpha, beta" are really just a single
X * trit and are handled thus:
X */
X#define AB_RED 1
X#define AB_WHI 2
X#define AB_BOTH 4
X#define AB_TRIT (alpha == DRAW ? AB_WHI : beta == DRAW ? AB_RED : AB_BOTH)
X
Xstruct he {
X struct he *cforw,
X *cback,
X *lru,
X *mru;
X union ug {
X struct occ he_occ;
X u_long he_d[3];
X } h;
X u_short valu;
X u_char refcnt;
X u_char heref:1;
X u_char abflag:7;
X} Htab[SIZH], *Itab[SIZI], Hd[NUMT];
X
X#define Mostru lru
X#define Leastru mru
X#define UNLISTED(x) (!(x)->lru)
X#define Hrm(x) if (UNLISTED(x)) ; else \
X (x)->lru->mru = (x)->mru, \
X (x)->mru->lru = (x)->lru, \
X (x)->lru = NULL
X
Xstruct pos {
X /*
X * `hori' must be first.
X * things copied to child must be prior to `p_hp'.
X */
X struct occ hori,
X dext,
X sini;
X char hei[7],
X vth[7],
X plytot,
X pos_spare;
X /* beyond here not needed for copy */
X struct he* p_hp;
X char move,
X pos_sp1,
X pos_sp2,
X asymetric;
X union pt {
X long u_l;
X struct {
X u_short us1;
X u_char us2,
X us3;
X } u_s;
X } pu;
X} Root, Dicdummy;
X#define ppred pu.u_l
X#define kweight pu.u_s.us1
X#define pcolum pu.u_s.us3
X#define VALID(t) ((t)->pu.u_s.us2 > 15)
X#define DONE(t) ((t)->pu.u_l &= 0xfff)
X
X/* klugy macro for getting at "hori" easily: (assumes hori is first) */
X /* code also relies on sizeof(long) == 4 */
X#define KEY(x) ((long *)(x))
X
Xu_char rimmx, wimmx;
X
Xu_char Four[128] = {
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
X 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
X 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,
X};
X
Xshort Rating[12] = { /* cf USCF rating system */
X 1, -1, 0,
X -9, 10, -1,
X -10, -6, 16,
X -4, -2, -1,
X#define GCBIG (1) /* should be +14 ... why does this work better? */
X};
X
X#define SCKICK 340
X
X#define PREDRED
Xu_char rpb[49*4] = {
X#include "predinit.h"
X};
X#undef PREDRED
X
X#define PREDWHITE
Xu_char wpb[49*4] = {
X#include "predinit.h"
X};
X#undef PREDWHITE
X
Xu_char pdefaults[49*4] = {
X#include "predinit.h"
X};
X
X#define rpred ((long *)(rpb))
X#define wpred ((long *)(wpb))
X
X
X#ifdef BORING
X/* costing data: */
Xlong cost = 0; /* total expenditure of energy */
Xstruct acctg {
X float amom1, amom2;
X long ahits;
X} Acc[43];
X/* Stupid temporary values: */
X#define COST_ANAL 1 /* cost of calling anal */
X#define COST_TAB 0 /* minimum cost per table entry */
X#define COST_KTAB 0 /* minimum cost per table entry */
X#endif
X
X#ifdef PSUCC
Xstruct {
X int win,
X place,
X show,
X other;
X} ksuccess[8];
Xint ks0, ks1, ks2, ks3, ks4;
X
Xpksucc()
X{
X int i, j;
X
X fprintf(stderr, "\n");
X for (i = 0; i < 43; i++) if (qs_did[i]) {
X fprintf(stderr,
X"Level %2d: %9d quick scans of which %9d were successful\n",
X i, qs_did[i], qs_did[i] - qs_didnt[i]);
X }
X fprintf(stderr, "\n");
X fprintf(stderr, "Cost accounting:\n");
X for (i = 0; i < 43; i++) if (j = Acc[i].ahits) {
X fprintf(stderr, "%9d hits at ply %2d cost:", j, i);
X showstat(Acc[i].amom1, Acc[i].amom2, j);
X }
X
X fprintf(stderr, "\nKiller prediction results:\n");
X for (i = 1; i < 8; i++) {
X fprintf(stderr,
X"%3d lgl moves- 1st=%8d 2nd=%8d 3rd=%8d other=%8d\n",
X i, ksuccess[i].win, ksuccess[i].place,
X ksuccess[i].show, ksuccess[i].other);
X }
X fprintf(stderr, " %9d positions where SC was first and killer\n",
X ks0);
X fprintf(stderr, " %9d positions where SC was first and not killer\n",
X ks1);
X fprintf(stderr, " %9d positions where SC wasnt first and killer\n",
X ks3);
X fprintf(stderr, " %9d positions where SC wasnt first and not killer\n",
X ks4);
X fprintf(stderr, " %9d positions where SC not considered\n",
X ks2);
X}
X#endif
X
Xfatal(a, b, c, d, e, f)
X{
X fprintf(stderr, a, b, c, d, e, f);
X fprintf(stderr, "\n");
X#ifdef BORING
X dumppred();
X printh();
X#endif
X exit(1);
X}
X
Xindex (c, s) u_char c, *s;
X{
X int i;
X for (i = 0; *s; i++)
X if (c == *s++)
X return i;
X return -1;
X}
X
Xstruct he *newhe(Tnum)
X{
X register struct he *h;
X
X if (cursize[Tnum] >= maxsize[Tnum]) {
X h = Hd[Tnum].Leastru;
X if (!h)
X fatal("Bad least list");
X if (h->refcnt > 20 && !h->heref) {
X#ifdef BORING
X je_remembered += h->refcnt - 1;
X je_recycled++;
X#endif
X h->refcnt = 0;
X h->heref = 1;
X htop(h, Tnum);
X h = Hd[Tnum].Leastru;
X }
X#ifdef BORING
X if (h->heref) {
X je_reaped++;
X je_refreap += h->refcnt - 1;
X }
X if (h->abflag)
X reused[Tnum]++;
X else
X nrecy++;
X if (h->refcnt > 1)
X lostref[Tnum] += h->refcnt - 1;
X#endif
X Hrm(h);
X if (h->cforw)
X h->cforw->cback = h->cback;
X h->cback->cforw = h->cforw;
X } else {
X cursize[Tnum]++;
X h = Htab + totsize++;
X }
X h->abflag = 0;
X h->refcnt = 0;
X h->heref = 0;
X h->cforw = h->lru = h->mru = NULL;
X return h;
X}
X
Xstruct he **gethe(pos)
X struct pos *pos;
X{
X u_int hix;
X register struct he **hp;
X#define Vp ((u_long *) pos->hori.red)
X
X hix = Vp[0] + Vp[1] + Vp[2];
X for (hp = Itab + hix % SIZI; *hp; hp = (struct he **)*hp)
X if (!memcmp((*hp)->h.he_d, Vp, sizeof(union ug)))
X break;
X return hp;
X}
X
X#define RED
X#include "anal.h"
X#undef RED
X#include "anal.h"
X
Xjsort(ixp, t)
X register u_long *ixp;
X register struct pos *t;
X{
X register u_long p, pwin, pplace, pshow;
X
X pwin = t++->ppred;
X p = t++->ppred;
X#define SM1 if (p < pwin) pplace = p; else pplace = pwin, pwin = p;
X SM1;
X p = t++->ppred;
X if ( p < pplace)
X pshow = p;
X else {
X pshow = pplace;
X SM1;
X }
X#define SM2 if (p < pplace) if (p < pshow) *ixp-- = p; \
X else *ixp-- = pshow, pshow = p; \
X else { *ixp-- = pshow; pshow = pplace; SM1 }
X p = t++->ppred;
X SM2;
X p = t++->ppred;
X SM2;
X p = t++->ppred;
X SM2;
X p = t->ppred;
X SM2;
X *ixp-- = pshow;
X *ixp-- = pplace;
X *ixp = pwin;
X}
X
Xcatcher()
X{
X fatal("Terminated by operator");
X}
X
Xmain(argc, argv)
X char *argv[];
X{
X
X int i,j, tothash = 0;
X
X if (argc >= 2 && !strcmp(argv[1], "-v")) {
X vflag = 1;
X argc--, argv++;
X }
X if (argc >= 2) {
X vlevel = atoi(argv[1]);
X argc--, argv++;
X } else
X vlevel = 4;
X if (argc >= 9) {
X usage:
X fprintf(stderr,
X"Usage: c4 [-v] Vlevel [N1 N2 N3 ...]\n where N? is the ply for the hashing\n");
X exit(2);
X }
X fprintf(stderr, "Compiled with %s\n", PARMS);
X i = NUMT;
X while (--argc > 0)
X hashedply[--i] = atoi(*++argv);
X for (i = 0; i < NUMT; i++) {
X tothash += (maxsize[i] *= SSS);
X j = hashedply[i];
X if (j < 0 || j > 40)
X goto usage;
X levty[j] = i+1;
X fprintf(stderr,
X"Allocating hash table of size %d for ply %d\n",
X maxsize[i], j);
X }
X if (tothash != SIZH) {
X fprintf(stderr, "Hash size/%d: exp=%d act=%d\n",
X SSS, SIZH/SSS, tothash/SSS);
X if (tothash > SIZH)
X exit(1);
X }
X fprintf(stderr, "sckick = %d\n", SCKICK);
X
X hinit();
X
X signal(2, catcher);
X Root.pcolum = 3;
X#ifdef BORING
X dumppred();
X#endif
X driver(&Root);
X fatal("Exit from main");
X}
X
Xint revtable[128] = {
X0, 64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120,
X4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124,
X2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122,
X6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126,
X1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121,
X5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125,
X3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123,
X7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127,
X};
X
Xsetupdic(p)
X struct pos *p;
X{
X static int beenhere = 0;
X int diclevy, dicval;
X int d_size = 0, d_used = 0;
X int i, kk, mm, symflag;
X int symmy = 0, mir_redund = 0, mir_use = 0;
X
X if (beenhere++)
X return;
X if ((diclevy = levty[DIC_PLY_IN] - 1) < 0) {
X fprintf(stderr, "No table for Dictionary\n");
X exit(2);
X }
X
X if (!(Dic = fopen("Dictionary", "r"))) {
X dicerr:
X fprintf(stderr, "Error opening Dictionary\n");
X exit(2);
X }
X while (4 == fscanf(Dic, "%x %x %x %x\n",
X KEY(&Dicdummy), KEY(&Dicdummy)+1,
X KEY(&Dicdummy)+2, &dicval)) {
X struct he *hp, **hpp;
X
X d_size++;
X for (i = 0; i < 6; i++) {
X if (Dicdummy.hori.red[i] & p->hori.whi[i])
X break;
X if (Dicdummy.hori.whi[i] & p->hori.red[i])
X break;
X }
X if (i != 6)
X continue;
X d_used++;
X
X if (!(*(hpp = gethe(&Dicdummy)))) {
X hp = newhe(diclevy);
X if (hp == (struct he *)hpp) {
X fprintf(stderr, "Dictionary overflow\n");
X exit(2);
X }
X *hpp = hp;
X/* next relies on 'red' first in struct ... need smarter union */
X memcpy(hp->h.he_d, Dicdummy.hori.red, 12);
X hp->cback = (struct he *)hpp;
X htop(hp, diclevy);
X hp->valu = dicval;
X hp->abflag = AB_BOTH|AB_RED|AB_WHI;
X } else {
X fprintf(stderr, "Duplicate in Dictionary\n");
X exit(2);
X }
X }
X fprintf(stderr, "Used %d out of %d dictionary entries.\n",
X d_used, d_size);
X fclose(Dic);
X
X if (!(Dic = fopen("Dictionary", "r")))
X goto dicerr;
X while (4 == fscanf(Dic, "%x %x %x %x\n",
X KEY(&Dicdummy), KEY(&Dicdummy)+1,
X KEY(&Dicdummy)+2, &dicval)) {
X struct he *hp, **hpp;
X
X symflag = TRUE;
X for (i = 0; i < 6; i++) {
X kk = Dicdummy.hori.whi[i];
X if (kk < 0 || kk > 127)
X goto badkk;
X mm = revtable[kk];
X if (mm != kk)
X symflag = FALSE;
X Dicdummy.hori.whi[i] = mm;
X kk = Dicdummy.hori.red[i];
X if (kk < 0 || kk > 127) {
X badkk:
X fprintf(stderr, "Bad kk\n");
X exit(1);
X }
X mm = revtable[kk];
X if (mm != kk)
X symflag = FALSE;
X Dicdummy.hori.red[i] = mm;
X }
X if (symflag) {
X symmy++;
X continue;
X }
X for (i = 0; i < 6; i++) {
X if (Dicdummy.hori.red[i] & p->hori.whi[i])
X break;
X if (Dicdummy.hori.whi[i] & p->hori.red[i])
X break;
X }
X if (i != 6)
X continue;
X
X if (!(*(hpp = gethe(&Dicdummy)))) {
X hp = newhe(diclevy);
X if (hp == (struct he *)hpp) {
X fprintf(stderr, "Dictionary overflow\n");
X exit(2);
X }
X *hpp = hp;
X memcpy(hp->h.he_d, Dicdummy.hori.red, 12);
X hp->cback = (struct he *)hpp;
X htop(hp, diclevy);
X hp->valu = dicval;
X hp->abflag = AB_BOTH|AB_RED|AB_WHI;
X mir_use++;
X } else {
X mir_redund++;
X }
X }
X
X fprintf(stderr, "Mirror: %d symet, %d usable but redundant, %d usable\n",
X symmy, mir_redund, mir_use);
X fclose(Dic);
X/* usually DIC_PLY_IN == DIC_PLY_OUT && "ln -s Dictionary Dict.out" */
X if (!(Dic = fopen("Dict.out", "a")))
X goto dicerr;
X setlinebuf(Dic);
X}
X
Xdriver(p)
X struct pos *p;
X{
X struct pos new;
X int a, b, c, x, y, white;
X int excode;
X FILE *Factfile;
X
X white = p->plytot & 1;
X next:
X do c = getchar();
X while ((unsigned) c <= ' ');
X if (c == EOF) {
X fatal("EOF");
X }
X x = index(c, (!white) ? "abcdefg" : "ABCDEFG");
X if (x >= 0) {
X fprintf(stderr, "Warning: false input move order\n");
X white ^= 1;
X }
X x = index(c, white ? "abcdefg" : "ABCDEFG");
X if (x >= 0) {
X memcpy(&new, p, sizeof (new));
X if (x != 3)
X new.asymetric = 1;
X y = p->hei[x];
X new.hei[x] = y + 1;
X new.plytot++;
X new.ppred = (white ? wpred : rpred)[new.move = x*7 + y];
X if (!VALID(&new))
X goto badinp;
X if (new.vth[x] == (white ? -3 : 3))
X goto victory;
X#define FOU(Q) (Four[new.Q[y] |= 1 << x])
X if (!white) {
X if (FOU(hori.red))
X goto victory;
X if ((y = x-y+2) >= 0 && y < 6 && FOU(dext.red))
X goto victory;
X if ((y += 6-x-x) >= 0 && y < 6 && FOU(sini.red))
X goto victory;
X y = new.vth[x];
X new.vth[x] = (y < 0) ? 1 : y+1;
X } else {
X if (FOU(hori.whi))
X goto victory;
X if ((y = x-y+2) >= 0 && y < 6 && FOU(dext.whi))
X goto victory;
X if ((y += 6-x-x) >= 0 && y < 6 && FOU(sini.whi))
X goto victory;
X y = new.vth[x];
X new.vth[x] = (y > 0) ? -1 : y-1;
X }
X if (new.plytot == 42)
X goto victory;
X driver(&new);
X goto next;
X victory:
X fatal("Game over");
X badinp:
X fatal("Illegal move");
X }
X switch (index(c, "+-=.")) {
X case 0: /* + */
X a = RWIN; b = DRAW;
X fprintf(stderr, "Looking for Red victory\n");
X goto callit;
X case 1: /* - */
X a = DRAW; b = WWIN;
X fprintf(stderr, "Looking for White victory\n");
X goto callit;
X case 2: /* = */
X a = RWIN; b = WWIN;
X fprintf(stderr, "Looking for total solution\n");
X callit:
X plydump = p->plytot + 3;
X fprintf(stderr, "Driver: plytot = %d\n", p->plytot);
X dumppos(p, stderr);
X
X
X treeshow = popen(
X"sort -r | ./showtree | pr -4 >> The_Game_Tree", "w");
X setlinebuf(treeshow);
X if (white) seq += 999999;
X fprintf(treeshow,
X"%07d %d 6\n", st_kluge--, vlevel); /* hack for showtree */
X
X/* 6 is number of lines for showtree to ignore */
X dumppos(p, treeshow);
X setupdic(p);
X c = (white ? wanal : ranal)(p, a, b, vlevel, 0);
X
X excode = pclose(treeshow);
X fprintf(stderr, "Treeshow exited with %x\n", excode);
X treeshow = 0; /* needed for "file == treeshow" below */
X
X fprintf(stderr, "value = %d\n", c);
X
X if (!(Factfile = fopen("Facts", "a")))
X fatal("Bad Facts file");
X dumppos(p, Factfile);
X if (c == RWIN)
X fprintf(Factfile, "\tRed Wins\n\n");
X else if (c == WWIN)
X fprintf(Factfile, "\tWhite Wins\n\n");
X else if (c != DRAW)
X fprintf(Factfile, "\t???\n\n");
X else if (a == DRAW)
X fprintf(Factfile, "\tWhite does NOT Win\n\n");
X else if (b == DRAW)
X fprintf(Factfile, "\tRed does NOT Win\n\n");
X else
X fprintf(Factfile, "\tDrawn Game\n\n");
X fclose(Factfile);
X return; /* let prev "driver" take over */
X default:
X goto next;
X case 3: /* . */
X return;
X }
X}
X
Xfixpred()
X{
X int i;
X
X for (i = 0; i < 49*4; i += 4) {
X switch (wpb[i] & 0xc0) {
X case 0x80:
X wpb[i] = 0x7c;
X poflow++;
X break;
X case 0xc0:
X wpb[i] = 0x01;
X poflow++;
X case 0x00:
X case 0x40:
X break;
X }
X switch (rpb[i] & 0xc0) {
X case 0x80:
X rpb[i] = 0x7c;
X poflow++;
X break;
X case 0xc0:
X rpb[i] = 0x01;
X poflow++;
X case 0x00:
X case 0x40:
X break;
X }
X }
X}
X
Xreducepred(pp)
X register short *pp; /* passed as a (long *) -- sorry :-} */
X{
X register short i, j;
X register short *pq = (short *)pdefaults;
X
X for (i = 0; i < 49; i++, pp += 2, pq += 2)
X if ((j = *pp) > 0)
X *pp -= ((j - *pq) / 8);
X}
X
Xhinit()
X{
X struct he *h;
X int i;
X
X for (h = Hd; h < Hd + NUMT; h++)
X h->Leastru = h->Mostru = h;
X for (i = 0; i < NUMT; i++) {
X cursize[i] = 0;
X#ifdef BORING
X reused[i] = lostref[i] = costfree[i] = 0;
X#endif
X }
X#ifdef BORING
X nrecy = abfunny = rarein = totsize = poflow = 0;
X#endif
X bzero(Itab, sizeof(Itab));
X}
X
Xhtop(h, Tnum)
X struct he *h;
X{
X Hrm(h);
X if (h->refcnt++ == 255) {
X h->refcnt = 1;
X#ifdef BORING
X je_overref++;
X#endif
X }
X Hd[Tnum].Mostru->mru = h;
X h->mru = Hd + Tnum;
X h->lru =Hd[Tnum].Mostru;
X Hd[Tnum].Mostru = h;
X}
X
Xhbot(h, Tnum)
X struct he *h;
X{
X Hrm(h);
X Hd[Tnum].Leastru->lru = h;
X h->lru = Hd + Tnum;
X h->mru =Hd[Tnum].Leastru;
X Hd[Tnum].Leastru = h;
X}
X
X#ifdef BORING
Xprinth() /* show hash usage */
X{
X float f1, f2, fr1, fr2;
X struct he **hp, *h;
X int j, i, k;
X int totexam = 0;
X
X for (i = 0; i < 43; i++)
X if (j = examined[i]) {
X totexam += j;
X fprintf(stderr,
X"Examined %9d positions at level %d (%d in restricted search)\n",
X j, i, qxamined[i]);
X }
X fprintf(stderr, "Total number of positions examined = %d\n",
X totexam);
X fprintf(stderr, "Number of rare collide incidents = %d\n",
X rarein);
X fprintf(stderr, "Number of pred table overflow incidents = %d\n",
X poflow);
X fprintf(stderr, "Number of humorous A-B incidents = %d\n",
X abfunny);
X fprintf(stderr, "Number of null table entries recycled = %d\n",
X nrecy);
X for (i = 14; i < 30; i += 3) if (examined[i]) {
X fprintf(stderr, "Fanout from %d to %d = %d\n", i, i+6,
X (examined[i]/2 + examined[i+6])/examined[i]);
X }
X fprintf(stderr, "\n");
X
X fprintf(stderr,
X"The tiny reference counters overflowed %d times\n", je_overref);
X fprintf(stderr,
X"Of %d recyc-lrus (with %d hits),\n\t%d were later reaped for a total of %d rehits\n",
X je_recycled, je_remembered, je_reaped, je_refreap);
X pksucc();
X fprintf(stderr, "\n");
X if (!vflag)
X return;
X
X for (i = 0; i < NUMT; i++) {
X fprintf(stderr, "\nTable %d (Ply %d) has %d entries\n",
X i, hashedply[i], cursize[i]);
X fprintf(stderr, " reused = %d lostref = %d low_cost = %d\n",
X reused[i], lostref[i], costfree[i]);
X k = 0;
X fr1 = fr2 = 0.0;
X for (h = Hd[i].Mostru; h != Hd + i; h = h->lru) {
X k++;
X j = h->refcnt - 1;
X if (j > 0) {
X fr1 += j;
X fr2 += j * j;
X }
X }
X if (k) {
X fprintf(stderr,
X" Re-ref rate, Table %d (k=%d): ", i, k);
X showstat(fr1, fr2, k);
X }
X }
X
X k = 0;
X fr1 = fr2 = 0.0;
X f1 = f2 = 0.0;
X for (i = 0; i < SIZI; i++) {
X hp = &Itab[i];
X for (j = 0; *hp; hp = (struct he **)*hp, j++) {
X k++;
X fr1 += (*hp)->refcnt;
X fr2 += (*hp)->refcnt * (*hp)->refcnt;
X }
X f1 += j;
X f2 += j * j;
X }
X fprintf(stderr, "\nTotsize = %d k = %d\n", totsize, k);
X if (!k)
X return;
X fprintf(stderr, "Hash collision rate: ");
X showstat(f1, f2, SIZI);
X fprintf(stderr, "Hash reference rate: ");
X showstat(fr1, fr2, k);
X}
X
Xshowstat(f1, f2, n)
X float f1, f2;
X{
X f1 /= n;
X f2 /= n;
X f2 -= f1 * f1;
X fprintf(stderr, " Mean= %f StdDev= %f\n",
X f1, f2 < 0.0000001 ? 0.0 : sqrt(f2));
X}
X#endif
X
Xdumppos(pos, file)
X struct pos *pos;
X FILE *file;
X{
X int i;
X char w, pp[6][8];
X
X for (i = 0; i < 6; i++) {
X strcpy(&pp[i][0], "-------");
X w = pos->hori.red[i];
X subdump(w, 'X', &pp[i][0]);
X w = pos->hori.whi[i];
X subdump(w, 'O', &pp[i][0]);
X }
X if (file == treeshow)
X fprintf(file, "%07dInput: %s\n", st_kluge, &pp[5][0]);
X else
X fprintf(file, "Position: %s\n", &pp[5][0]);
X for (i = 4; i >= 0; i--)
X if (file == treeshow)
X fprintf(file, "%07d %s\n",st_kluge--, &pp[i][0]);
X else
X fprintf(file, " %s\n", &pp[i][0]);
X}
X
Xsubdump(w, c, s)
X u_char c, *s;
X{
X w &= 0xff;
X for (; w; w >>= 1, s++)
X if (w & 1)
X *s = c;
X}
X
X#ifdef BORING
Xdumppred()
X{
X int i, j;
X
X fprintf(stderr, "Rpred:\n\t");
X for (i = 0; i < 49; i += 7) {
X for (j = i; j < i + 7; j++)
X fprintf(stderr, "%08x ", rpred[j]);
X fprintf(stderr, "\n\t");
X }
X fprintf(stderr, "\nWpred:\n\t");
X for (i = 0; i < 49; i += 7) {
X for (j = i; j < i + 7; j++)
X fprintf(stderr, "%08x ", wpred[j]);
X fprintf(stderr, "\n\t");
X }
X fprintf(stderr, "\n");
X}
X#endif
END_OF_FILE
if test 19626 -ne `wc -c <'c4.c'`; then
echo shar: \"'c4.c'\" unpacked with wrong size!
fi
# end of 'c4.c'
fi
if test -f 'do_conn4' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'do_conn4'\"
else
echo shar: Extracting \"'do_conn4'\" \(124 characters\)
sed "s/^X//" >'do_conn4' <<'END_OF_FILE'
X#!/bin/sh
Xcat Game.$2 > Info.$2
X(./c4 -v $1 < Game.$2) 2>> Info.$2
X/bin/echo -n " " >> Info.$2
Xcat The_Game_Tree >> Info.$2
END_OF_FILE
if test 124 -ne `wc -c <'do_conn4'`; then
echo shar: \"'do_conn4'\" unpacked with wrong size!
fi
chmod +x 'do_conn4'
# end of 'do_conn4'
fi
if test -f 'parameters.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'parameters.h'\"
else
echo shar: Extracting \"'parameters.h'\" \(1291 characters\)
sed "s/^X//" >'parameters.h' <<'END_OF_FILE'
X#define PARMS "parms.new"
X
X/* codes for "plymode: */
X#define PM_DICOUT 1 /* dictionary output ply */
X#define PM_REDUCE 2 /* reduce alpha-beta here */
X#define PM_IMMOK 4 /* cache immediate wins */
X
Xint plymode[43] = {
X/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 */
X 0, 0, 0, 0, 2, 2, 2, 2, 4, 1, 6, 4, 3, 6, 6, 4, 6, 2, 0, 6,
X/* 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 */
X 4, 4, 6, 4, 6, 4, 6, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0,
X/* 40 41 42 */
X 0, 0, 0,
X};
Xint quikdepth[43] = {
X/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 */
X 0, 0, 0,11, 0, 0, 9, 0, 6, 0, 9, 0, 0, 0, 7, 0, 0, 4, 0, 5,
X/* 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 */
X 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
X/* 40 41 42 */
X 0, 0, 0,
X};
X
X#ifdef mc68000 /* really should be mem = 4Meg */
X#define SSS 13
X#else
X#define SSS 132 /* preposterously large for 32meg machine */
X#endif
X
X#define SIZH (3203*SSS) /* sum of maxsize table */
X#define SIZI (863*SSS)
X#define NUMT 25
X
Xint maxsize[NUMT] = {
X 1,1,1,2,9,15,900, 20, 9, 25, 40, 63,160,200,150,190,290,
X 140,110,150,200,187,175,100, 65, };
X
Xint hashedply[NUMT] = {
X 5,6,7,8,9,10, 11, 12,13, 14, 15, 16, 17, 18, 19, 20, 21,
X 22, 23, 25, 27, 29, 31, 33, 35, };
END_OF_FILE
if test 1291 -ne `wc -c <'parameters.h'`; then
echo shar: \"'parameters.h'\" unpacked with wrong size!
fi
# end of 'parameters.h'
fi
if test -f 'predinit.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'predinit.h'\"
else
echo shar: Extracting \"'predinit.h'\" \(1023 characters\)
sed "s/^X//" >'predinit.h' <<'END_OF_FILE'
X#define APLUS 72
X#define A 71
X#define BPLUS 70
X#define B 69
X#define CPLUS 68
X#define C 67
X#define DPLUS 66
X#define D 65
X#define F 64
X
X#define V 31
X#define AVG 0
X
X DPLUS, AVG, V, 0,
X F, AVG, V, 0,
X D, AVG, V, 0,
X DPLUS, AVG, V, 0,
X D, AVG, V, 0,
X DPLUS, AVG, V, 0,
X 0, 0, 0, 0,
X
X D, AVG, V, 1,
X DPLUS, AVG, V, 1,
X F, AVG, V, 1,
X C, AVG, V, 1,
X BPLUS, AVG, V, 1,
X B, AVG, V, 1,
X 0, 0, 0, 1,
X
X B, AVG, V, 2,
X B, AVG, V, 2,
X BPLUS, AVG, V, 2,
X CPLUS, AVG, V, 2,
X BPLUS, AVG, V, 2,
X A, AVG, V, 2,
X 0, 0, 0, 2,
X
X B, AVG, V, 3,
X B, AVG, V, 3,
X A, AVG, V, 3,
X C, AVG, V, 3,
X BPLUS, AVG, V, 3,
X A, AVG, V, 3,
X 0, 0, 0, 3,
X
X B, AVG, V, 4,
X B, AVG, V, 4,
X BPLUS, AVG, V, 4,
X CPLUS, AVG, V, 4,
X BPLUS, AVG, V, 4,
X A, AVG, V, 4,
X 0, 0, 0, 4,
X
X D, AVG, V, 5,
X DPLUS, AVG, V, 5,
X F, AVG, V, 5,
X C, AVG, V, 5,
X BPLUS, AVG, V, 5,
X B, AVG, V, 5,
X 0, 0, 0, 5,
X
X DPLUS, AVG, V, 6,
X F, AVG, V, 6,
X D, AVG, V, 6,
X DPLUS, AVG, V, 6,
X D, AVG, V, 6,
X DPLUS, AVG, V, 6,
X 0, 0, 0, 6,
X
X#undef A
X#undef B
X#undef C
X#undef D
X#undef F
X#undef V
X#undef AVG
END_OF_FILE
if test 1023 -ne `wc -c <'predinit.h'`; then
echo shar: \"'predinit.h'\" unpacked with wrong size!
fi
# end of 'predinit.h'
fi
if test -f 'showtree.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'showtree.c'\"
else
echo shar: Extracting \"'showtree.c'\" \(1660 characters\)
sed "s/^X//" >'showtree.c' <<'END_OF_FILE'
X
X#include <stdio.h>
X
X/*
X * RWIN, etc. stupidly hardcoded here.
X */
X
X/*
X * Input format:
X *
X * First line:i %d %d %d =Seq, Numlev, K
X * Next K lines: "whatever" * K
X * Rest of file: %d %d %d %d =Seq, Level, move, value
X */
Xmain()
X{
X int seq, lvl, mov, val;
X int ignory, numlev = 0, i, lastlvl = -99;
X char out[100];
X char *rep = " ";
X int theval, whity, lwhity, nwhity;
X
X i = scanf("%d %d %d\n", &seq, &numlev, &ignory);
X printf("\n\n");
X while (ignory--) {
X gets(out);
X printf("%s\n", out+7);
X }
X printf("\n\n");
X printf("\n\n");
X rep[numlev*3+1] = '\n';
X rep[numlev*3+2] = '\0';
X strcpy(out, rep);
X loop:
X i = scanf("%d %d %d %d\n", &seq, &lvl, &mov, &val);
X if (seq > 99999) {
X whity = 0;
X lwhity = numlev & 1;
X } else {
X whity = 1;
X lwhity = (~numlev) & 1;
X }
X/* whity is true when red makes the first move */
X/* lwhity is true when white makes the last move */
X/* nwhity is true when white makes this move */
X nwhity = ((~whity) ^ lvl) & 1;
X if (i < 4) {
X printf(out);
X exit(0);
X }
X if (val < 256)
X goto loop;
X if (lvl == numlev-1 && (nwhity ? val > 512 : val < 512))
X goto loop;
X#ifdef oldway
X if (lvl == numlev - 1)
X if (val == 1 || val == (lwhity ? 768 : 256) || val == theval)
X goto loop;
X#endif
X if (lvl == numlev - 2)
X theval = val;
X if (lvl <= lastlvl) {
X printf(out);
X strcpy(out, rep);
X }
X lastlvl = lvl;
X i = lvl * 3 + 1;
X out[i] = mov + (((whity ^ lvl) & 1) ? 'A' : 'a');
X if (val == 768)
X out[i+1] = '+';
X else if (val == 256)
X out[i+1] = '-';
X else if (val == 512)
X out[i+1] = '=';
X else
X out[i+1] = '?';
X goto loop;
X}
END_OF_FILE
if test 1660 -ne `wc -c <'showtree.c'`; then
echo shar: \"'showtree.c'\" unpacked with wrong size!
fi
# end of 'showtree.c'
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0