checkers.cxx

PIXIL is a small footprint operating environment, complete with PDA PIM applications, a browser and

//
// "$Id: checkers.cxx,v 1.1.1.1 2003/08/07 21:18:42 jasonk Exp $"
//
// Checkers game for the Fast Light Tool Kit (FLTK).
//
// Hours of fun: the FLTK checkers game!
// Based on a very old algorithim, but it still works!
//
// Copyright 1998-1999 by Bill Spitzak and others.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
// USA.
//
// Please report all bugs and problems to "[e-mail]".
//

const char* copyright = 
"Checkers game\n"
"Copyright (C) 1997 Bill Spitzak    [e-mail]\n"
"Original Pascal code:\n"
"Copyright 1978, Oregon Minicomputer Software, Inc.\n"
"2340 SW Canyon Road, Portland, Oregon 97201\n"
"Written by Steve Poulsen 18-Jan-79\n"
"\n"
"This program is free software; you can redistribute it and/or modify "
"it under the terms of the GNU General Public License as published by "
"the Free Software Foundation; either version 2 of the License, or "
"(at your option) any later version.\n"
"\n"
"This program is distributed in the hope that it will be useful, "
"but WITHOUT ANY WARRANTY; without even the implied warranty of "
"MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the "
"GNU General Public License for more details.\n"
"\n"
"You should have received a copy of the GNU Library General Public "
"License along with this library; if not, write to the Free Software "
"Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 "
"USA.";

// Define FLTK to get the fltk interface
// Define VT100 to get the VT100 interface
// Define both to get a program that takes a -t switch

#define FLTK
//#define VT100

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <ctype.h>
#include <time.h>

////////////////////////////////////////////////////////////////
// The algorithim:

int maxevaluate=2500;		// max number of moves to examine on a turn
int maxnodes = 2500;		// maximum number of nodes in search tree
int maxply = 20;		// maximum depth to look ahead
char forcejumps = 1;		// is forced jumps rule in effect?

// scoring parameters: (all divided by 5 from original code)
// some signs seem to be backwards, marked them with (-) in comment
const int spiece = 800;		// value of a piece
const int sking = 1200;		// value of a king
const int sadvan = 160;		// value of mypieces/theirpieces-1
// const int smobil = ?		// moves *enemy* can make w/o being jumped
const int sallpin = 80;		// mobil == 0
const int sdeny = 10;		// moves enemy can make that will be jumped
const int spin = 32;		// enemy pieces that have no move except jumped
const int sthreat = -10;	// enemy pieces we can jump if not moved (-)
const int sgrad = 1;		// score of piece positions
const int sback = 10;		// back row occupied so enemy can't make king
const int smoc2 = 200;		// more mobility, more center
const int smoc3 = -8;		// less mobility, less center
const int smoc4 = -80;		// more mobility, less center
const int smode2 = -14;		// less mobility, less denied
const int smode3 = -40;		// more mobility, more denied (-)
const int sdemmo = -20;		// more denied, more moves (-)
const int scent = 10;		// pieces in center
const int skcent = 100;		// kings in center

const int depthpenalty=4;	// guess
const int noise=2;		// values less or eq to this apart are eq

// const int sattackking = 4;	// not used
// const int sattackpiece = 3;

struct node {
  node *father;
  node *son;		// best son
  node *brother;	// next brother
  short int value;	// value of this board position to player making move
  unsigned char from,to; // the move to reach this board
  long int jump;	// bit map of locations jumped
  unsigned char mobil;
  unsigned char deny;
  unsigned char pin;
  unsigned char threat;
  short int gradient;
  unsigned who:1;	// 0 = black's move, 1 = white's move
  unsigned king:1;	// 1 = move causes piece to be kinged
  unsigned back:1;
  unsigned moc2:1;
  unsigned moc3:1;
  unsigned moc4:1;
  unsigned mode2:1;
  unsigned mode3:1;
  unsigned demmo:1;
};

int nodes;		// count of nodes

