nickle 2.81-1 / usr / share / nickle / examples / menace2.5c

/*
 * MENACE was a 1960 construction by Michie which
 * learned to play Tic-Tac-Toe.  Remarkably, it did this
 * using only a large number of matchboxes and
 * colored glass beads: no computer was involved.
 *   http://www.atarimagazines.com/v3n1/matchboxttt.html
 * 
 * MENACE2 is a simulation of this system in Nickle.
 *   http://www.cs.pdx.edu/~bart/cs541-fall2001/homework/3-learn.html
 *
 *
 * Copyright © 2001  Bart Massey.
 * All Rights Reserved.  See the file COPYING in this directory
 * for licensing information.
 *
 * Bart Massey 2001/11/21
 */

autoload PRNG;

/* initial weight */
const int initial_weight = 32;

/* move weights for legal moves */
typedef int[3,3] weights;

/* pieces/players */
typedef enum {
    x, o, none
} piece;

/* board positions */
typedef piece[3,3] position;

/* all rotations and reflections of a board position */
typedef position[8] poslist;

/* transposition table (memory) entry */
typedef ttent;

typedef union {
    *ttent  ref;
    void    end;
} ttentref;

typedef struct {
    piece on_move;
    poslist posns;
    int nmoves;
    int tweight;
    weights val;
    ttentref next;
} ttent;

/* the transposition table (memory) */
ttentref ttable = ttentref.end;

/* whose turn it is: piece.none == board full  */
piece side_on_move(*position b) {
  int n = 0;
  for(int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      if (b*[i,j] != piece.none)
	n++;
  if (n == 9)
    return piece.none;
  if (n % 2 == 1)
    return piece.o;
  return piece.x;
}

/* number of explored states */
int nttstates = 0;


/* lookup or create the current pos in the ttable */
ttentref ttable_lookup(position pos) {

    /* return all rotations/reflections of pos */
    poslist all_posns(position pos) {
	/* a transformation: elems are in 3 * y + x form */
	typedef int[9] xform;
	xform rot = {2,5,8,1,4,7,0,3,6};
	xform refl = {0,3,6,1,4,7,2,5,8};
	/* return the x-transformed version of p */
	position do_xform(xform x, position p) {
	    position np;
	    for (int i = 0; i < 9; i++)
		np[x[i] % 3, x[i] // 3] = p[i % 3, i // 3];
	    return np;
	}
	poslist result;
	int j = 0;
	for (int i = 0; i < 4; i++) {
	    result[j++] = pos;
	    position reflpos = do_xform(refl, pos);
	    result[j++] = reflpos;
	    pos = do_xform(rot, pos);
	}
	return result;
    }

    /* first, try to look up an old entry */
    for (ttentref t = ttable; t != ttentref.end; t = t.ref->next)
	for (int i = 0; i < 8; i++)
	    if (t.ref->posns[i] == pos)
		return t;
    /* nope: create a new entry */
    nttstates++;
    ttent t = {
	.on_move = side_on_move(&pos),
	.posns = all_posns(pos),
	.next = ttable
    };
    /* count legal moves */
    int nmoves = 0;
    for (int i = 0; i < 3; i++)
	for (int j = 0; j < 3; j++)
	    if (pos[i, j] == piece.none)
		nmoves++;
    t.nmoves = nmoves;
    /* set up initial weights */
    t.tweight = 0;
    for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	    if (pos[i, j] == piece.none) {
		t.val[i, j] = initial_weight;
		t.tweight += initial_weight;
	    } else {
		t.val[i, j] = 0;
	    }
	}
    }
    /* insert the new entry into the table */
    ttable = (ttentref.ref) (&t);
    return ttable;
}

/* actually run a game from the given position
   and adjust the weights */
piece menace2(position b) {

    /* check for a win */
    piece win(*position b) {

	/* check for a row, given delta and base in x and y */
	piece row(*position b,
			   int dx, int dy,
			   int bx, int by) {
	  if (b*[dx + bx,dy + by] == b*[bx,by] &&
	      b*[dx + dx + bx,dy + dy + by] == b*[bx,by])
	    return b*[bx,by];
	  return piece.none;
	}

	/* check rows and columns */
	for (int i = 0; i < 3; i++) {
	  piece w = row(b, 0, 1, i, 0);
	  if (w != piece.none)
	    return w;
	  piece w = row(b, 1, 0, 0, i);
	  if (w != piece.none)
	    return w;
	}
	/* check diagonals */
	piece w = row(b, 1, 1, 0, 0);
	if (w != piece.none)
	  return w;
	return row(b, 1, -1, 0, 2);
      }

    piece w = win(&b);
    if (w != piece.none)
	return w;
    piece us = side_on_move(&b);
    if (us == piece.none)
	return us;
    *ttent t = ttable_lookup(b).ref;
    b = t->posns[0];
    int r = PRNG::randint(t->tweight) + 1;
    for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	    if (b[i, j] == piece.none) {
		r -= t->val[i, j];
		if (r <= 0) {
		    b[i, j] = us;
		    piece w = menace2(b);
		    b[i, j] = piece.none;
		    if (t->nmoves <= 1)
			return w;
		    rational delta;
		    switch (w) {
		    case us:
			t->val[i,j] += 3;
			t->tweight += 3;
			return w;
		    case piece.none:
			return w;
		    }
		    if (t->val[i,j] <= 1)
			return w;
		    --t->val[i,j];
		    --t->tweight;
		    return w;
		}
	    }
	}
    }
    abort("menace2: weird t->val");
}

void go(int n) {
    position b;
    for (int i = 0; i < 9; i++) {
	int j;
	scanf("%d", &j);
	switch (j) {
	case -1: b[i % 3, i // 3] = piece.o; break;
	case 1: b[i % 3, i // 3] = piece.x; break;
	case 0: b[i % 3, i // 3] = piece.none; break;
	default: abort("bad piece on input");
	}
    }
    for(int i = 0; i < n; i++)
	piece w = menace2(b);
    *ttent t = ttable_lookup(b).ref;
    for(int j = 0; j < 3; j++) {
    	for(int i = 0; i < 3; i++) {
	    string label(piece p) {
		union switch (p) {
		case x: return "X";
		case o: return "O";
		case none: abort("label: blank label"); return "";
		}
	    }
	    if (b[i,j] == piece.none)
		printf("%8d", t->val[i,j]);
	    else
		printf("%8s", label(b[i,j]));
	}
        printf("\n");
    }
    printf("%d states explored\n", nttstates);
}

int n = string_to_integer(argv[1]);
go(n);