From 02e921727a5f9fee1d5d8beae4dfa197b976f86e Mon Sep 17 00:00:00 2001 From: downsj Date: Mon, 16 Dec 1996 06:56:07 +0000 Subject: [PATCH] Import of gomoku from 4.4BSD Lite2. Uses ocurses. --- games/gomoku/Makefile | 11 + games/gomoku/bdinit.c | 247 +++++++ games/gomoku/bdisp.c | 276 ++++++++ games/gomoku/gomoku.6 | 94 +++ games/gomoku/gomoku.h | 267 +++++++ games/gomoku/main.c | 533 ++++++++++++++ games/gomoku/makemove.c | 302 ++++++++ games/gomoku/pickmove.c | 1480 +++++++++++++++++++++++++++++++++++++++ games/gomoku/stoc.c | 107 +++ 9 files changed, 3317 insertions(+) create mode 100644 games/gomoku/Makefile create mode 100644 games/gomoku/bdinit.c create mode 100644 games/gomoku/bdisp.c create mode 100644 games/gomoku/gomoku.6 create mode 100644 games/gomoku/gomoku.h create mode 100644 games/gomoku/main.c create mode 100644 games/gomoku/makemove.c create mode 100644 games/gomoku/pickmove.c create mode 100644 games/gomoku/stoc.c diff --git a/games/gomoku/Makefile b/games/gomoku/Makefile new file mode 100644 index 00000000000..97c4fb5ef23 --- /dev/null +++ b/games/gomoku/Makefile @@ -0,0 +1,11 @@ +# $OpenBSD: Makefile,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ +# @(#)Makefile 8.1 (Berkeley) 7/24/94 + +PROG= gomoku +SRCS= bdinit.c bdisp.c main.c makemove.c pickmove.c stoc.c +MAN= gomoku.6 +DPADD= ${LIBOCURSES} ${LIBTERMCAP} +LDADD= -locurses -ltermcap +HIDEGAME=hidegame + +.include diff --git a/games/gomoku/bdinit.c b/games/gomoku/bdinit.c new file mode 100644 index 00000000000..d86e3ef5c80 --- /dev/null +++ b/games/gomoku/bdinit.c @@ -0,0 +1,247 @@ +/* $OpenBSD: bdinit.c,v 1.1.1.1 1996/12/16 06:56:07 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)bdinit.c 8.2 (Berkeley) 5/3/95"; +#endif /* not lint */ + +#include +#include "gomoku.h" + +bdinit(bp) + struct spotstr *bp; +{ + register int i, j, r; + register struct spotstr *sp; + register struct combostr *cbp; + + movenum = 1; + + /* mark the borders as such */ + sp = bp; + for (i = BSZ2; --i >= 0; sp++) { + sp->s_occ = BORDER; /* top border */ + sp->s_flg = BFLAGALL; + } + + /* fill entire board with EMPTY spots */ + memset(frames, 0, sizeof(frames)); + cbp = frames; + for (j = 0; ++j < BSZ1; sp++) { /* for each row */ + for (i = 0; ++i < BSZ1; sp++) { /* for each column */ + sp->s_occ = EMPTY; + sp->s_flg = 0; + sp->s_wval = 0; + if (j < 5) { + /* directions 1, 2, 3 are blocked */ + sp->s_flg |= (BFLAG << 1) | (BFLAG << 2) | + (BFLAG << 3); + sp->s_fval[BLACK][1].s = MAXCOMBO; + sp->s_fval[BLACK][2].s = MAXCOMBO; + sp->s_fval[BLACK][3].s = MAXCOMBO; + sp->s_fval[WHITE][1].s = MAXCOMBO; + sp->s_fval[WHITE][2].s = MAXCOMBO; + sp->s_fval[WHITE][3].s = MAXCOMBO; + } else if (j == 5) { + /* five spaces, blocked on one side */ + sp->s_fval[BLACK][1].s = 0x500; + sp->s_fval[BLACK][2].s = 0x500; + sp->s_fval[BLACK][3].s = 0x500; + sp->s_fval[WHITE][1].s = 0x500; + sp->s_fval[WHITE][2].s = 0x500; + sp->s_fval[WHITE][3].s = 0x500; + } else { + /* six spaces, not blocked */ + sp->s_fval[BLACK][1].s = 0x401; + sp->s_fval[BLACK][2].s = 0x401; + sp->s_fval[BLACK][3].s = 0x401; + sp->s_fval[WHITE][1].s = 0x401; + sp->s_fval[WHITE][2].s = 0x401; + sp->s_fval[WHITE][3].s = 0x401; + } + if (i > (BSZ - 4)) { + /* directions 0, 1 are blocked */ + sp->s_flg |= BFLAG | (BFLAG << 1); + sp->s_fval[BLACK][0].s = MAXCOMBO; + sp->s_fval[BLACK][1].s = MAXCOMBO; + sp->s_fval[WHITE][0].s = MAXCOMBO; + sp->s_fval[WHITE][1].s = MAXCOMBO; + } else if (i == (BSZ - 4)) { + sp->s_fval[BLACK][0].s = 0x500; + sp->s_fval[WHITE][0].s = 0x500; + /* if direction 1 is not blocked */ + if (!(sp->s_flg & (BFLAG << 1))) { + sp->s_fval[BLACK][1].s = 0x500; + sp->s_fval[WHITE][1].s = 0x500; + } + } else { + sp->s_fval[BLACK][0].s = 0x401; + sp->s_fval[WHITE][0].s = 0x401; + if (i < 5) { + /* direction 3 is blocked */ + sp->s_flg |= (BFLAG << 3); + sp->s_fval[BLACK][3].s = MAXCOMBO; + sp->s_fval[WHITE][3].s = MAXCOMBO; + } else if (i == 5 && + !(sp->s_flg & (BFLAG << 3))) { + sp->s_fval[BLACK][3].s = 0x500; + sp->s_fval[WHITE][3].s = 0x500; + } + } + /* + * Allocate a frame structure for non blocked frames. + */ + for (r = 4; --r >= 0; ) { + if (sp->s_flg & (BFLAG << r)) + continue; + cbp->c_combo.s = sp->s_fval[BLACK][r].s; + cbp->c_vertex = sp - board; + cbp->c_nframes = 1; + cbp->c_dir = r; + sp->s_frame[r] = cbp; + cbp++; + } + } + sp->s_occ = BORDER; /* left & right border */ + sp->s_flg = BFLAGALL; + } + + /* mark the borders as such */ + for (i = BSZ1; --i >= 0; sp++) { + sp->s_occ = BORDER; /* bottom border */ + sp->s_flg = BFLAGALL; + } + + sortframes[BLACK] = (struct combostr *)0; + sortframes[WHITE] = (struct combostr *)0; + init_overlap(); +} + +/* + * Initialize the overlap array. + * Each entry in the array is a bit mask with eight bits corresponding + * to whether frame B overlaps frame A (as indexed by overlap[A * FAREA + B]). + * The eight bits coorespond to whether A and B are open ended (length 6) or + * closed (length 5). + * 0 A closed and B closed + * 1 A closed and B open + * 2 A open and B closed + * 3 A open and B open + * 4 A closed and B closed and overlaps in more than one spot + * 5 A closed and B open and overlaps in more than one spot + * 6 A open and B closed and overlaps in more than one spot + * 7 A open and B open and overlaps in more than one spot + * As pieces are played, it can make frames not overlap if there are no + * common open spaces shared between the two frames. + */ +init_overlap() +{ + register struct spotstr *sp1, *sp2; + register struct combostr *cbp; + register int i, f, r, n, d1, d2; + int mask, bmask, vertex, s; + u_char *str; + short *ip; + + memset(overlap, 0, sizeof(overlap)); + memset(intersect, 0, sizeof(intersect)); + str = &overlap[FAREA * FAREA]; + ip = &intersect[FAREA * FAREA]; + for (cbp = frames + FAREA; --cbp >= frames; ) { /* each frame */ + str -= FAREA; + ip -= FAREA; + sp1 = &board[vertex = cbp->c_vertex]; + d1 = dd[r = cbp->c_dir]; + /* + * s = 5 if closed, 6 if open. + * At this point black & white are the same. + */ + s = 5 + sp1->s_fval[BLACK][r].c.b; + /* for each spot in frame A */ + for (i = 0; i < s; i++, sp1 += d1, vertex += d1) { + /* the sixth spot in frame A only overlaps if it is open */ + mask = (i == 5) ? 0xC : 0xF; + /* for each direction */ + for (r = 4; --r >= 0; ) { + bmask = BFLAG << r; + sp2 = sp1; + d2 = dd[r]; + /* for each frame that intersects at spot sp1 */ + for (f = 0; f < 6; f++, sp2 -= d2) { + if (sp2->s_occ == BORDER) + break; + if (sp2->s_flg & bmask) + continue; + n = sp2->s_frame[r] - frames; + ip[n] = vertex; + str[n] |= (f == 5) ? mask & 0xA : mask; + if (r == cbp->c_dir) { + /* compute the multiple spot overlap values */ + switch (i) { + case 0: /* sp1 is the first spot in A */ + if (f == 4) + str[n] |= 0xA0; + else if (f != 5) + str[n] |= 0xF0; + break; + case 1: /* sp1 is the second spot in A */ + if (f == 5) + str[n] |= 0xA0; + else + str[n] |= 0xF0; + break; + case 4: /* sp1 is the penultimate spot in A */ + if (f == 0) + str[n] |= 0xC0; + else + str[n] |= 0xF0; + break; + case 5: /* sp1 is the last spot in A */ + if (f == 1) + str[n] |= 0xC0; + else if (f != 0) + str[n] |= 0xF0; + break; + default: + str[n] |= 0xF0; + } + } + } + } + } + } +} diff --git a/games/gomoku/bdisp.c b/games/gomoku/bdisp.c new file mode 100644 index 00000000000..46a740dad5d --- /dev/null +++ b/games/gomoku/bdisp.c @@ -0,0 +1,276 @@ +/* $OpenBSD: bdisp.c,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)bdisp.c 8.2 (Berkeley) 5/3/95"; +#endif /* not lint */ + +#include "gomoku.h" +#include +#include + +#define SCRNH 24 /* assume 24 lines for the moment */ +#define SCRNW 80 /* assume 80 chars for the moment */ + +static int lastline; +static char pcolor[] = "*O.?"; + +/* + * Initialize screen display. + */ +cursinit() +{ + + initscr(); + noecho(); + cbreak(); + leaveok(stdscr, TRUE); +} + +/* + * Restore screen display. + */ +cursfini() +{ + + leaveok(stdscr, FALSE); + move(23, 0); + clrtoeol(); + refresh(); + endwin(); +} + +/* + * Initialize board display. + */ +bdisp_init() +{ + register int i, j; + + /* top border */ + for (i = 1; i < BSZ1; i++) { + move(0, 2 * i + 1); + addch(letters[i]); + } + /* left and right edges */ + for (j = BSZ1; --j > 0; ) { + move(20 - j, 0); + printw("%2d ", j); + move(20 - j, 2 * BSZ1 + 1); + printw("%d ", j); + } + /* bottom border */ + for (i = 1; i < BSZ1; i++) { + move(20, 2 * i + 1); + addch(letters[i]); + } + bdwho(0); + move(0, 47); + addstr("# black white"); + lastline = 0; + bdisp(); +} + +/* + * Update who is playing whom. + */ +bdwho(update) + int update; +{ + int i; + extern char *plyr[]; + + move(21, 0); + clrtoeol(); + i = 6 - strlen(plyr[BLACK]) / 2; + move(21, i > 0 ? i : 0); + printw("BLACK/%s", plyr[BLACK]); + i = 30 - strlen(plyr[WHITE]) / 2; + move(21, i); + printw("WHITE/%s", plyr[WHITE]); + move(21, 19); + addstr(" vs. "); + if (update) + refresh(); +} + +/* + * Update the board display after a move. + */ +bdisp() +{ + register int i, j, c; + register struct spotstr *sp; + + for (j = BSZ1; --j > 0; ) { + for (i = 1; i < BSZ1; i++) { + move(BSZ1 - j, 2 * i + 1); + sp = &board[i + j * BSZ1]; + if (debug > 1 && sp->s_occ == EMPTY) { + if (sp->s_flg & IFLAGALL) + c = '+'; + else if (sp->s_flg & CFLAGALL) + c = '-'; + else + c = '.'; + } else + c = pcolor[sp->s_occ]; + addch(c); + } + } + refresh(); +} + +#ifdef DEBUG +/* + * Dump board display to a file. + */ +bdump(fp) + FILE *fp; +{ + register int i, j, c; + register struct spotstr *sp; + + /* top border */ + fprintf(fp, " A B C D E F G H J K L M N O P Q R S T\n"); + + for (j = BSZ1; --j > 0; ) { + /* left edge */ + fprintf(fp, "%2d ", j); + for (i = 1; i < BSZ1; i++) { + sp = &board[i + j * BSZ1]; + if (debug > 1 && sp->s_occ == EMPTY) { + if (sp->s_flg & IFLAGALL) + c = '+'; + else if (sp->s_flg & CFLAGALL) + c = '-'; + else + c = '.'; + } else + c = pcolor[sp->s_occ]; + putc(c, fp); + putc(' ', fp); + } + /* right edge */ + fprintf(fp, "%d\n", j); + } + + /* bottom border */ + fprintf(fp, " A B C D E F G H J K L M N O P Q R S T\n"); +} +#endif /* DEBUG */ + +/* + * Display a transcript entry + */ +dislog(str) + char *str; +{ + + if (++lastline >= SCRNH - 1) { + /* move 'em up */ + lastline = 1; + } + if (strlen(str) >= SCRNW - 46) + str[SCRNW - 46 - 1] = '\0'; + move(lastline, 46); + addstr(str); + clrtoeol(); + move(lastline + 1, 46); + clrtoeol(); +} + +/* + * Display a question. + */ +ask(str) + char *str; +{ + int len = strlen(str); + + move(23, 0); + addstr(str); + clrtoeol(); + move(23, len); + refresh(); +} + +getline(buf, size) + char *buf; + int size; +{ + register char *cp, *end; + register int c; + extern int interactive; + + cp = buf; + end = buf + size - 1; /* save room for the '\0' */ + while (cp < end && (c = getchar()) != EOF && c != '\n' && c != '\r') { + *cp++ = c; + if (interactive) { + switch (c) { + case 0x0c: /* ^L */ + wrefresh(curscr); + cp--; + continue; + case 0x15: /* ^U */ + case 0x18: /* ^X */ + while (cp > buf) { + cp--; + addch('\b'); + } + clrtoeol(); + break; + case '\b': + case 0x7f: /* DEL */ + if (cp == buf + 1) { + cp--; + continue; + } + cp -= 2; + addch('\b'); + c = ' '; + /* FALLTHROUGH */ + default: + addch(c); + } + refresh(); + } + } + *cp = '\0'; + return(c != EOF); +} diff --git a/games/gomoku/gomoku.6 b/games/gomoku/gomoku.6 new file mode 100644 index 00000000000..70acbe66b4d --- /dev/null +++ b/games/gomoku/gomoku.6 @@ -0,0 +1,94 @@ +.\" $OpenBSD: gomoku.6,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ +.\" +.\" Copyright (c) 1994 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Ralph Campbell. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)gomoku.6 8.2 (Berkeley) 8/4/94 +.\" +.Dd August 4, 1994 +.Dt GOMOKU 6 +.Os +.Sh NAME +.Nm gomoku +.Nd game of 5 in a row +.Sh SYNOPSIS +.Nm gomoku +.Op Fl bcdu +.Op Fl D Ar debugfile +.Op Ar inputfile +.Sh DESCRIPTION +.Nm Gomoku +is a two player game were the object is to get 5 in a row horizontally, +vertically or diagonally on a 19 by 19 grid. By convention, black always +moves first. +With no arguments, +.Nm gomoku +will display a playing board and prompt for moves from the user. +Valid moves are a letter for the column and a number for the row of an empty +board location. Entering ``quit" or ``resign" will end the game. +You can save the current state of the game by entering ``save" and +supplying a file name when prompted. +The optional file +.Ar inputfile +can be used to restore a saved game. +.Pp +The options are: +.Bl -tag -width Ds +.It Fl b +This option sets background mode. Input moves are read from standard input, +the computer picks a move, and prints it to standard output. The first +input line should be either ``black" or ``white" to specify whether +.Nm gomoku +has the first move or not respectively. This +option was intended for game tournaments where a referee program handles +the board display and pits one program against another. +.It Fl c +Computer verses computer. +.Nm Gomoku +will play a game against itself. This is mostly used for testing. +.It Fl d +Print debugging information. Repeating this option more than +once yields more detailed information. +.It Fl D Ar debugfile +Print the debug information to +.Ar debugfile +instead of to the standard output. +.It Fl u +User verses user. This is mostly used for testing. +.Sh AUTHOR +Ralph Campbell +.Sh ACKNOWLEDGEMENTS +The board display routines were based on the +.Nm goref +program written by Peter Langston. diff --git a/games/gomoku/gomoku.h b/games/gomoku/gomoku.h new file mode 100644 index 00000000000..d35abe79cc4 --- /dev/null +++ b/games/gomoku/gomoku.h @@ -0,0 +1,267 @@ +/* $OpenBSD: gomoku.h,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)gomoku.h 8.2 (Berkeley) 5/3/95 + */ + +#include + +/* board dimensions */ +#define BSZ 19 +#define BSZ1 (BSZ+1) +#define BSZ2 (BSZ+2) +#define BAREA (BSZ2*BSZ1+1) + +/* frame dimentions (based on 5 in a row) */ +#define FSZ1 BSZ +#define FSZ2 (BSZ-4) +#define FAREA (FSZ1*FSZ2 + FSZ2*FSZ2 + FSZ1*FSZ2 + FSZ2*FSZ2) + +#define MUP (BSZ1) +#define MDOWN (-BSZ1) +#define MLEFT (-1) +#define MRIGHT (1) + +/* values for s_occ */ +#define BLACK 0 +#define WHITE 1 +#define EMPTY 2 +#define BORDER 3 + +/* return values for makemove() */ +#define MOVEOK 0 +#define RESIGN 1 +#define ILLEGAL 2 +#define WIN 3 +#define TIE 4 +#define SAVE 5 + +#define A 1 +#define B 2 +#define C 3 +#define D 4 +#define E 5 +#define F 6 +#define G 7 +#define H 8 +#define J 9 +#define K 10 +#define L 11 +#define M 12 +#define N 13 +#define O 14 +#define P 15 +#define Q 16 +#define R 17 +#define S 18 +#define T 19 + +#define PT(x,y) ((x) + BSZ1 * (y)) + +/* + * A 'frame' is a group of five or six contiguous board locations. + * An open ended frame is one with spaces on both ends; otherwise, its closed. + * A 'combo' is a group of intersecting frames and consists of two numbers: + * 'A' is the number of moves to make the combo non-blockable. + * 'B' is the minimum number of moves needed to win once it can't be blocked. + * A 'force' is a combo that is one move away from being non-blockable + * + * Single frame combo values: + * board values + * 5,0 . . . . . O + * 4,1 . . . . . . + * 4,0 . . . . X O + * 3,1 . . . . X . + * 3,0 . . . X X O + * 2,1 . . . X X . + * 2,0 . . X X X O + * 1,1 . . X X X . + * 1,0 . X X X X O + * 0,1 . X X X X . + * 0,0 X X X X X O + * + * The rule for combining two combos ( ) + * with V valid intersection points, is: + * A' = A1 + A2 - 2 - V + * B' = MIN(A1 + B1 - 1, A2 + B2 - 1) + * Each time a frame is added to the combo, the number of moves to complete + * the force is the number of moves needed to 'fill' the frame plus one at + * the intersection point. The number of moves to win is the number of moves + * to complete the best frame minus the last move to complete the force. + * Note that it doesn't make sense to combine a <1,x> with anything since + * it is already a force. Also, the frames have to be independent so a + * single move doesn't affect more than one frame making up the combo. + * + * Rules for comparing which of two combos ( ) is better: + * Both the same color: + * = (A1 < A2 || A1 == A2 && B1 <= B2) ? : + * We want to complete the force first, then the combo with the + * fewest moves to win. + * Different colors, is the combo for the player with the next move: + * = A2 <= 1 && (A1 > 1 || A2 + B2 < A1 + B1) ? : + * We want to block only if we have to (i.e., if they are one move away + * from completing a force and we don't have a force that we can + * complete which takes fewer or the same number of moves to win). + */ + +#define MAXA 6 +#define MAXB 2 +#define MAXCOMBO 0x600 + +union comboval { + struct { +#if BYTE_ORDER == BIG_ENDIAN + u_char a; /* # moves to complete force */ + u_char b; /* # moves to win */ +#endif +#if BYTE_ORDER == LITTLE_ENDIAN + u_char b; /* # moves to win */ + u_char a; /* # moves to complete force */ +#endif + } c; + u_short s; +}; + +/* + * This structure is used to record information about single frames (F) and + * combinations of two more frames (C). + * For combinations of two or more frames, there is an additional + * array of pointers to the frames of the combination which is sorted + * by the index into the frames[] array. This is used to prevent duplication + * since frame A combined with B is the same as B with A. + * struct combostr *c_sort[size c_nframes]; + * The leaves of the tree (frames) are numbered 0 (bottom, leftmost) + * to c_nframes - 1 (top, right). This is stored in c_frameindex and + * c_dir if C_LOOP is set. + */ +struct combostr { + struct combostr *c_next; /* list of combos at the same level */ + struct combostr *c_prev; /* list of combos at the same level */ + struct combostr *c_link[2]; /* C:previous level or F:NULL */ + union comboval c_linkv[2]; /* C:combo value for link[0,1] */ + union comboval c_combo; /* C:combo value for this level */ + u_short c_vertex; /* C:intersection or F:frame head */ + u_char c_nframes; /* number of frames in the combo */ + u_char c_dir; /* C:loop frame or F:frame direction */ + u_char c_flg; /* C:combo flags */ + u_char c_frameindex; /* C:intersection frame index */ + u_char c_framecnt[2]; /* number of frames left to attach */ + u_char c_emask[2]; /* C:bit mask of completion spots for + * link[0] and link[1] */ + u_char c_voff[2]; /* C:vertex offset within frame */ +}; + +/* flag values for c_flg */ +#define C_OPEN_0 0x01 /* link[0] is an open ended frame */ +#define C_OPEN_1 0x02 /* link[1] is an open ended frame */ +#define C_LOOP 0x04 /* link[1] intersects previous frame */ +#define C_MARK 0x08 /* indicates combo processed */ + +/* + * This structure is used for recording the completion points of + * multi frame combos. + */ +struct elist { + struct elist *e_next; /* list of completion points */ + struct combostr *e_combo; /* the whole combo */ + u_char e_off; /* offset in frame of this empty spot */ + u_char e_frameindex; /* intersection frame index */ + u_char e_framecnt; /* number of frames left to attach */ + u_char e_emask; /* real value of the frame's emask */ + union comboval e_fval; /* frame combo value */ +}; + +/* + * One spot structure for each location on the board. + * A frame consists of the combination for the current spot plus the five spots + * 0: right, 1: right & down, 2: down, 3: down & left. + */ +struct spotstr { + short s_occ; /* color of occupant */ + short s_wval; /* weighted value */ + int s_flg; /* flags for graph walks */ + struct combostr *s_frame[4]; /* level 1 combo for frame[dir] */ + union comboval s_fval[2][4]; /* combo value for [color][frame] */ + union comboval s_combo[2]; /* minimum combo value for BLK & WHT */ + u_char s_level[2]; /* number of frames in the min combo */ + u_char s_nforce[2]; /* number of <1,x> combos */ + struct elist *s_empty; /* level n combo completion spots */ + struct elist *s_nempty; /* level n+1 combo completion spots */ + int dummy[2]; /* XXX */ +}; + +/* flag values for s_flg */ +#define CFLAG 0x000001 /* frame is part of a combo */ +#define CFLAGALL 0x00000F /* all frame directions marked */ +#define IFLAG 0x000010 /* legal intersection point */ +#define IFLAGALL 0x0000F0 /* any intersection points? */ +#define FFLAG 0x000100 /* frame is part of a <1,x> combo */ +#define FFLAGALL 0x000F00 /* all force frames */ +#define MFLAG 0x001000 /* frame has already been seen */ +#define MFLAGALL 0x00F000 /* all frames seen */ +#define BFLAG 0x010000 /* frame intersects border or dead */ +#define BFLAGALL 0x0F0000 /* all frames dead */ + +/* + * This structure is used to store overlap information between frames. + */ +struct ovlp_info { + int o_intersect; /* intersection spot */ + struct combostr *o_fcombo; /* the connecting combo */ + u_char o_link; /* which link to update (0 or 1) */ + u_char o_off; /* offset in frame of intersection */ + u_char o_frameindex; /* intersection frame index */ +}; + +extern char *letters; +extern char fmtbuf[]; +extern char pdir[]; + +extern int dd[4]; +extern struct spotstr board[BAREA]; /* info for board */ +extern struct combostr frames[FAREA]; /* storage for single frames */ +extern struct combostr *sortframes[2]; /* sorted, non-empty frames */ +extern u_char overlap[FAREA * FAREA]; /* frame [a][b] overlap */ +extern short intersect[FAREA * FAREA]; /* frame [a][b] intersection */ +extern int movelog[BSZ * BSZ]; /* history of moves */ +extern int movenum; +extern int debug; + +extern char *copy(); +extern char *stoc(); +extern char *tail(); + +#define ASSERT(x) diff --git a/games/gomoku/main.c b/games/gomoku/main.c new file mode 100644 index 00000000000..0a4bbfd58fd --- /dev/null +++ b/games/gomoku/main.c @@ -0,0 +1,533 @@ +/* $OpenBSD: main.c,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char copyright[] = +"@(#) Copyright (c) 1994\n\ + The Regents of the University of California. All rights reserved.\n"; +#endif /* not lint */ + +#ifndef lint +static char sccsid[] = "@(#)main.c 8.4 (Berkeley) 5/4/95"; +#endif /* not lint */ + +#include +#include +#include +#include +#include +#include +#include + +#include "gomoku.h" + +#define USER 0 /* get input from standard input */ +#define PROGRAM 1 /* get input from program */ +#define INPUTF 2 /* get input from a file */ + +int interactive = 1; /* true if interactive */ +int debug; /* true if debugging */ +int test; /* both moves come from 1: input, 2: computer */ +char *prog; /* name of program */ +FILE *debugfp; /* file for debug output */ +FILE *inputfp; /* file for debug input */ + +char pdir[4] = "-\\|/"; +char fmtbuf[128]; + +struct spotstr board[BAREA]; /* info for board */ +struct combostr frames[FAREA]; /* storage for all frames */ +struct combostr *sortframes[2]; /* sorted list of non-empty frames */ +u_char overlap[FAREA * FAREA]; /* true if frame [a][b] overlap */ +short intersect[FAREA * FAREA]; /* frame [a][b] intersection */ +int movelog[BSZ * BSZ]; /* log of all the moves */ +int movenum; /* current move number */ +char *plyr[2]; /* who's who */ + +extern void quit(); +#ifdef DEBUG +extern void whatsup(); +#endif + +main(argc, argv) + int argc; + char **argv; +{ + char buf[128]; + int color, curmove, i, ch; + int input[2]; + static char *fmt[2] = { + "%3d %-6s", + "%3d %-6s" + }; + + prog = strrchr(argv[0], '/'); + if (prog) + prog++; + else + prog = argv[0]; + + while ((ch = getopt(argc, argv, "bcdD:u")) != EOF) { + switch (ch) { + case 'b': /* background */ + interactive = 0; + break; + case 'd': /* debugging */ + debug++; + break; + case 'D': /* log debug output to file */ + if ((debugfp = fopen(optarg, "w")) == NULL) + err(1, "%s", optarg); + break; + case 'u': /* testing: user verses user */ + test = 1; + break; + case 'c': /* testing: computer verses computer */ + test = 2; + break; + } + } + argc -= optind; + argv += optind; + if (argc) { + if ((inputfp = fopen(*argv, "r")) == NULL) + err(1, "%s", *argv); + } + + if (!debug) +#ifdef SVR4 + srand(time(0)); +#else + srandom(time(0)); +#endif + if (interactive) + cursinit(); /* initialize curses */ +again: + bdinit(board); /* initialize board contents */ + + if (interactive) { + plyr[BLACK] = plyr[WHITE] = "???"; + bdisp_init(); /* initialize display of board */ +#ifdef DEBUG + signal(SIGINT, whatsup); +#else + signal(SIGINT, quit); +#endif + + if (inputfp == NULL && test == 0) { + for (;;) { + ask("black or white? "); + getline(buf, sizeof(buf)); + if (buf[0] == 'b' || buf[0] == 'B') { + color = BLACK; + break; + } + if (buf[0] == 'w' || buf[0] == 'W') { + color = WHITE; + break; + } + move(22, 0); + printw("Black moves first. Please enter `black' or `white'\n"); + } + move(22, 0); + clrtoeol(); + } + } else { + setbuf(stdout, 0); + getline(buf, sizeof(buf)); + if (strcmp(buf, "black") == 0) + color = BLACK; + else if (strcmp(buf, "white") == 0) + color = WHITE; + else { + sprintf(fmtbuf, + "Huh? Expected `black' or `white', got `%s'\n", + buf); + panic(fmtbuf); + } + } + + if (inputfp) { + input[BLACK] = INPUTF; + input[WHITE] = INPUTF; + } else { + switch (test) { + case 0: /* user verses program */ + input[color] = USER; + input[!color] = PROGRAM; + break; + + case 1: /* user verses user */ + input[BLACK] = USER; + input[WHITE] = USER; + break; + + case 2: /* program verses program */ + input[BLACK] = PROGRAM; + input[WHITE] = PROGRAM; + break; + } + } + if (interactive) { + plyr[BLACK] = input[BLACK] == USER ? "you" : prog; + plyr[WHITE] = input[WHITE] == USER ? "you" : prog; + bdwho(1); + } + + for (color = BLACK; ; color = !color) { + top: + switch (input[color]) { + case INPUTF: /* input comes from a file */ + curmove = readinput(inputfp); + if (curmove != ILLEGAL) + break; + switch (test) { + case 0: /* user verses program */ + input[color] = USER; + input[!color] = PROGRAM; + break; + + case 1: /* user verses user */ + input[BLACK] = USER; + input[WHITE] = USER; + break; + + case 2: /* program verses program */ + input[BLACK] = PROGRAM; + input[WHITE] = PROGRAM; + break; + } + plyr[BLACK] = input[BLACK] == USER ? "you" : prog; + plyr[WHITE] = input[WHITE] == USER ? "you" : prog; + bdwho(1); + goto top; + + case USER: /* input comes from standard input */ + getinput: + if (interactive) + ask("move? "); + if (!getline(buf, sizeof(buf))) { + curmove = RESIGN; + break; + } + if (buf[0] == '\0') + goto getinput; + curmove = ctos(buf); + if (interactive) { + if (curmove == SAVE) { + FILE *fp; + + ask("save file name? "); + (void)getline(buf, sizeof(buf)); + if ((fp = fopen(buf, "w")) == NULL) { + log("cannot create save file"); + goto getinput; + } + for (i = 0; i < movenum - 1; i++) + fprintf(fp, "%s\n", + stoc(movelog[i])); + fclose(fp); + goto getinput; + } + if (curmove != RESIGN && + board[curmove].s_occ != EMPTY) { + log("Illegal move"); + goto getinput; + } + } + break; + + case PROGRAM: /* input comes from the program */ + curmove = pickmove(color); + break; + } + if (interactive) { + sprintf(fmtbuf, fmt[color], movenum, stoc(curmove)); + log(fmtbuf); + } + if ((i = makemove(color, curmove)) != MOVEOK) + break; + if (interactive) + bdisp(); + } + if (interactive) { + move(22, 0); + switch (i) { + case WIN: + if (input[color] == PROGRAM) + addstr("Ha ha, I won"); + else + addstr("Rats! you won"); + break; + case TIE: + addstr("Wow! its a tie"); + break; + case ILLEGAL: + addstr("Illegal move"); + break; + } + clrtoeol(); + bdisp(); + if (i != RESIGN) { + replay: + ask("replay? "); + if (getline(buf, sizeof(buf)) && + buf[0] == 'y' || buf[0] == 'Y') + goto again; + if (strcmp(buf, "save") == 0) { + FILE *fp; + + ask("save file name? "); + (void)getline(buf, sizeof(buf)); + if ((fp = fopen(buf, "w")) == NULL) { + log("cannot create save file"); + goto replay; + } + for (i = 0; i < movenum - 1; i++) + fprintf(fp, "%s\n", + stoc(movelog[i])); + fclose(fp); + goto replay; + } + } + } + quit(); +} + +readinput(fp) + FILE *fp; +{ + char *cp; + int c; + + cp = fmtbuf; + while ((c = getc(fp)) != EOF && c != '\n') + *cp++ = c; + *cp = '\0'; + return (ctos(fmtbuf)); +} + +#ifdef DEBUG +/* + * Handle strange situations. + */ +void +whatsup(signum) + int signum; +{ + int i, pnum, n, s1, s2, d1, d2; + struct spotstr *sp; + FILE *fp; + char *str; + struct elist *ep; + struct combostr *cbp; + + if (!interactive) + quit(); +top: + ask("cmd? "); + if (!getline(fmtbuf, sizeof(fmtbuf))) + quit(); + switch (*fmtbuf) { + case '\0': + goto top; + case 'q': /* conservative quit */ + quit(); + case 'd': /* set debug level */ + debug = fmtbuf[1] - '0'; + sprintf(fmtbuf, "Debug set to %d", debug); + dlog(fmtbuf); + sleep(1); + case 'c': + break; + case 'b': /* back up a move */ + if (movenum > 1) { + movenum--; + board[movelog[movenum - 1]].s_occ = EMPTY; + bdisp(); + } + goto top; + case 's': /* suggest a move */ + i = fmtbuf[1] == 'b' ? BLACK : WHITE; + sprintf(fmtbuf, "suggest %c %s", i == BLACK ? 'B' : 'W', + stoc(pickmove(i))); + dlog(fmtbuf); + goto top; + case 'f': /* go forward a move */ + board[movelog[movenum - 1]].s_occ = movenum & 1 ? BLACK : WHITE; + movenum++; + bdisp(); + goto top; + case 'l': /* print move history */ + if (fmtbuf[1] == '\0') { + for (i = 0; i < movenum - 1; i++) + dlog(stoc(movelog[i])); + goto top; + } + if ((fp = fopen(fmtbuf + 1, "w")) == NULL) + goto top; + for (i = 0; i < movenum - 1; i++) { + fprintf(fp, "%s", stoc(movelog[i])); + if (++i < movenum - 1) + fprintf(fp, " %s\n", stoc(movelog[i])); + else + fputc('\n', fp); + } + bdump(fp); + fclose(fp); + goto top; + case 'o': + n = 0; + for (str = fmtbuf + 1; *str; str++) + if (*str == ',') { + for (d1 = 0; d1 < 4; d1++) + if (str[-1] == pdir[d1]) + break; + str[-1] = '\0'; + sp = &board[s1 = ctos(fmtbuf + 1)]; + n = (sp->s_frame[d1] - frames) * FAREA; + *str++ = '\0'; + break; + } + sp = &board[s2 = ctos(str)]; + while (*str) + str++; + for (d2 = 0; d2 < 4; d2++) + if (str[-1] == pdir[d2]) + break; + n += sp->s_frame[d2] - frames; + str = fmtbuf; + sprintf(str, "overlap %s%c,", stoc(s1), pdir[d1]); + str += strlen(str); + sprintf(str, "%s%c = %x", stoc(s2), pdir[d2], overlap[n]); + dlog(fmtbuf); + goto top; + case 'p': + sp = &board[i = ctos(fmtbuf + 1)]; + sprintf(fmtbuf, "V %s %x/%d %d %x/%d %d %d %x", stoc(i), + sp->s_combo[BLACK].s, sp->s_level[BLACK], + sp->s_nforce[BLACK], + sp->s_combo[WHITE].s, sp->s_level[WHITE], + sp->s_nforce[WHITE], sp->s_wval, sp->s_flg); + dlog(fmtbuf); + sprintf(fmtbuf, "FB %s %x %x %x %x", stoc(i), + sp->s_fval[BLACK][0].s, sp->s_fval[BLACK][1].s, + sp->s_fval[BLACK][2].s, sp->s_fval[BLACK][3].s); + dlog(fmtbuf); + sprintf(fmtbuf, "FW %s %x %x %x %x", stoc(i), + sp->s_fval[WHITE][0].s, sp->s_fval[WHITE][1].s, + sp->s_fval[WHITE][2].s, sp->s_fval[WHITE][3].s); + dlog(fmtbuf); + goto top; + case 'e': /* e {b|w} [0-9] spot */ + str = fmtbuf + 1; + if (*str >= '0' && *str <= '9') + n = *str++ - '0'; + else + n = 0; + sp = &board[i = ctos(str)]; + for (ep = sp->s_empty; ep; ep = ep->e_next) { + cbp = ep->e_combo; + if (n) { + if (cbp->c_nframes > n) + continue; + if (cbp->c_nframes != n) + break; + } + printcombo(cbp, fmtbuf); + dlog(fmtbuf); + } + goto top; + default: +syntax: + dlog("Options are:"); + dlog("q - quit"); + dlog("c - continue"); + dlog("d# - set debug level to #"); + dlog("p# - print values at #"); + goto top; + } +} +#endif /* DEBUG */ + +/* + * Display debug info. + */ +dlog(str) + char *str; +{ + + if (debugfp) + fprintf(debugfp, "%s\n", str); + if (interactive) + dislog(str); + else + fprintf(stderr, "%s\n", str); +} + +log(str) + char *str; +{ + + if (debugfp) + fprintf(debugfp, "%s\n", str); + if (interactive) + dislog(str); + else + printf("%s\n", str); +} + +void +quit() +{ + if (interactive) { + bdisp(); /* show final board */ + cursfini(); + } + exit(0); +} + +/* + * Die gracefully. + */ +panic(str) + char *str; +{ + fprintf(stderr, "%s: %s\n", prog, str); + fputs("resign\n", stdout); + quit(); +} diff --git a/games/gomoku/makemove.c b/games/gomoku/makemove.c new file mode 100644 index 00000000000..ebf0f9fed5e --- /dev/null +++ b/games/gomoku/makemove.c @@ -0,0 +1,302 @@ +/* $OpenBSD: makemove.c,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)makemove.c 8.2 (Berkeley) 5/3/95"; +#endif /* not lint */ + +#include "gomoku.h" + + /* direction deltas */ +int dd[4] = { + MRIGHT, MRIGHT+MDOWN, MDOWN, MDOWN+MLEFT +}; + +int weight[5] = { 0, 1, 7, 22, 100 }; + +/* + * Return values: + * MOVEOK everything is OK. + * RESIGN Player resigned. + * ILLEGAL Illegal move. + * WIN The the winning move was just played. + * TIE The game is a tie. + */ +makemove(us, mv) + int us, mv; +{ + register struct spotstr *sp, *fsp; + register union comboval *cp; + struct spotstr *osp; + struct combostr *cbp, *cbp1; + union comboval *cp1; + register int i, f, r, d, n; + int space, val, bmask; + + /* check for end of game */ + if (mv == RESIGN) + return(RESIGN); + + /* check for illegal move */ + sp = &board[mv]; + if (sp->s_occ != EMPTY) + return(ILLEGAL); + + /* make move */ + sp->s_occ = us; + movelog[movenum - 1] = mv; + if (++movenum == BSZ * BSZ) + return(TIE); + + /* compute new frame values */ + sp->s_wval = 0; + osp = sp; + for (r = 4; --r >= 0; ) { /* for each direction */ + d = dd[r]; + fsp = osp; + bmask = BFLAG << r; + for (f = 5; --f >= 0; fsp -= d) { /* for each frame */ + if (fsp->s_occ == BORDER) + goto nextr; + if (fsp->s_flg & bmask) + continue; + + /* remove this frame from the sorted list of frames */ + cbp = fsp->s_frame[r]; + if (cbp->c_next) { + if (sortframes[BLACK] == cbp) + sortframes[BLACK] = cbp->c_next; + if (sortframes[WHITE] == cbp) + sortframes[WHITE] = cbp->c_next; + cbp->c_next->c_prev = cbp->c_prev; + cbp->c_prev->c_next = cbp->c_next; + } + + /* compute old weight value for this frame */ + cp = &fsp->s_fval[BLACK][r]; + if (cp->s <= 0x500) + val = weight[5 - cp->c.a - cp->c.b]; + else + val = 0; + cp = &fsp->s_fval[WHITE][r]; + if (cp->s <= 0x500) + val += weight[5 - cp->c.a - cp->c.b]; + + /* compute new combo value for this frame */ + sp = fsp; + space = sp->s_occ == EMPTY; + n = 0; + for (i = 5; --i >= 0; sp += d) { /* for each spot */ + if (sp->s_occ == us) + n++; + else if (sp->s_occ == EMPTY) + sp->s_wval -= val; + else { + /* this frame is now blocked, adjust values */ + fsp->s_flg |= bmask; + fsp->s_fval[BLACK][r].s = MAXCOMBO; + fsp->s_fval[WHITE][r].s = MAXCOMBO; + while (--i >= 0) { + sp += d; + if (sp->s_occ == EMPTY) + sp->s_wval -= val; + } + goto nextf; + } + } + + /* check for game over */ + if (n == 5) + return(WIN); + + /* compute new value & combo number for this frame & color */ + fsp->s_fval[!us][r].s = MAXCOMBO; + cp = &fsp->s_fval[us][r]; + /* both ends open? */ + if (space && sp->s_occ == EMPTY) { + cp->c.a = 4 - n; + cp->c.b = 1; + } else { + cp->c.a = 5 - n; + cp->c.b = 0; + } + val = weight[n]; + sp = fsp; + for (i = 5; --i >= 0; sp += d) /* for each spot */ + if (sp->s_occ == EMPTY) + sp->s_wval += val; + + /* add this frame to the sorted list of frames by combo value */ + cbp1 = sortframes[us]; + if (!cbp1) + sortframes[us] = cbp->c_next = cbp->c_prev = cbp; + else { + cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; + if (cp->s <= cp1->s) { + /* insert at the head of the list */ + sortframes[us] = cbp; + } else { + do { + cbp1 = cbp1->c_next; + cp1 = &board[cbp1->c_vertex].s_fval[us][cbp1->c_dir]; + if (cp->s <= cp1->s) + break; + } while (cbp1 != sortframes[us]); + } + cbp->c_next = cbp1; + cbp->c_prev = cbp1->c_prev; + cbp1->c_prev->c_next = cbp; + cbp1->c_prev = cbp; + } + + nextf: + ; + } + + /* both ends open? */ + if (fsp->s_occ == EMPTY) { + cp = &fsp->s_fval[BLACK][r]; + if (cp->c.b) { + cp->c.a += 1; + cp->c.b = 0; + } + cp = &fsp->s_fval[WHITE][r]; + if (cp->c.b) { + cp->c.a += 1; + cp->c.b = 0; + } + } + + nextr: + ; + } + + update_overlap(osp); + + return(MOVEOK); +} + +/* + * fix up the overlap array due to updating spot osp. + */ +update_overlap(osp) + struct spotstr *osp; +{ + register struct spotstr *sp, *sp1, *sp2; + register int i, f, r, r1, d, d1, n; + int a, b, bmask, bmask1; + struct spotstr *esp; + char *str; + + for (r = 4; --r >= 0; ) { /* for each direction */ + d = dd[r]; + sp1 = osp; + bmask = BFLAG << r; + for (f = 0; f < 6; f++, sp1 -= d) { /* for each frame */ + if (sp1->s_occ == BORDER) + break; + if (sp1->s_flg & bmask) + continue; + /* + * Update all other frames that intersect the current one + * to indicate whether they still overlap or not. + * Since F1 overlap F2 == F2 overlap F1, we only need to + * do the rows 0 <= r1 <= r. The r1 == r case is special + * since the two frames can overlap at more than one point. + */ + str = &overlap[(a = sp1->s_frame[r] - frames) * FAREA]; + sp2 = sp1 - d; + for (i = f + 1; i < 6; i++, sp2 -= d) { + if (sp2->s_occ == BORDER) + break; + if (sp2->s_flg & bmask) + continue; + /* + * count the number of empty spots to see if there is + * still an overlap. + */ + n = 0; + sp = sp1; + for (b = i - f; b < 5; b++, sp += d) { + if (sp->s_occ == EMPTY) { + esp = sp; /* save the intersection point */ + n++; + } + } + b = sp2->s_frame[r] - frames; + if (n == 0) { + if (sp->s_occ == EMPTY) { + str[b] &= 0xA; + overlap[b * FAREA + a] &= 0xC; + intersect[a * FAREA + b] = n = sp - board; + intersect[b * FAREA + a] = n; + } else { + str[b] = 0; + overlap[b * FAREA + a] = 0; + } + } else if (n == 1) { + if (sp->s_occ == EMPTY) { + str[b] &= 0xAF; + overlap[b * FAREA + a] &= 0xCF; + } else { + str[b] &= 0xF; + overlap[b * FAREA + a] &= 0xF; + } + intersect[a * FAREA + b] = n = esp - board; + intersect[b * FAREA + a] = n; + } + /* else no change, still multiple overlap */ + } + + /* the other directions can only intersect at spot osp */ + for (r1 = r; --r1 >= 0; ) { + d1 = dd[r1]; + bmask1 = BFLAG << r1; + sp = osp; + for (i = 6; --i >= 0; sp -= d1) { /* for each spot */ + if (sp->s_occ == BORDER) + break; + if (sp->s_flg & bmask1) + continue; + b = sp->s_frame[r1] - frames; + str[b] = 0; + overlap[b * FAREA + a] = 0; + } + } + } + } +} diff --git a/games/gomoku/pickmove.c b/games/gomoku/pickmove.c new file mode 100644 index 00000000000..cefcdb42df8 --- /dev/null +++ b/games/gomoku/pickmove.c @@ -0,0 +1,1480 @@ +/* $OpenBSD: pickmove.c,v 1.1.1.1 1996/12/16 06:56:08 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)pickmove.c 8.2 (Berkeley) 5/3/95"; +#endif /* not lint */ + +#include +#include +#include + +#include "gomoku.h" + +#define BITS_PER_INT (sizeof(int) * CHAR_BIT) +#define MAPSZ (BAREA / BITS_PER_INT) + +#define BIT_SET(a, b) ((a)[(b)/BITS_PER_INT] |= (1 << ((b) % BITS_PER_INT))) +#define BIT_CLR(a, b) ((a)[(b)/BITS_PER_INT] &= ~(1 << ((b) % BITS_PER_INT))) +#define BIT_TEST(a, b) ((a)[(b)/BITS_PER_INT] & (1 << ((b) % BITS_PER_INT))) + +struct combostr *hashcombos[FAREA]; /* hash list for finding duplicates */ +struct combostr *sortcombos; /* combos at higher levels */ +int combolen; /* number of combos in sortcombos */ +int nextcolor; /* color of next move */ +int elistcnt; /* count of struct elist allocated */ +int combocnt; /* count of struct combostr allocated */ +int forcemap[MAPSZ]; /* map for blocking <1,x> combos */ +int tmpmap[MAPSZ]; /* map for blocking <1,x> combos */ +int nforce; /* count of opponent <1,x> combos */ + +pickmove(us) + int us; +{ + register struct spotstr *sp, *sp1, *sp2; + register union comboval *Ocp, *Tcp; + char *str; + int i, j, m; + + /* first move is easy */ + if (movenum == 1) + return (PT(K,10)); + + /* initialize all the board values */ + for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { + sp->s_combo[BLACK].s = MAXCOMBO + 1; + sp->s_combo[WHITE].s = MAXCOMBO + 1; + sp->s_level[BLACK] = 255; + sp->s_level[WHITE] = 255; + sp->s_nforce[BLACK] = 0; + sp->s_nforce[WHITE] = 0; + sp->s_flg &= ~(FFLAGALL | MFLAGALL); + } + nforce = 0; + memset(forcemap, 0, sizeof(forcemap)); + + /* compute new values */ + nextcolor = us; + scanframes(BLACK); + scanframes(WHITE); + + /* find the spot with the highest value */ + for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) { + if (sp->s_occ != EMPTY) + continue; + if (debug && (sp->s_combo[BLACK].c.a == 1 || + sp->s_combo[WHITE].c.a == 1)) { + sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board), + sp->s_combo[BLACK].s, sp->s_level[BLACK], + sp->s_nforce[BLACK], + sp->s_combo[WHITE].s, sp->s_level[WHITE], + sp->s_nforce[WHITE], + sp->s_wval); + dlog(fmtbuf); + } + /* pick the best black move */ + if (better(sp, sp1, BLACK)) + sp1 = sp; + /* pick the best white move */ + if (better(sp, sp2, WHITE)) + sp2 = sp; + } + + if (debug) { + sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d %d", + stoc(sp1 - board), + sp1->s_combo[BLACK].s, sp1->s_level[BLACK], + sp1->s_nforce[BLACK], + sp1->s_combo[WHITE].s, sp1->s_level[WHITE], + sp1->s_nforce[WHITE], sp1->s_wval); + dlog(fmtbuf); + sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d %d", + stoc(sp2 - board), + sp2->s_combo[WHITE].s, sp2->s_level[WHITE], + sp2->s_nforce[WHITE], + sp2->s_combo[BLACK].s, sp2->s_level[BLACK], + sp2->s_nforce[BLACK], sp2->s_wval); + dlog(fmtbuf); + /* + * Check for more than one force that can't + * all be blocked with one move. + */ + sp = (us == BLACK) ? sp2 : sp1; + m = sp - board; + if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m)) + dlog("*** Can't be blocked"); + } + if (us == BLACK) { + Ocp = &sp1->s_combo[BLACK]; + Tcp = &sp2->s_combo[WHITE]; + } else { + Tcp = &sp1->s_combo[BLACK]; + Ocp = &sp2->s_combo[WHITE]; + sp = sp1; + sp1 = sp2; + sp2 = sp; + } + /* + * Block their combo only if we have to (i.e., if they are one move + * away from completing a force and we don't have a force that + * we can complete which takes fewer moves to win). + */ + if (Tcp->c.a <= 1 && (Ocp->c.a > 1 || + Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b)) + return (sp2 - board); + return (sp1 - board); +} + +/* + * Return true if spot 'sp' is better than spot 'sp1' for color 'us'. + */ +better(sp, sp1, us) + struct spotstr *sp; + struct spotstr *sp1; + int us; +{ + int them, s, s1; + + if (sp->s_combo[us].s < sp1->s_combo[us].s) + return (1); + if (sp->s_combo[us].s != sp1->s_combo[us].s) + return (0); + if (sp->s_level[us] < sp1->s_level[us]) + return (1); + if (sp->s_level[us] != sp1->s_level[us]) + return (0); + if (sp->s_nforce[us] > sp1->s_nforce[us]) + return (1); + if (sp->s_nforce[us] != sp1->s_nforce[us]) + return (0); + + them = !us; + s = sp - board; + s1 = sp1 - board; + if (BIT_TEST(forcemap, s) && !BIT_TEST(forcemap, s1)) + return (1); + if (!BIT_TEST(forcemap, s) && BIT_TEST(forcemap, s1)) + return (0); + if (sp->s_combo[them].s < sp1->s_combo[them].s) + return (1); + if (sp->s_combo[them].s != sp1->s_combo[them].s) + return (0); + if (sp->s_level[them] < sp1->s_level[them]) + return (1); + if (sp->s_level[them] != sp1->s_level[them]) + return (0); + if (sp->s_nforce[them] > sp1->s_nforce[them]) + return (1); + if (sp->s_nforce[them] != sp1->s_nforce[them]) + return (0); + + if (sp->s_wval > sp1->s_wval) + return (1); + if (sp->s_wval != sp1->s_wval) + return (0); + +#ifdef SVR4 + return (rand() & 1); +#else + return (random() & 1); +#endif +} + +int curcolor; /* implicit parameter to makecombo() */ +int curlevel; /* implicit parameter to makecombo() */ + +/* + * Scan the sorted list of non-empty frames and + * update the minimum combo values for each empty spot. + * Also, try to combine frames to find more complex (chained) moves. + */ +scanframes(color) + int color; +{ + register struct combostr *cbp, *ecbp; + register struct spotstr *sp; + register union comboval *cp; + register struct elist *ep, *nep; + register int i, r, d, n; + union comboval cb; + + curcolor = color; + + /* check for empty list of frames */ + cbp = sortframes[color]; + if (cbp == (struct combostr *)0) + return; + + /* quick check for four in a row */ + sp = &board[cbp->c_vertex]; + cb.s = sp->s_fval[color][d = cbp->c_dir].s; + if (cb.s < 0x101) { + d = dd[d]; + for (i = 5 + cb.c.b; --i >= 0; sp += d) { + if (sp->s_occ != EMPTY) + continue; + sp->s_combo[color].s = cb.s; + sp->s_level[color] = 1; + } + return; + } + + /* + * Update the minimum combo value for each spot in the frame + * and try making all combinations of two frames intersecting at + * an empty spot. + */ + n = combolen; + ecbp = cbp; + do { + sp = &board[cbp->c_vertex]; + cp = &sp->s_fval[color][r = cbp->c_dir]; + d = dd[r]; + if (cp->c.b) { + /* + * Since this is the first spot of an open ended + * frame, we treat it as a closed frame. + */ + cb.c.a = cp->c.a + 1; + cb.c.b = 0; + if (cb.s < sp->s_combo[color].s) { + sp->s_combo[color].s = cb.s; + sp->s_level[color] = 1; + } + /* + * Try combining other frames that intersect + * at this spot. + */ + makecombo2(cbp, sp, 0, cb.s); + if (cp->s != 0x101) + cb.s = cp->s; + else if (color != nextcolor) + memset(tmpmap, 0, sizeof(tmpmap)); + sp += d; + i = 1; + } else { + cb.s = cp->s; + i = 0; + } + for (; i < 5; i++, sp += d) { /* for each spot */ + if (sp->s_occ != EMPTY) + continue; + if (cp->s < sp->s_combo[color].s) { + sp->s_combo[color].s = cp->s; + sp->s_level[color] = 1; + } + if (cp->s == 0x101) { + sp->s_nforce[color]++; + if (color != nextcolor) { + n = sp - board; + BIT_SET(tmpmap, n); + } + } + /* + * Try combining other frames that intersect + * at this spot. + */ + makecombo2(cbp, sp, i, cb.s); + } + if (cp->s == 0x101 && color != nextcolor) { + if (nforce == 0) + memcpy(forcemap, tmpmap, sizeof(tmpmap)); + else { + for (i = 0; i < MAPSZ; i++) + forcemap[i] &= tmpmap[i]; + } + } + /* mark frame as having been processed */ + board[cbp->c_vertex].s_flg |= MFLAG << r; + } while ((cbp = cbp->c_next) != ecbp); + + /* + * Try to make new 3rd level combos, 4th level, etc. + * Limit the search depth early in the game. + */ + d = 2; + while (d <= ((movenum + 1) >> 1) && combolen > n) { + if (debug) { + sprintf(fmtbuf, "%cL%d %d %d %d", "BW"[color], + d, combolen - n, combocnt, elistcnt); + dlog(fmtbuf); + refresh(); + } + n = combolen; + addframes(d); + d++; + } + + /* scan for combos at empty spots */ + for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { + for (ep = sp->s_empty; ep; ep = nep) { + cbp = ep->e_combo; + if (cbp->c_combo.s <= sp->s_combo[color].s) { + if (cbp->c_combo.s != sp->s_combo[color].s) { + sp->s_combo[color].s = cbp->c_combo.s; + sp->s_level[color] = cbp->c_nframes; + } else if (cbp->c_nframes < sp->s_level[color]) + sp->s_level[color] = cbp->c_nframes; + } + nep = ep->e_next; + free(ep); + elistcnt--; + } + sp->s_empty = (struct elist *)0; + for (ep = sp->s_nempty; ep; ep = nep) { + cbp = ep->e_combo; + if (cbp->c_combo.s <= sp->s_combo[color].s) { + if (cbp->c_combo.s != sp->s_combo[color].s) { + sp->s_combo[color].s = cbp->c_combo.s; + sp->s_level[color] = cbp->c_nframes; + } else if (cbp->c_nframes < sp->s_level[color]) + sp->s_level[color] = cbp->c_nframes; + } + nep = ep->e_next; + free(ep); + elistcnt--; + } + sp->s_nempty = (struct elist *)0; + } + + /* remove old combos */ + if ((cbp = sortcombos) != (struct combostr *)0) { + struct combostr *ncbp; + + /* scan the list */ + ecbp = cbp; + do { + ncbp = cbp->c_next; + free(cbp); + combocnt--; + } while ((cbp = ncbp) != ecbp); + sortcombos = (struct combostr *)0; + } + combolen = 0; + +#ifdef DEBUG + if (combocnt) { + sprintf(fmtbuf, "scanframes: %c combocnt %d", "BW"[color], + combocnt); + dlog(fmtbuf); + whatsup(0); + } + if (elistcnt) { + sprintf(fmtbuf, "scanframes: %c elistcnt %d", "BW"[color], + elistcnt); + dlog(fmtbuf); + whatsup(0); + } +#endif +} + +/* + * Compute all level 2 combos of frames intersecting spot 'osp' + * within the frame 'ocbp' and combo value 's'. + */ +makecombo2(ocbp, osp, off, s) + struct combostr *ocbp; + struct spotstr *osp; + int off; + int s; +{ + register struct spotstr *sp, *fsp; + register struct combostr *ncbp; + register int f, r, d, c; + int baseB, fcnt, emask, bmask, n; + union comboval ocb, fcb; + struct combostr **scbpp, *fcbp; + + /* try to combine a new frame with those found so far */ + ocb.s = s; + baseB = ocb.c.a + ocb.c.b - 1; + fcnt = ocb.c.a - 2; + emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0; + for (r = 4; --r >= 0; ) { /* for each direction */ + /* don't include frames that overlap in the same direction */ + if (r == ocbp->c_dir) + continue; + d = dd[r]; + /* + * Frame A combined with B is the same value as B combined with A + * so skip frames that have already been processed (MFLAG). + * Also skip blocked frames (BFLAG) and frames that are <1,x> + * since combining another frame with it isn't valid. + */ + bmask = (BFLAG | FFLAG | MFLAG) << r; + fsp = osp; + for (f = 0; f < 5; f++, fsp -= d) { /* for each frame */ + if (fsp->s_occ == BORDER) + break; + if (fsp->s_flg & bmask) + continue; + + /* don't include frames of the wrong color */ + fcb.s = fsp->s_fval[curcolor][r].s; + if (fcb.c.a >= MAXA) + continue; + + /* + * Get the combo value for this frame. + * If this is the end point of the frame, + * use the closed ended value for the frame. + */ + if (f == 0 && fcb.c.b || fcb.s == 0x101) { + fcb.c.a++; + fcb.c.b = 0; + } + + /* compute combo value */ + c = fcb.c.a + ocb.c.a - 3; + if (c > 4) + continue; + n = fcb.c.a + fcb.c.b - 1; + if (baseB < n) + n = baseB; + + /* make a new combo! */ + ncbp = (struct combostr *)malloc(sizeof(struct combostr) + + 2 * sizeof(struct combostr *)); + scbpp = (struct combostr **)(ncbp + 1); + fcbp = fsp->s_frame[r]; + if (ocbp < fcbp) { + scbpp[0] = ocbp; + scbpp[1] = fcbp; + } else { + scbpp[0] = fcbp; + scbpp[1] = ocbp; + } + ncbp->c_combo.c.a = c; + ncbp->c_combo.c.b = n; + ncbp->c_link[0] = ocbp; + ncbp->c_link[1] = fcbp; + ncbp->c_linkv[0].s = ocb.s; + ncbp->c_linkv[1].s = fcb.s; + ncbp->c_voff[0] = off; + ncbp->c_voff[1] = f; + ncbp->c_vertex = osp - board; + ncbp->c_nframes = 2; + ncbp->c_dir = 0; + ncbp->c_frameindex = 0; + ncbp->c_flg = (ocb.c.b) ? C_OPEN_0 : 0; + if (fcb.c.b) + ncbp->c_flg |= C_OPEN_1; + ncbp->c_framecnt[0] = fcnt; + ncbp->c_emask[0] = emask; + ncbp->c_framecnt[1] = fcb.c.a - 2; + ncbp->c_emask[1] = ncbp->c_framecnt[1] ? + ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0; + combocnt++; + + if (c == 1 && debug > 1 || debug > 3) { + sprintf(fmtbuf, "%c c %d %d m %x %x o %d %d", + "bw"[curcolor], + ncbp->c_framecnt[0], ncbp->c_framecnt[1], + ncbp->c_emask[0], ncbp->c_emask[1], + ncbp->c_voff[0], ncbp->c_voff[1]); + dlog(fmtbuf); + printcombo(ncbp, fmtbuf); + dlog(fmtbuf); + } + if (c > 1) { + /* record the empty spots that will complete this combo */ + makeempty(ncbp); + + /* add the new combo to the end of the list */ + appendcombo(ncbp, curcolor); + } else { + updatecombo(ncbp, curcolor); + free(ncbp); + combocnt--; + } +#ifdef DEBUG + if (c == 1 && debug > 1 || debug > 5) { + markcombo(ncbp); + bdisp(); + whatsup(0); + clearcombo(ncbp, 0); + } +#endif /* DEBUG */ + } + } +} + +/* + * Scan the sorted list of frames and try to add a frame to + * combinations of 'level' number of frames. + */ +addframes(level) + int level; +{ + register struct combostr *cbp, *ecbp; + register struct spotstr *sp, *fsp; + register struct elist *ep, *nep; + register int i, r, d; + struct combostr **cbpp, *pcbp; + union comboval fcb, cb; + + curlevel = level; + + /* scan for combos at empty spots */ + i = curcolor; + for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) { + for (ep = sp->s_empty; ep; ep = nep) { + cbp = ep->e_combo; + if (cbp->c_combo.s <= sp->s_combo[i].s) { + if (cbp->c_combo.s != sp->s_combo[i].s) { + sp->s_combo[i].s = cbp->c_combo.s; + sp->s_level[i] = cbp->c_nframes; + } else if (cbp->c_nframes < sp->s_level[i]) + sp->s_level[i] = cbp->c_nframes; + } + nep = ep->e_next; + free(ep); + elistcnt--; + } + sp->s_empty = sp->s_nempty; + sp->s_nempty = (struct elist *)0; + } + + /* try to add frames to the uncompleted combos at level curlevel */ + cbp = ecbp = sortframes[curcolor]; + do { + fsp = &board[cbp->c_vertex]; + r = cbp->c_dir; + /* skip frames that are part of a <1,x> combo */ + if (fsp->s_flg & (FFLAG << r)) + continue; + + /* + * Don't include <1,x> combo frames, + * treat it as a closed three in a row instead. + */ + fcb.s = fsp->s_fval[curcolor][r].s; + if (fcb.s == 0x101) + fcb.s = 0x200; + + /* + * If this is an open ended frame, use + * the combo value with the end closed. + */ + if (fsp->s_occ == EMPTY) { + if (fcb.c.b) { + cb.c.a = fcb.c.a + 1; + cb.c.b = 0; + } else + cb.s = fcb.s; + makecombo(cbp, fsp, 0, cb.s); + } + + /* + * The next four spots are handled the same for both + * open and closed ended frames. + */ + d = dd[r]; + sp = fsp + d; + for (i = 1; i < 5; i++, sp += d) { + if (sp->s_occ != EMPTY) + continue; + makecombo(cbp, sp, i, fcb.s); + } + } while ((cbp = cbp->c_next) != ecbp); + + /* put all the combos in the hash list on the sorted list */ + cbpp = &hashcombos[FAREA]; + do { + cbp = *--cbpp; + if (cbp == (struct combostr *)0) + continue; + *cbpp = (struct combostr *)0; + ecbp = sortcombos; + if (ecbp == (struct combostr *)0) + sortcombos = cbp; + else { + /* append to sort list */ + pcbp = ecbp->c_prev; + pcbp->c_next = cbp; + ecbp->c_prev = cbp->c_prev; + cbp->c_prev->c_next = ecbp; + cbp->c_prev = pcbp; + } + } while (cbpp != hashcombos); +} + +/* + * Compute all level N combos of frames intersecting spot 'osp' + * within the frame 'ocbp' and combo value 's'. + */ +makecombo(ocbp, osp, off, s) + struct combostr *ocbp; + struct spotstr *osp; + int off; + int s; +{ + register struct combostr *cbp, *ncbp; + register struct spotstr *sp; + register struct elist *ep; + register int n, c; + struct elist *nep, **epp; + struct combostr **scbpp; + int baseB, fcnt, emask, verts, d; + union comboval ocb, cb; + struct ovlp_info vertices[1]; + + ocb.s = s; + baseB = ocb.c.a + ocb.c.b - 1; + fcnt = ocb.c.a - 2; + emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0; + for (ep = osp->s_empty; ep; ep = ep->e_next) { + /* check for various kinds of overlap */ + cbp = ep->e_combo; + verts = checkframes(cbp, ocbp, osp, s, vertices); + if (verts < 0) + continue; + + /* check to see if this frame forms a valid loop */ + if (verts) { + sp = &board[vertices[0].o_intersect]; +#ifdef DEBUG + if (sp->s_occ != EMPTY) { + sprintf(fmtbuf, "loop: %c %s", "BW"[curcolor], + stoc(sp - board)); + dlog(fmtbuf); + whatsup(0); + } +#endif + /* + * It is a valid loop if the intersection spot + * of the frame we are trying to attach is one + * of the completion spots of the combostr + * we are trying to attach the frame to. + */ + for (nep = sp->s_empty; nep; nep = nep->e_next) { + if (nep->e_combo == cbp) + goto fnd; + if (nep->e_combo->c_nframes < cbp->c_nframes) + break; + } + /* frame overlaps but not at a valid spot */ + continue; + fnd: + ; + } + + /* compute the first half of the combo value */ + c = cbp->c_combo.c.a + ocb.c.a - verts - 3; + if (c > 4) + continue; + + /* compute the second half of the combo value */ + n = ep->e_fval.c.a + ep->e_fval.c.b - 1; + if (baseB < n) + n = baseB; + + /* make a new combo! */ + ncbp = (struct combostr *)malloc(sizeof(struct combostr) + + (cbp->c_nframes + 1) * sizeof(struct combostr *)); + scbpp = (struct combostr **)(ncbp + 1); + if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) { + free(ncbp); + continue; + } + combocnt++; + + ncbp->c_combo.c.a = c; + ncbp->c_combo.c.b = n; + ncbp->c_link[0] = cbp; + ncbp->c_link[1] = ocbp; + ncbp->c_linkv[1].s = ocb.s; + ncbp->c_voff[1] = off; + ncbp->c_vertex = osp - board; + ncbp->c_nframes = cbp->c_nframes + 1; + ncbp->c_flg = ocb.c.b ? C_OPEN_1 : 0; + ncbp->c_frameindex = ep->e_frameindex; + /* + * Update the completion spot mask of the frame we + * are attaching 'ocbp' to so the intersection isn't + * listed twice. + */ + ncbp->c_framecnt[0] = ep->e_framecnt; + ncbp->c_emask[0] = ep->e_emask; + if (verts) { + ncbp->c_flg |= C_LOOP; + ncbp->c_dir = vertices[0].o_frameindex; + ncbp->c_framecnt[1] = fcnt - 1; + if (ncbp->c_framecnt[1]) { + n = (vertices[0].o_intersect - ocbp->c_vertex) / + dd[ocbp->c_dir]; + ncbp->c_emask[1] = emask & ~(1 << n); + } else + ncbp->c_emask[1] = 0; + ncbp->c_voff[0] = vertices[0].o_off; + } else { + ncbp->c_dir = 0; + ncbp->c_framecnt[1] = fcnt; + ncbp->c_emask[1] = emask; + ncbp->c_voff[0] = ep->e_off; + } + + if (c == 1 && debug > 1 || debug > 3) { + sprintf(fmtbuf, "%c v%d i%d d%d c %d %d m %x %x o %d %d", + "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir, + ncbp->c_framecnt[0], ncbp->c_framecnt[1], + ncbp->c_emask[0], ncbp->c_emask[1], + ncbp->c_voff[0], ncbp->c_voff[1]); + dlog(fmtbuf); + printcombo(ncbp, fmtbuf); + dlog(fmtbuf); + } + if (c > 1) { + /* record the empty spots that will complete this combo */ + makeempty(ncbp); + combolen++; + } else { + /* update board values */ + updatecombo(ncbp, curcolor); + } +#ifdef DEBUG + if (c == 1 && debug > 1 || debug > 4) { + markcombo(ncbp); + bdisp(); + whatsup(0); + clearcombo(ncbp, 0); + } +#endif /* DEBUG */ + } +} + +#define MAXDEPTH 100 +struct elist einfo[MAXDEPTH]; +struct combostr *ecombo[MAXDEPTH]; /* separate from elist to save space */ + +/* + * Add the combostr 'ocbp' to the empty spots list for each empty spot + * in 'ocbp' that will complete the combo. + */ +makeempty(ocbp) + struct combostr *ocbp; +{ + struct combostr *cbp, *tcbp, **cbpp; + struct elist *ep, *nep, **epp; + struct spotstr *sp; + int s, d, m, emask, i; + int nframes; + + if (debug > 2) { + sprintf(fmtbuf, "E%c ", "bw"[curcolor]); + printcombo(ocbp, fmtbuf + 3); + dlog(fmtbuf); + } + + /* should never happen but check anyway */ + if ((nframes = ocbp->c_nframes) >= MAXDEPTH) + return; + + /* + * The lower level combo can be pointed to by more than one + * higher level 'struct combostr' so we can't modify the + * lower level. Therefore, higher level combos store the + * real mask of the lower level frame in c_emask[0] and the + * frame number in c_frameindex. + * + * First we traverse the tree from top to bottom and save the + * connection info. Then we traverse the tree from bottom to + * top overwriting lower levels with the newer emask information. + */ + ep = &einfo[nframes]; + cbpp = &ecombo[nframes]; + for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { + ep--; + ep->e_combo = cbp; + *--cbpp = cbp->c_link[1]; + ep->e_off = cbp->c_voff[1]; + ep->e_frameindex = cbp->c_frameindex; + ep->e_fval.s = cbp->c_linkv[1].s; + ep->e_framecnt = cbp->c_framecnt[1]; + ep->e_emask = cbp->c_emask[1]; + } + cbp = ep->e_combo; + ep--; + ep->e_combo = cbp; + *--cbpp = cbp->c_link[0]; + ep->e_off = cbp->c_voff[0]; + ep->e_frameindex = 0; + ep->e_fval.s = cbp->c_linkv[0].s; + ep->e_framecnt = cbp->c_framecnt[0]; + ep->e_emask = cbp->c_emask[0]; + + /* now update the emask info */ + s = 0; + for (i = 2, ep += 2; i < nframes; i++, ep++) { + cbp = ep->e_combo; + nep = &einfo[ep->e_frameindex]; + nep->e_framecnt = cbp->c_framecnt[0]; + nep->e_emask = cbp->c_emask[0]; + + if (cbp->c_flg & C_LOOP) { + s++; + /* + * Account for the fact that this frame connects + * to a previous one (thus forming a loop). + */ + nep = &einfo[cbp->c_dir]; + if (--nep->e_framecnt) + nep->e_emask &= ~(1 << cbp->c_voff[0]); + else + nep->e_emask = 0; + } + } + + /* + * We only need to update the emask values of "complete" loops + * to include the intersection spots. + */ + if (s && ocbp->c_combo.c.a == 2) { + /* process loops from the top down */ + ep = &einfo[nframes]; + do { + ep--; + cbp = ep->e_combo; + if (!(cbp->c_flg & C_LOOP)) + continue; + + /* + * Update the emask values to include the + * intersection spots. + */ + nep = &einfo[cbp->c_dir]; + nep->e_framecnt = 1; + nep->e_emask = 1 << cbp->c_voff[0]; + ep->e_framecnt = 1; + ep->e_emask = 1 << ep->e_off; + ep = &einfo[ep->e_frameindex]; + do { + ep->e_framecnt = 1; + ep->e_emask = 1 << ep->e_off; + ep = &einfo[ep->e_frameindex]; + } while (ep > nep); + } while (ep != einfo); + } + + /* check all the frames for completion spots */ + for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) { + /* skip this frame if there are no incomplete spots in it */ + if ((emask = ep->e_emask) == 0) + continue; + cbp = *cbpp; + sp = &board[cbp->c_vertex]; + d = dd[cbp->c_dir]; + for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) { + if (sp->s_occ != EMPTY || !(emask & m)) + continue; + + /* add the combo to the list of empty spots */ + nep = (struct elist *)malloc(sizeof(struct elist)); + nep->e_combo = ocbp; + nep->e_off = s; + nep->e_frameindex = i; + if (ep->e_framecnt > 1) { + nep->e_framecnt = ep->e_framecnt - 1; + nep->e_emask = emask & ~m; + } else { + nep->e_framecnt = 0; + nep->e_emask = 0; + } + nep->e_fval.s = ep->e_fval.s; + if (debug > 2) { + sprintf(fmtbuf, "e %s o%d i%d c%d m%x %x", + stoc(sp - board), + nep->e_off, + nep->e_frameindex, + nep->e_framecnt, + nep->e_emask, + nep->e_fval.s); + dlog(fmtbuf); + } + + /* sort by the number of frames in the combo */ + nep->e_next = sp->s_nempty; + sp->s_nempty = nep; + elistcnt++; + } + } +} + +/* + * Update the board value based on the combostr. + * This is called only if 'cbp' is a <1,x> combo. + * We handle things differently depending on whether the next move + * would be trying to "complete" the combo or trying to block it. + */ +updatecombo(cbp, color) + struct combostr *cbp; + int color; +{ + register struct framestr *fp; + register struct spotstr *sp; + register struct combostr *tcbp; + register int i, d; + int nframes, flg, s; + union comboval cb; + + /* save the top level value for the whole combo */ + cb.c.a = cbp->c_combo.c.a; + nframes = cbp->c_nframes; + + if (color != nextcolor) + memset(tmpmap, 0, sizeof(tmpmap)); + + for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { + flg = cbp->c_flg; + cb.c.b = cbp->c_combo.c.b; + if (color == nextcolor) { + /* update the board value for the vertex */ + sp = &board[cbp->c_vertex]; + sp->s_nforce[color]++; + if (cb.s <= sp->s_combo[color].s) { + if (cb.s != sp->s_combo[color].s) { + sp->s_combo[color].s = cb.s; + sp->s_level[color] = nframes; + } else if (nframes < sp->s_level[color]) + sp->s_level[color] = nframes; + } + } else { + /* update the board values for each spot in frame */ + sp = &board[s = tcbp->c_vertex]; + d = dd[tcbp->c_dir]; + i = (flg & C_OPEN_1) ? 6 : 5; + for (; --i >= 0; sp += d, s += d) { + if (sp->s_occ != EMPTY) + continue; + sp->s_nforce[color]++; + if (cb.s <= sp->s_combo[color].s) { + if (cb.s != sp->s_combo[color].s) { + sp->s_combo[color].s = cb.s; + sp->s_level[color] = nframes; + } else if (nframes < sp->s_level[color]) + sp->s_level[color] = nframes; + } + BIT_SET(tmpmap, s); + } + } + + /* mark the frame as being part of a <1,x> combo */ + board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir; + } + + if (color != nextcolor) { + /* update the board values for each spot in frame */ + sp = &board[s = cbp->c_vertex]; + d = dd[cbp->c_dir]; + i = (flg & C_OPEN_0) ? 6 : 5; + for (; --i >= 0; sp += d, s += d) { + if (sp->s_occ != EMPTY) + continue; + sp->s_nforce[color]++; + if (cb.s <= sp->s_combo[color].s) { + if (cb.s != sp->s_combo[color].s) { + sp->s_combo[color].s = cb.s; + sp->s_level[color] = nframes; + } else if (nframes < sp->s_level[color]) + sp->s_level[color] = nframes; + } + BIT_SET(tmpmap, s); + } + if (nforce == 0) + memcpy(forcemap, tmpmap, sizeof(tmpmap)); + else { + for (i = 0; i < MAPSZ; i++) + forcemap[i] &= tmpmap[i]; + } + nforce++; + } + + /* mark the frame as being part of a <1,x> combo */ + board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir; +} + +/* + * Add combo to the end of the list. + */ +appendcombo(cbp, color) + struct combostr *cbp; + int color; +{ + struct combostr *pcbp, *ncbp; + + combolen++; + ncbp = sortcombos; + if (ncbp == (struct combostr *)0) { + sortcombos = cbp; + cbp->c_next = cbp; + cbp->c_prev = cbp; + return; + } + pcbp = ncbp->c_prev; + cbp->c_next = ncbp; + cbp->c_prev = pcbp; + ncbp->c_prev = cbp; + pcbp->c_next = cbp; +} + +/* + * Return zero if it is valid to combine frame 'fcbp' with the frames + * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops). + * Return positive if combining frame 'fcbp' to the frames in 'cbp' + * would form some kind of valid loop. Also return the intersection spots + * in 'vertices[]' beside the known intersection at spot 'osp'. + * Return -1 if 'fcbp' should not be combined with 'cbp'. + * 's' is the combo value for frame 'fcpb'. + */ +checkframes(cbp, fcbp, osp, s, vertices) + struct combostr *cbp; + struct combostr *fcbp; + struct spotstr *osp; + int s; + struct ovlp_info *vertices; +{ + struct combostr *tcbp, *lcbp; + int i, n, mask, flg, verts, loop, index, fcnt; + union comboval cb; + u_char *str; + short *ip; + + cb.s = s; + fcnt = cb.c.a - 2; + verts = 0; + loop = 0; + index = cbp->c_nframes; + n = (fcbp - frames) * FAREA; + str = &overlap[n]; + ip = &intersect[n]; + /* + * i == which overlap bit to test based on whether 'fcbp' is + * an open or closed frame. + */ + i = cb.c.b ? 2 : 0; + for (; tcbp = cbp->c_link[1]; lcbp = cbp, cbp = cbp->c_link[0]) { + if (tcbp == fcbp) + return (-1); /* fcbp is already included */ + + /* check for intersection of 'tcbp' with 'fcbp' */ + index--; + mask = str[tcbp - frames]; + flg = cbp->c_flg; + n = i + ((flg & C_OPEN_1) != 0); + if (mask & (1 << n)) { + /* + * The two frames are not independent if they + * both lie in the same line and intersect at + * more than one point. + */ + if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n))) + return (-1); + /* + * If this is not the spot we are attaching + * 'fcbp' to and it is a reasonable intersection + * spot, then there might be a loop. + */ + n = ip[tcbp - frames]; + if (osp != &board[n]) { + /* check to see if this is a valid loop */ + if (verts) + return (-1); + if (fcnt == 0 || cbp->c_framecnt[1] == 0) + return (-1); + /* + * Check to be sure the intersection is not + * one of the end points if it is an open + * ended frame. + */ + if ((flg & C_OPEN_1) && + (n == tcbp->c_vertex || + n == tcbp->c_vertex + 5 * dd[tcbp->c_dir])) + return (-1); /* invalid overlap */ + if (cb.c.b && + (n == fcbp->c_vertex || + n == fcbp->c_vertex + 5 * dd[fcbp->c_dir])) + return (-1); /* invalid overlap */ + + vertices->o_intersect = n; + vertices->o_fcombo = cbp; + vertices->o_link = 1; + vertices->o_off = (n - tcbp->c_vertex) / + dd[tcbp->c_dir]; + vertices->o_frameindex = index; + verts++; + } + } + n = i + ((flg & C_OPEN_0) != 0); + } + if (cbp == fcbp) + return (-1); /* fcbp is already included */ + + /* check for intersection of 'cbp' with 'fcbp' */ + mask = str[cbp - frames]; + if (mask & (1 << n)) { + /* + * The two frames are not independent if they + * both lie in the same line and intersect at + * more than one point. + */ + if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n))) + return (-1); + /* + * If this is not the spot we are attaching + * 'fcbp' to and it is a reasonable intersection + * spot, then there might be a loop. + */ + n = ip[cbp - frames]; + if (osp != &board[n]) { + /* check to see if this is a valid loop */ + if (verts) + return (-1); + if (fcnt == 0 || lcbp->c_framecnt[0] == 0) + return (-1); + /* + * Check to be sure the intersection is not + * one of the end points if it is an open + * ended frame. + */ + if ((flg & C_OPEN_0) && + (n == cbp->c_vertex || + n == cbp->c_vertex + 5 * dd[cbp->c_dir])) + return (-1); /* invalid overlap */ + if (cb.c.b && + (n == fcbp->c_vertex || + n == fcbp->c_vertex + 5 * dd[fcbp->c_dir])) + return (-1); /* invalid overlap */ + + vertices->o_intersect = n; + vertices->o_fcombo = lcbp; + vertices->o_link = 0; + vertices->o_off = (n - cbp->c_vertex) / + dd[cbp->c_dir]; + vertices->o_frameindex = 0; + verts++; + } + } + return (verts); +} + +/* + * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and + * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array. + * Return true if this list of frames is already in the hash list. + * Otherwise, add the new combo to the hash list. + */ +sortcombo(scbpp, cbpp, fcbp) + struct combostr **scbpp; + struct combostr **cbpp; + struct combostr *fcbp; +{ + struct combostr **spp, **cpp; + struct combostr *cbp, *ecbp; + int n, inx; + +#ifdef DEBUG + if (debug > 3) { + char *str; + + sprintf(fmtbuf, "sortc: %s%c l%d", stoc(fcbp->c_vertex), + pdir[fcbp->c_dir], curlevel); + dlog(fmtbuf); + str = fmtbuf; + for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) { + sprintf(str, " %s%c", stoc((*cpp)->c_vertex), + pdir[(*cpp)->c_dir]); + str += strlen(str); + } + dlog(fmtbuf); + } +#endif /* DEBUG */ + + /* first build the new sorted list */ + n = curlevel + 1; + spp = scbpp + n; + cpp = cbpp + curlevel; + do { + cpp--; + if (fcbp > *cpp) { + *--spp = fcbp; + do + *--spp = *cpp; + while (cpp-- != cbpp); + goto inserted; + } + *--spp = *cpp; + } while (cpp != cbpp); + *--spp = fcbp; +inserted: + + /* now check to see if this list of frames has already been seen */ + cbp = hashcombos[inx = *scbpp - frames]; + if (cbp == (struct combostr *)0) { + /* + * Easy case, this list hasn't been seen. + * Add it to the hash list. + */ + fcbp = (struct combostr *) + ((char *)scbpp - sizeof(struct combostr)); + hashcombos[inx] = fcbp; + fcbp->c_next = fcbp->c_prev = fcbp; + return (0); + } + ecbp = cbp; + do { + cbpp = (struct combostr **)(cbp + 1); + cpp = cbpp + n; + spp = scbpp + n; + cbpp++; /* first frame is always the same */ + do { + if (*--spp != *--cpp) + goto next; + } while (cpp != cbpp); + /* we found a match */ +#ifdef DEBUG + if (debug > 3) { + char *str; + + sprintf(fmtbuf, "sort1: n%d", n); + dlog(fmtbuf); + str = fmtbuf; + for (cpp = scbpp; cpp < scbpp + n; cpp++) { + sprintf(str, " %s%c", stoc((*cpp)->c_vertex), + pdir[(*cpp)->c_dir]); + str += strlen(str); + } + dlog(fmtbuf); + printcombo(cbp, fmtbuf); + dlog(fmtbuf); + str = fmtbuf; + cbpp--; + for (cpp = cbpp; cpp < cbpp + n; cpp++) { + sprintf(str, " %s%c", stoc((*cpp)->c_vertex), + pdir[(*cpp)->c_dir]); + str += strlen(str); + } + dlog(fmtbuf); + } +#endif /* DEBUG */ + return (1); + next: + ; + } while ((cbp = cbp->c_next) != ecbp); + /* + * This list of frames hasn't been seen. + * Add it to the hash list. + */ + ecbp = cbp->c_prev; + fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr)); + fcbp->c_next = cbp; + fcbp->c_prev = ecbp; + cbp->c_prev = fcbp; + ecbp->c_next = fcbp; + return (0); +} + +/* + * Print the combo into string 'str'. + */ +printcombo(cbp, str) + struct combostr *cbp; + char *str; +{ + struct combostr *tcbp; + + sprintf(str, "%x/%d", cbp->c_combo.s, cbp->c_nframes); + str += strlen(str); + for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { + sprintf(str, " %s%c%x", stoc(tcbp->c_vertex), pdir[tcbp->c_dir], + cbp->c_flg); + str += strlen(str); + } + sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]); +} + +#ifdef DEBUG +markcombo(ocbp) + struct combostr *ocbp; +{ + struct combostr *cbp, *tcbp, **cbpp; + struct elist *ep, *nep, **epp; + struct spotstr *sp; + int s, d, m, i; + int nframes; + int r, n, flg, cmask, omask; + + /* should never happen but check anyway */ + if ((nframes = ocbp->c_nframes) >= MAXDEPTH) + return; + + /* + * The lower level combo can be pointed to by more than one + * higher level 'struct combostr' so we can't modify the + * lower level. Therefore, higher level combos store the + * real mask of the lower level frame in c_emask[0] and the + * frame number in c_frameindex. + * + * First we traverse the tree from top to bottom and save the + * connection info. Then we traverse the tree from bottom to + * top overwriting lower levels with the newer emask information. + */ + ep = &einfo[nframes]; + cbpp = &ecombo[nframes]; + for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { + ep--; + ep->e_combo = cbp; + *--cbpp = cbp->c_link[1]; + ep->e_off = cbp->c_voff[1]; + ep->e_frameindex = cbp->c_frameindex; + ep->e_fval.s = cbp->c_linkv[1].s; + ep->e_framecnt = cbp->c_framecnt[1]; + ep->e_emask = cbp->c_emask[1]; + } + cbp = ep->e_combo; + ep--; + ep->e_combo = cbp; + *--cbpp = cbp->c_link[0]; + ep->e_off = cbp->c_voff[0]; + ep->e_frameindex = 0; + ep->e_fval.s = cbp->c_linkv[0].s; + ep->e_framecnt = cbp->c_framecnt[0]; + ep->e_emask = cbp->c_emask[0]; + + /* now update the emask info */ + s = 0; + for (i = 2, ep += 2; i < nframes; i++, ep++) { + cbp = ep->e_combo; + nep = &einfo[ep->e_frameindex]; + nep->e_framecnt = cbp->c_framecnt[0]; + nep->e_emask = cbp->c_emask[0]; + + if (cbp->c_flg & C_LOOP) { + s++; + /* + * Account for the fact that this frame connects + * to a previous one (thus forming a loop). + */ + nep = &einfo[cbp->c_dir]; + if (--nep->e_framecnt) + nep->e_emask &= ~(1 << cbp->c_voff[0]); + else + nep->e_emask = 0; + } + } + + /* + * We only need to update the emask values of "complete" loops + * to include the intersection spots. + */ + if (s && ocbp->c_combo.c.a == 2) { + /* process loops from the top down */ + ep = &einfo[nframes]; + do { + ep--; + cbp = ep->e_combo; + if (!(cbp->c_flg & C_LOOP)) + continue; + + /* + * Update the emask values to include the + * intersection spots. + */ + nep = &einfo[cbp->c_dir]; + nep->e_framecnt = 1; + nep->e_emask = 1 << cbp->c_voff[0]; + ep->e_framecnt = 1; + ep->e_emask = 1 << ep->e_off; + ep = &einfo[ep->e_frameindex]; + do { + ep->e_framecnt = 1; + ep->e_emask = 1 << ep->e_off; + ep = &einfo[ep->e_frameindex]; + } while (ep > nep); + } while (ep != einfo); + } + + /* mark all the frames with the completion spots */ + for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) { + m = ep->e_emask; + cbp = *cbpp; + sp = &board[cbp->c_vertex]; + d = dd[s = cbp->c_dir]; + cmask = CFLAG << s; + omask = (IFLAG | CFLAG) << s; + s = ep->e_fval.c.b ? 6 : 5; + for (; --s >= 0; sp += d, m >>= 1) + sp->s_flg |= (m & 1) ? omask : cmask; + } +} + +clearcombo(cbp, open) + struct combostr *cbp; + int open; +{ + register struct spotstr *sp; + struct combostr *tcbp; + int d, n, mask; + + for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { + clearcombo(tcbp, cbp->c_flg & C_OPEN_1); + open = cbp->c_flg & C_OPEN_0; + } + sp = &board[cbp->c_vertex]; + d = dd[n = cbp->c_dir]; + mask = ~((IFLAG | CFLAG) << n); + n = open ? 6 : 5; + for (; --n >= 0; sp += d) + sp->s_flg &= mask; +} + +list_eq(scbpp, cbpp, n) + struct combostr **scbpp; + struct combostr **cbpp; + int n; +{ + struct combostr **spp, **cpp; + + spp = scbpp + n; + cpp = cbpp + n; + do { + if (*--spp != *--cpp) + return (0); + } while (cpp != cbpp); + /* we found a match */ + return (1); +} +#endif /* DEBUG */ diff --git a/games/gomoku/stoc.c b/games/gomoku/stoc.c new file mode 100644 index 00000000000..2d77eea1ae6 --- /dev/null +++ b/games/gomoku/stoc.c @@ -0,0 +1,107 @@ +/* $OpenBSD: stoc.c,v 1.1.1.1 1996/12/16 06:56:09 downsj Exp $ */ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ralph Campbell. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)stoc.c 8.1 (Berkeley) 7/24/94"; +#endif /* not lint */ + +#include "gomoku.h" +#include + +char *letters = ""; + +struct mvstr { + int m_code; + char *m_text; +}; +static struct mvstr mv[] = { + RESIGN, "resign", + RESIGN, "quit", + SAVE, "save", + -1, 0 +}; + +/* + * Turn the spot number form of a move into the character form. + */ +char * +stoc(s) + int s; +{ + static char buf[32]; + register int i; + + for (i = 0; mv[i].m_code >= 0; i++) + if (s == mv[i].m_code) + return(mv[i].m_text); + sprintf(buf, "%c%d", letters[s % BSZ1], s / BSZ1); + return(buf); +} + +/* + * Turn the character form of a move into the spot number form. + */ +ctos(mp) + char *mp; +{ + register int i; + + for (i = 0; mv[i].m_code >= 0; i++) + if (strcmp(mp, mv[i].m_text) == 0) + return(mv[i].m_code); + if (!isalpha(mp[0])) + return(ILLEGAL); + i = atoi(&mp[1]); + if (i < 1 || i > 19) + return(ILLEGAL); + return(PT(lton(mp[0]), i)); +} + +/* + * Turn a letter into a number. + */ +lton(c) + int c; +{ + register int i; + + if (islower(c)) + c = toupper(c); + for (i = 1; i <= BSZ && letters[i] != c; i++) + ; + return(i); +} -- 2.20.1