/*	Board positions:	Border positions:

	      CWHITE		  00  01  02  03  04
	  05  06  07  08	04  XX  XX  XX  XX
	09  10  11  12		  XX  XX  XX  XX  13
	  14  15  16  17	13  XX  XX  XX  XX
	18  19  20  21		  XX  XX  XX  XX  22
	  23  24  25  26	22  XX  XX  XX  XX
	27  28  29  30		  XX  XX  XX  XX  31
	  32  33  34  36	31  XX  XX  XX  XX
	36  37  38  39		  XX  XX  XX  XX  40
	      CBLACK		40  41  42  43  44

*/

typedef char piece;

// Piece values so that CBLACK and CWHITE are bit flags:
#define EMPTY 0
#define CBLACK 1
#define CWHITE 2
#define KING 4
#define BLACKKING 5
#define WHITEKING 6
#define CBLUE 8

const piece flip[9] = {
  EMPTY, CWHITE, CBLACK, 0, 0, WHITEKING, BLACKKING, 0, CBLUE};

const int offset[9][4] = {	// legal move directions
  {0,0,0,0},
  {-5,-4,0,0},
  {4,5,0,0},
  {0,0,0,0},
  {0,0,0,0},
  {4,5,-4,-5},
  {4,5,-4,-5},
  {0,0,0,0},
  {0,0,0,0}
};

piece b[45];		// current board position being considered

int evaluated;		// number of moves evaluated this turn

char centralsquares[45];
char is_protected[45];

piece flipboard[45];	// swapped if enemy is black
piece *tb;		// pointer to real or swapped board
#define FRIEND CBLACK
#define FRIENDKING BLACKKING
#define ENEMY CWHITE
#define ENEMYKING WHITEKING

char check(int target,int direction) {
  // see if enemy at target can be jumped from direction by our piece
  int dst = target-direction;
  if (tb[dst]) return(0);
  int src = target+direction;
  if (tb[src] == FRIENDKING);
  else if (direction < 0 || tb[src] != FRIEND) return(0);
  piece a = tb[target]; piece b = tb[src];
  tb[target] = EMPTY; tb[src] = EMPTY;
  int safe =
    (tb[src-4]&FRIEND && tb[src-8]&ENEMY
     ||tb[src-5]&FRIEND && tb[src-10]&ENEMY
     ||tb[dst-4]&ENEMY && !tb[dst+4]
     ||tb[dst-5]&ENEMY && !tb[dst+5]
     ||tb[src+4]&FRIEND && tb[src+8]==ENEMYKING
     ||tb[src+5]&FRIEND && tb[src+10]==ENEMYKING
     ||tb[dst+4]==ENEMYKING && !tb[dst-4]
     ||tb[dst+5]==ENEMYKING && !tb[dst-5]);
  tb[target] = a; tb[src] = b;
  return(safe);
}

int deniedmoves,undeniedmoves;
void analyzemove(int direction,int src) {
  int target = src+direction;
  if (!tb[target]) {
    if (!tb[target+direction]) is_protected[target] = 1;
    piece a = tb[src]; tb[src] = EMPTY;
    if (check(target,4) || check(target,5) ||
	check(target,-4) || check(target,-5) ||
	(tb[src+4]&ENEMY && check(src+4,4)) ||
	(tb[src+5]&ENEMY && check(src+5,5)) ||
	(tb[src-4]&ENEMY && check(src-4,-4)) ||
	(tb[src-5]&ENEMY && check(src-5,-5)))
      deniedmoves++;
    else undeniedmoves++;
    tb[src] = a;
  }
}

