From: mjd@saul.cis.upenn.edu ("[*] The Power in the Streets")
Newsgroups: rec.games.abstract
Subject: New Old Paper and Pencil Game (Sim)
Date: 11 Nov 92 23:55:26 GMT
Organization: Eaters of Wisdom


You need two different colors of pencils for this.

Draw six spots.  That's the board.

    Players take turns drawing a straight line of their own color
between two spots that don't already have a line between them.  (There
are 15 pairs of spots, so the game is over in 15 moves.)

    If you make a triangle whose edges are your color and whose vertices
are spots, you lose.

    The game is a second-player win, (there's a lovely proof that it
can't be a tie. and the usual it-can't-hurt-to-have-a-free-move argument
applies in reverse) but is quite playable.  The computer regularly beats
me even when I go second.  (Source code for X version follows.  I got it
from a gentleman at Carnegie Mellon.  To make a non-X version, cut out
the X parts.)

/* xsim.c */
/* Paper and pencil game, coloring a six clique avoiding triangles */
/* Copyright Enderton 1990 */
/* Make with "cc -O ramsey.c -lX11 -lm" */
	
#include <stdio.h>
#include "assert.h"
#include <X11/X.h>
#include <X11/Xlib.h>
#include <X11/Xatom.h>
#include <X11/Xutil.h>
#include <math.h>

extern Display * XOpenDisplay ();
Window win;
Display * dpy;
GC gc[2]; /* different line styles */
XSetWindowAttributes xswa;
XEvent xev;

int vert [2][15] = { 
  { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 },
  { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 } };

int edge [6][6] =   { 
  { -1,  0,  1,  2,  3,  4 },
  {  0, -1,  5,  6,  7,  8 },
  {  1,  5, -1,  9, 10, 11 },
  {  2,  6,  9, -1, 12, 13 },
  {  3,  7, 10, 12, -1, 14 },
  {  4,  8, 11, 13, 14, -1 } };

int board [15];
int onmove;

#define EMPTY 0
#define SOLID 1
#define DASH 2
#define opposite(x) (3-x)

int 
  number () 
{
  int i, n = 0;
  /* board [0] is always SOLID */
  for (i = 1; i < 15; i++) {
    n = 3 * n + board [i]; 
  }

  /* 0 <= n < 4782969 */
  assert ( n < 4782969);
  return n; 
}

char database [4782969];

int 
  losing (move) 
int move; 
{
  int u, v, w;
  u = vert [0][move];
  v = vert [1][move];
  for (w = 6; w--; ) {
    if (w == u || w == v) continue;
    if (board [edge [u][w]] == onmove && 
	board [edge [v][w]] == onmove) 
      return 1;
  }
  return 0;
}
    
int
  solve () 
{
  /* returns a winning move, or negative if there isn't one */
  int i, v, n;
  v = -1;
  n = number ();
  if (database [n] != 0) return database [n];
  
  for (i = 1; i < 15 && v < 0; i++) 
    {
      if (board [i] != EMPTY || losing (i)) continue;
      board [i] = onmove;
      onmove = opposite (onmove);
      if (solve () < 0) {
	v = i; 
      }
      board [i] = EMPTY;
      onmove = opposite (onmove); 
    }
  database [n] = v;
  return v; 
}

int 
  xc (n) 
int n; 
{
  return (int) (200.5 + 150.0 * cos (n * 3.1415926 / 3.0)); 
}

int 
  yc (n) 
int n; 
{
  return (int) (200.5 - 150.0 * sin (n * 3.1415926 / 3.0)); 
}

void 
  xdraw () 
{
  int i;
  XClearWindow (dpy, win);
  for (i = 0; i < 6; i++) {
    XFillArc (dpy, win, gc[0], xc(i)-5, yc(i)-5, 10, 10, 0, 360*64); 
  }
  for (i = 0; i < 15; i++) {
    switch (board [i]) {
    case SOLID:
      XDrawLine (dpy, win, gc[0], 
		 xc(vert[0][i]), yc(vert[0][i]), 
		 xc (vert[1][i]), yc(vert[1][i]));
      break;
    case DASH:
      XDrawLine (dpy, win, gc[1], 
		 xc(vert[0][i]), yc(vert[0][i]), 
		 xc (vert[1][i]), yc(vert[1][i]));
    default:
      ; 
    } 
  }
  XFlush (dpy); 
}

void 
  xboard_init () 
{
  XGCValues gcv;
  dpy = XOpenDisplay ("");
  if (!dpy) { 
    printf ("XOpenDisplay returned NULL\n"); 
    exit (1); 
  }
  xswa.event_mask = ExposureMask|ButtonPressMask|KeyPressMask;
  xswa.background_pixel = BlackPixel (dpy, DefaultScreen (dpy));
  xswa.backing_store = Always;
  win = XCreateWindow (dpy, DefaultRootWindow (dpy), 
		       0, 0, 400, 400, 2, 0, 
		       InputOutput, CopyFromParent, 
		       CWEventMask | CWBackPixel | CWBackingStore, 
		       & xswa);
  XStoreName (dpy, win, "ramsey");
  gcv.function = GXcopy;
  gcv.plane_mask = AllPlanes;
  gcv.foreground = WhitePixel(dpy,DefaultScreen(dpy));
  gcv.background = BlackPixel(dpy,DefaultScreen(dpy));
  gcv.line_width = 2;
  gcv.fill_style = FillSolid;
  gcv.line_style = LineSolid;
  gc[0] = XCreateGC (dpy, win, 
		     GCFunction | GCPlaneMask | GCForeground | GCBackground | 
		     GCLineWidth | GCFillStyle | GCLineStyle, 
		     & gcv);
  gcv.line_style = LineOnOffDash;
  gc[1] = XCreateGC (dpy, win, 
		     GCFunction | GCPlaneMask | GCForeground | GCBackground | 
		     GCLineWidth | GCFillStyle | GCLineStyle, 
		     & gcv);
  XMapWindow (dpy, win);
  XNextEvent (dpy, &xev); /* exposure */
  xdraw (); 
}