void evaluateboard(node *n,int print) {

  if (!n->who) tb = b;	// move was black's
  else {
    for (int i=0; i<45; i++) flipboard[44-i] = flip[b[i]];
    tb = flipboard;
  }

  memset(is_protected,0,sizeof(is_protected));
  int friendpieces = 0;
  int enemypieces = 0;
  int friendkings = 0;
  int enemykings = 0;
  int friendkcent = 0;
  int friendcent = 0;
  int enemykcent = 0;
  int enemycent = 0;
  n->mobil = n->deny = n->pin = n->threat = 0;

  int i;
  for (i=5; i<40; i++) switch(tb[i]) {
  case ENEMYKING:
    enemykings++;
    enemykcent += centralsquares[i];
    deniedmoves = 0;
    undeniedmoves = 0;
    if (i>8) {
      analyzemove(-4,i);
      analyzemove(-5,i);
    }
    goto J1;
  case ENEMY:
    deniedmoves = 0;
    undeniedmoves = 0;
  J1:	enemypieces++;
    enemycent += centralsquares[i];
    if (i<36) {
      analyzemove(4,i);
      analyzemove(5,i);
    }
    if (deniedmoves && !undeniedmoves) n->pin++;
    n->deny += deniedmoves;
    n->mobil += undeniedmoves;
    break;
  case FRIENDKING:
    friendkings++;
    friendkcent += centralsquares[i];
    if (tb[i+4]&ENEMY && !tb[i+8] && !(tb[i+4]==ENEMYKING && !tb[i-4]))
      n->threat++;
    if (tb[i+5]&ENEMY && !tb[i+10] && !(tb[i+5]==ENEMYKING && !tb[i-5]))
      n->threat++;
  case FRIEND:
    friendpieces++;
    friendcent += centralsquares[i];
    if (tb[i-4]&ENEMY && !tb[i-8] && tb[i+4]) n->threat++;
    if (tb[i-5]&ENEMY && !tb[i-10] && tb[i+5]) n->threat++;
    break;
  }

  int gradient[40];
  for (i=4; i<9; i++) gradient[i] = tb[i] ? 0 : 32;
  int total = 0;
  for (i=9; i<40; i++) {
    int x = (gradient[i-4]+gradient[i-5])/2;
    if (tb[i]==FRIEND) total += x;
    gradient[i] = (tb[i]&FRIEND || !tb[i] && !is_protected[i]) ? x : 0;
  }
  n->gradient = total;

  n->back = tb[39]==FRIEND && tb[37]==FRIEND && !enemykings;

  node* f = n->father;

  n->moc2 = f->mobil>n->mobil && friendcent>enemycent;
  n->moc3 = f->mobil<=n->mobil && friendcent<enemycent;
  n->moc4 = f->mobil>n->mobil && friendcent<enemycent;
  n->mode2 = f->mobil<=n->mobil && n->deny<f->deny;
  n->mode3 = f->mobil>n->mobil && n->deny>f->deny;
  n->demmo = n->deny>f->deny && f->deny+f->mobil>n->deny+n->mobil;

  total =
    spiece	* (friendpieces - enemypieces) +
    (sking-spiece) * (friendkings	- enemykings) +
    //	mobil?
    sdeny	* (n->deny	- f->deny) +
    spin	* (n->pin	- f->pin) +
    sthreat	* (n->threat	- f->threat) +
    sgrad	* (n->gradient	- f->gradient) +
    sback	* (n->back	- f->back) +
    smoc2	* (n->moc2	- f->moc2) +
    smoc3	* (n->moc3	- f->moc3) +
    smoc4	* (n->moc4	- f->moc4) +
    smode2	* (n->mode2	- f->mode2) +
    smode3	* (n->mode3	- f->mode3) +
    sdemmo	* (n->demmo	- f->demmo) +
    scent	* (friendcent	- enemycent) +
    (skcent-scent) * (friendkcent	- enemykcent);
  if (!n->mobil) total += sallpin;

  if (!enemypieces) total = 30000;
  else if (friendpieces > enemypieces)
    total += (sadvan*friendpieces)/enemypieces-sadvan;
  else total -= (sadvan*enemypieces)/friendpieces-sadvan;

  if (print) {
    printf("\tParent\tNew\tScore\n");
    printf("pieces\t%d\t%d\t%d\n",enemypieces,friendpieces,
	   spiece*(friendpieces-enemypieces));
    printf("kings\t%d\t%d\t%d\n",enemykings,friendkings,
	   (sking-spiece)*(friendkings-enemykings));
    printf("mobil\t%d\t%d\n",f->mobil,n->mobil);
    printf("deny\t%d\t%d\t%d\n",f->deny,n->deny,sdeny*(n->deny-f->deny));
    printf("pin\t%d\t%d\t%d\n",f->pin,n->pin,spin*(n->pin-f->pin));
    printf("threat\t%d\t%d\t%d\n",f->threat,n->threat,sthreat*(n->threat-f->threat));
    printf("grad\t%d\t%d\t%d\n",f->gradient,n->gradient,sgrad*(n->gradient-f->gradient));
    printf("back\t%d\t%d\t%d\n",f->back,n->back,sback*(n->back-f->back));
    printf("moc2\t%d\t%d\t%d\n",f->moc2,n->moc2,smoc2*(n->moc2-f->moc2));
    printf("moc3\t%d\t%d\t%d\n",f->moc3,n->moc3,smoc3*(n->moc3-f->moc3));
    printf("moc4\t%d\t%d\t%d\n",f->moc4,n->moc4,smoc4*(n->moc4-f->moc4));
    printf("mode2\t%d\t%d\t%d\n",f->mode2,n->mode2,smode2*(n->mode2-f->mode2));
    printf("mode3\t%d\t%d\t%d\n",f->mode3,n->mode3,smode3*(n->mode3-f->mode3));
    printf("demmo\t%d\t%d\t%d\n",f->demmo,n->demmo,sdemmo*(n->demmo-f->demmo));
    printf("cent\t%d\t%d\t%dn",enemycent,friendcent,scent*(friendcent-enemycent));
    printf("kcent\t%d\t%d\t%d\n",enemykcent,friendkcent,skcent*(friendkcent-enemykcent));
    printf("total:\t\t\t%d\n",total);
  }
  else {
    n->value = total;
    evaluated++;
  }
}	// end of evaluateboard