int 
  sq (x) 
int x; 
{ 
  return x * x; 
}

int 
  xprocessevent (buf) 
char * buf; 
{
  int x, y, i, j, len = 0;
  char keys [256];
  XNextEvent (dpy, & xev);
  if (xev.type == ButtonPress) {
    int least = 1000000, closest = 0, dist;
    for (i = 0; i < 6; i++) {
      dist = sq (xev.xbutton.x - xc (i)) + sq (xev.xbutton.y - yc (i));
      if (dist < least) {
	least = dist;
	closest = i; 
      } 
    }
    return closest; 
  }
  else if (xev.type == KeyPress) {
    j = XLookupString (& xev.xkey, keys, 16, NULL, NULL);
    for (i = 0; i < j; i++) {
      buf [len++] = keys [i];
      buf [len] = 0; 
    }
    return -1; 
  }
  else if (xev.type == Expose) {
    xdraw ();
    return xprocessevent (buf); 
  } 
}

int 
  findmove () 
{
  int i, j, win = 0, best = -9999, mostblunders = -1;
  win = solve ();
  if (win >= 0) return win;
  /* in losing position, give opponent most chances to screw up */
  for (i = 0; i < 15; i++) {
    if (board [i] == EMPTY && !losing (i)) {
      int nblunders = 0;
      board [i] = onmove;
      onmove = opposite (onmove);
      for (j = 0; j < 15; j++) {
	if (board [j] == EMPTY && !losing (j)) {
	  board [j] = onmove;
	  onmove = opposite (onmove);
	  if (solve () >= 0) nblunders++;
	  board [j] = EMPTY;
	  onmove = opposite (onmove);
	}
      }
      if (nblunders > mostblunders) {
	mostblunders = nblunders;
	best = i; 
      }
      board [i] = EMPTY;
      onmove = opposite (onmove); 
    } 
  }
  return best; 
}

int 
  nlegal () 
{
  int i, n = 0;
  for (i = 0; i < 15; i++) {
    if (board [i] == EMPTY && !losing (i)) n++; 
  }
  return n; 
}

main () 
{
  int i, j, move;
  int nmoves = 0, history [15];
  int computercolor = SOLID;
  char buf [256];
  for (i = 15; i--; ) board [i] = EMPTY;
  board [0] = SOLID;
  history [nmoves++] = 0;
  onmove = DASH;
  printf ("This is a simple `pencil and paper' game inspired by Ramsey theory.\nOn your turn you select a pair of vertices (by clicking near each one).\nYou may not form a triangle of all one `color'; if forced to do so, you lose.\nOther commands available by hitting a key at the `Your move' prompt while the\nmouse is over the graph window:  `u' to undo, `v' to print theoretical value.\n");
  xboard_init ();
 beginning:
  printf ("Do you want to play the dashed lines (computer takes solid)? ");
  scanf ("%s", buf);
  if (buf [0] != 'y') {
    computercolor = DASH; 
  }
  while (1) {
    if (onmove == computercolor) {
      move = findmove ();
      if (move != -9999) {
	printf ("Computer plays (%d,%d)\n", vert[0][move], vert[1][move]);
	board [move] = onmove;
	history [nmoves++] = move;
	onmove = opposite (onmove);
	xdraw (); 
      } else {
	printf ("I have no legal moves, you win.\n");
	break; 
      } 
    }
    if (nlegal () == 0) {
      printf ("You have no legal moves, you lose.\n");
      break; 
    }
    printf ("Your move:  ");
    fflush (stdout);
    i = xprocessevent (buf);
    if (i == -1 && buf[0] == 'u') {
      printf ("\n");
      if (nmoves > 2) {
	board [history [--nmoves]] = EMPTY;
	board [history [--nmoves]] = EMPTY; 
      } 
    }
    else if (i == -1 && buf [0] == 'v') {
      if (solve () < 0) printf ("\nYou cannot win.\n");
      else printf ("\nYou can still win.\n"); 
    }
    else if (i >= 0) {
      printf ("(%d,", i);
      fflush (stdout);
      j = xprocessevent (buf);
      printf ("%d)\n", j);
      if (i < 0 || i > 5 || j < 0 || j > 5 || i == j) continue;
      move = edge [i][j];			
      if (board [move] != EMPTY) {
	printf ("That edge has already been taken.\n");
	continue; 
      }
      if (losing (move)) {
	printf ("Illegal, that would form a triangle of your color.\n");
	continue; 
      }
      board [move] = onmove;
      onmove = opposite (onmove);				
      history [nmoves++] = move; 
    }
    xdraw ();
    sleep (1); 
  }
  printf ("Do you want to play again? ");
  scanf ("%s", buf);
  if (buf [0] == 'y') {
    for (i = 1; i < 15; i++) board [i] = EMPTY;
    nmoves = 1;
    onmove = DASH;
    xdraw ();
    goto beginning; 
  }
}


--

                And for to se, and eek for to be seye
Mark-Jason Dominus 	  			    mjd@central.cis.upenn.edu 

Newsgroups: rec.games.abstract