// --------------------- Tree management -----------------

node *freelist;

node *newnode(void) {
  node *n;
  if (freelist) {
    n = freelist;
    freelist = n->brother;
  }
  else n = (node *)malloc(sizeof(node));
  memset(n,0,sizeof(node));
  nodes++;
  return(n);
}

void extract(node *n) {
  node* i = n->father;
  if (i) {
    node* j = i->son;
    if (j==n) i->son = n->brother;
    else while (j) {
      i = j; j = j->brother;
      if (j==n) {i->brother = n->brother; break;}
    }
  }
  n->brother = 0;
}

void killnode(node *x) {
  if (!x) return;
  node *y;
  for (y = x; ; y = y->brother) {
    nodes--;
    killnode(y->son); y->son = 0;
    if (!y->brother) break;
  }
  y->brother = freelist;
  freelist = x;
}

int seed;		// current random number

void insert(node *n) {
  int val = n->value;
  node **pp;
  for (pp = &(n->father->son); *pp; pp = &((*pp)->brother)) {
    int val1 = (*pp)->value;
    if (abs(val-val1) <= noise) {
      seed = (seed*13077+5051)%0100000;
      if ((seed & 070) >= 060) break;
    }
    else if (val > val1) break;
  }
  n->brother = *pp;
  *pp = n;
}

// --------------------------------------------------------------

void movepiece(node* f, int i, node* jnode) {
  static char jumphappened;

  for (int k=0; k<4; k++) {
    int direction = offset[b[i]][k];
    if (!direction) break;
    int j = i+direction;
    if (b[j] == EMPTY) {
      if (!jnode && (!forcejumps || !f->son || !f->son->jump)) {
	node* n = newnode();
	n->father = f;
	n->who = !f->who;
	n->from = i;
	n->to = j;
	piece oldpiece = b[i]; b[i] = EMPTY;
	if (!(oldpiece&KING) && n->who ? (j>=36) : (j<=8)) {
	  n->king = 1;
	  b[j] = oldpiece|KING;
	}
	else b[j] = oldpiece;
	evaluateboard(n,0);
	insert(n);
	b[i] = oldpiece; b[j] = EMPTY;
      }
    } else if (((b[j]^b[i])&(CWHITE|CBLACK))==(CWHITE|CBLACK) && !b[j+direction]) {
      if (forcejumps && f->son && !f->son->jump) {
	killnode(f->son);
	f->son = 0;
      }
      int jumploc = j;
      j += direction;
      node* n = newnode();
      n->father = f;
      n->who = !f->who;
      n->from = i;
      n->to = j;
      n->jump = (1<<(jumploc-10));
      piece oldpiece = b[i]; b[i] = EMPTY;
      if (!(oldpiece&KING) && n->who ? (j>=36) : (j<=8)) {
	n->king = 1;
	b[j] = oldpiece|KING;
      }
      else b[j] = oldpiece;
      if (jnode) {
	n->from = jnode->from;