non
/
ntk
mirror of https://github.com/original-male/ntk
1
0
Fork 0
Code Releases 2 Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
166 Commits
1 Branch
8.9MB
Branch: master
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
ntk/test/checkers.cxx

1372 lines
36KB
Raw Permalink Blame History 

  1. //

  2. // "$Id: checkers.cxx 8168 2011-01-02 03:55:23Z matt $"

  3. //

  4. // Checkers game for the Fast Light Tool Kit (FLTK).

  5. //

  6. // Hours of fun: the FLTK checkers game!

  7. // Based on a very old algorithm, but it still works!

  8. //

  9. // Copyright 1998-2010 by Bill Spitzak and others.

  10. //

  11. // This library is free software; you can redistribute it and/or

  12. // modify it under the terms of the GNU Library General Public

  13. // License as published by the Free Software Foundation; either

  14. // version 2 of the License, or (at your option) any later version.

  15. //

  16. // This library is distributed in the hope that it will be useful,

  17. // but WITHOUT ANY WARRANTY; without even the implied warranty of

  18. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

  19. // Library General Public License for more details.

  20. //

  21. // You should have received a copy of the GNU Library General Public

  22. // License along with this library; if not, write to the Free Software

  23. // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307

  24. // USA.

  25. //

  26. // Please report all bugs and problems on the following page:

  27. //

  28. //     http://www.fltk.org/str.php

  29. //

  30. 

  31. const char* copyright = 

  32. "Checkers game\n"

  33. "Copyright (C) 1997-2010 Bill Spitzak    spitzak@d2.com\n"

  34. "Original Pascal code:\n"

  35. "Copyright 1978, Oregon Minicomputer Software, Inc.\n"

  36. "2340 SW Canyon Road, Portland, Oregon 97201\n"

  37. "Written by Steve Poulsen 18-Jan-79\n"

  38. "\n"

  39. "This program is free software; you can redistribute it and/or modify "

  40. "it under the terms of the GNU General Public License as published by "

  41. "the Free Software Foundation; either version 2 of the License, or "

  42. "(at your option) any later version.\n"

  43. "\n"

  44. "This program is distributed in the hope that it will be useful, "

  45. "but WITHOUT ANY WARRANTY; without even the implied warranty of "

  46. "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the "

  47. "GNU General Public License for more details.\n"

  48. "\n"

  49. "You should have received a copy of the GNU Library General Public "

  50. "License along with this library; if not, write to the Free Software "

  51. "Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 "

  52. "USA.";

  53. 

  54. // Define FLTK to get the fltk interface

  55. // Define VT100 to get the VT100 interface

  56. // Define both to get a program that takes a -t switch

  57. 

  58. #define FLTK

  59. //#define VT100

  60. 

  61. #undef check

  62. 

  63. #include <string.h>

  64. #include <stdlib.h>

  65. #include <stdio.h>

  66. #include <stdarg.h>

  67. #include <time.h>

  68. 

  69. #ifdef VT100

  70. #include <ctype.h>	// toupper

  71. #endif

  72. 

  73. ////////////////////////////////////////////////////////////////

  74. // The algorithim:

  75. 

  76. int maxevaluate=2500;		// max number of moves to examine on a turn

  77. int maxnodes = 2500;		// maximum number of nodes in search tree

  78. int maxply = 20;		// maximum depth to look ahead

  79. char forcejumps = 1;		// is forced jumps rule in effect?

  80. 

  81. // scoring parameters: (all divided by 5 from original code)

  82. // some signs seem to be backwards, marked them with (-) in comment

  83. const int spiece = 800;		// value of a piece

  84. const int sking = 1200;		// value of a king

  85. const int sadvan = 160;		// value of mypieces/theirpieces-1

  86. // const int smobil = ?		// moves *enemy* can make w/o being jumped

  87. const int sallpin = 80;		// mobil == 0

  88. const int sdeny = 10;		// moves enemy can make that will be jumped

  89. const int spin = 32;		// enemy pieces that have no move except jumped

  90. const int sthreat = -10;	// enemy pieces we can jump if not moved (-)

  91. const int sgrad = 1;		// score of piece positions

  92. const int sback = 10;		// back row occupied so enemy can't make king

  93. const int smoc2 = 200;		// more mobility, more center

  94. const int smoc3 = -8;		// less mobility, less center

  95. const int smoc4 = -80;		// more mobility, less center

  96. const int smode2 = -14;		// less mobility, less denied

  97. const int smode3 = -40;		// more mobility, more denied (-)

  98. const int sdemmo = -20;		// more denied, more moves (-)

  99. const int scent = 10;		// pieces in center

  100. const int skcent = 100;		// kings in center

  101. 

  102. const int depthpenalty=4;	// guess

  103. const int noise=2;		// values less or eq to this apart are eq

  104. 

  105. // const int sattackking = 4;	// not used

  106. // const int sattackpiece = 3;

  107. 

  108. struct node {

  109.   node *father;

  110.   node *son;		// best son

  111.   node *brother;	// next brother

  112.   short int value;	// value of this board position to player making move

  113.   unsigned char from,to; // the move to reach this board

  114.   long int jump;	// bit map of locations jumped

  115.   unsigned char mobil;

  116.   unsigned char deny;

  117.   unsigned char pin;

  118.   unsigned char threat;

  119.   short int gradient;

  120.   unsigned who:1;	// 0 = black's move, 1 = white's move

  121.   unsigned king:1;	// 1 = move causes piece to be kinged

  122.   unsigned back:1;

  123.   unsigned moc2:1;

  124.   unsigned moc3:1;

  125.   unsigned moc4:1;

  126.   unsigned mode2:1;

  127.   unsigned mode3:1;

  128.   unsigned demmo:1;

  129. };

  130. 

  131. int nodes;		// count of nodes

  132. 

  133. /*	Board positions:	Border positions:

  134. 

  135. 	      WHITE		  00  01  02  03  04

  136. 	  05  06  07  08	04  XX  XX  XX  XX

  137. 	09  10  11  12		  XX  XX  XX  XX  13

  138. 	  14  15  16  17	13  XX  XX  XX  XX

  139. 	18  19  20  21		  XX  XX  XX  XX  22

  140. 	  23  24  25  26	22  XX  XX  XX  XX

  141. 	27  28  29  30		  XX  XX  XX  XX  31

  142. 	  32  33  34  36	31  XX  XX  XX  XX

  143. 	36  37  38  39		  XX  XX  XX  XX  40

  144. 	      BLACK		40  41  42  43  44

  145. 

  146. */

  147. 

  148. typedef char piece;

  149. 

  150. // Piece values so that BLACK and WHITE are bit flags:

  151. #define EMPTY 0

  152. #define BLACK 1

  153. #define WHITE 2

  154. #define KING 4

  155. #define BLACKKING 5

  156. #define WHITEKING 6

  157. #define BLUE 8

  158. 

  159. const piece flip[9] = {

  160.   EMPTY, WHITE, BLACK, 0, 0, WHITEKING, BLACKKING, 0, BLUE};

  161. 

  162. const int offset[9][4] = {	// legal move directions

  163.   {0,0,0,0},

  164.   {-5,-4,0,0},

  165.   {4,5,0,0},

  166.   {0,0,0,0},

  167.   {0,0,0,0},

  168.   {4,5,-4,-5},

  169.   {4,5,-4,-5},

  170.   {0,0,0,0},

  171.   {0,0,0,0}

  172. };

  173. 

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

  175. 

  176. int evaluated;		// number of moves evaluated this turn

  177. 

  178. char centralsquares[45];

  179. char is_protected[45];

  180. 

  181. piece flipboard[45];	// swapped if enemy is black

  182. piece *tb;		// pointer to real or swapped board

  183. #define FRIEND BLACK

  184. #define FRIENDKING BLACKKING

  185. #define ENEMY WHITE

  186. #define ENEMYKING WHITEKING

  187. 

  188. char check(int target,int direction) {

  189.   // see if enemy at target can be jumped from direction by our piece

  190.   int dst = target-direction;

  191.   if (tb[dst]) return(0);

  192.   int src = target+direction;

  193.   if (tb[src] == FRIENDKING);

  194.   else if (direction < 0 || tb[src] != FRIEND) return(0);

  195.   piece aa = tb[target]; piece bb = tb[src];

  196.   tb[target] = EMPTY; tb[src] = EMPTY;

  197.   int safe =

  198.     (   (tb[src-4]&FRIEND && tb[src-8]&ENEMY)

  199.      || (tb[src-5]&FRIEND && tb[src-10]&ENEMY)

  200.      || (tb[dst-4]&ENEMY && !tb[dst+4])

  201.      || (tb[dst-5]&ENEMY && !tb[dst+5])

  202.      || (tb[src+4]&FRIEND && tb[src+8]==ENEMYKING)

  203.      || (tb[src+5]&FRIEND && tb[src+10]==ENEMYKING)

  204.      || (tb[dst+4]==ENEMYKING && !tb[dst-4])

  205.      || (tb[dst+5]==ENEMYKING && !tb[dst-5]));

  206.   tb[target] = aa; tb[src] = bb;

  207.   return(safe);

  208. }

  209. 

  210. int deniedmoves,undeniedmoves;

  211. void analyzemove(int direction,int src) {

  212.   int target = src+direction;

  213.   if (!tb[target]) {

  214.     if (!tb[target+direction]) is_protected[target] = 1;

  215.     piece a = tb[src]; tb[src] = EMPTY;

  216.     if (check(target,4) || check(target,5) ||

  217. 	check(target,-4) || check(target,-5) ||

  218. 	(tb[src+4]&ENEMY && check(src+4,4)) ||

  219. 	(tb[src+5]&ENEMY && check(src+5,5)) ||

  220. 	(tb[src-4]&ENEMY && check(src-4,-4)) ||

  221. 	(tb[src-5]&ENEMY && check(src-5,-5)))

  222.       deniedmoves++;

  223.     else undeniedmoves++;

  224.     tb[src] = a;

  225.   }

  226. }

  227. 

  228. void evaluateboard(node *n,int print) {

  229. 

  230.   if (!n->who) tb = b;	// move was black's

  231.   else {

  232.     for (int i=0; i<45; i++) flipboard[44-i] = flip[(int)b[i]];

  233.     tb = flipboard;

  234.   }

  235. 

  236.   memset(is_protected,0,sizeof(is_protected));

  237.   int friendpieces = 0;

  238.   int enemypieces = 0;

  239.   int friendkings = 0;

  240.   int enemykings = 0;

  241.   int friendkcent = 0;

  242.   int friendcent = 0;

  243.   int enemykcent = 0;

  244.   int enemycent = 0;

  245.   n->mobil = n->deny = n->pin = n->threat = 0;

  246. 

  247.   int i;

  248.   for (i=5; i<40; i++) switch(tb[i]) {

  249.   case ENEMYKING:

  250.     enemykings++;

  251.     enemykcent += centralsquares[i];

  252.     deniedmoves = 0;

  253.     undeniedmoves = 0;

  254.     if (i>8) {

  255.       analyzemove(-4,i);

  256.       analyzemove(-5,i);

  257.     }

  258.     goto J1;

  259.   case ENEMY:

  260.     deniedmoves = 0;

  261.     undeniedmoves = 0;

  262.   J1:	enemypieces++;

  263.     enemycent += centralsquares[i];

  264.     if (i<36) {

  265.       analyzemove(4,i);

  266.       analyzemove(5,i);

  267.     }

  268.     if (deniedmoves && !undeniedmoves) n->pin++;

  269.     n->deny += deniedmoves;

  270.     n->mobil += undeniedmoves;

  271.     break;

  272.   case FRIENDKING:

  273.     friendkings++;

  274.     friendkcent += centralsquares[i];

  275.     if (tb[i+4]&ENEMY && !tb[i+8] && !(tb[i+4]==ENEMYKING && !tb[i-4]))

  276.       n->threat++;

  277.     if (tb[i+5]&ENEMY && !tb[i+10] && !(tb[i+5]==ENEMYKING && !tb[i-5]))

  278.       n->threat++;

  279.   case FRIEND:

  280.     friendpieces++;

  281.     friendcent += centralsquares[i];

  282.     if (tb[i-4]&ENEMY && !tb[i-8] && tb[i+4]) n->threat++;

  283.     if (tb[i-5]&ENEMY && !tb[i-10] && tb[i+5]) n->threat++;

  284.     break;

  285.   }

  286. 

  287.   int gradient[40];

  288.   for (i=4; i<9; i++) gradient[i] = tb[i] ? 0 : 32;

  289.   int total = 0;

  290.   for (i=9; i<40; i++) {

  291.     int x = (gradient[i-4]+gradient[i-5])/2;

  292.     if (tb[i]==FRIEND) total += x;

  293.     gradient[i] = (tb[i]&FRIEND || (!tb[i] && !is_protected[i])) ? x : 0;

  294.   }

  295.   n->gradient = total;

  296. 

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

  298. 

  299.   node* f = n->father;

  300. 

  301.   n->moc2 = f->mobil>n->mobil && friendcent>enemycent;

  302.   n->moc3 = f->mobil<=n->mobil && friendcent<enemycent;

  303.   n->moc4 = f->mobil>n->mobil && friendcent<enemycent;

  304.   n->mode2 = f->mobil<=n->mobil && n->deny<f->deny;

  305.   n->mode3 = f->mobil>n->mobil && n->deny>f->deny;

  306.   n->demmo = n->deny>f->deny && f->deny+f->mobil>n->deny+n->mobil;

  307. 

  308.   total =

  309.     spiece	* (friendpieces - enemypieces) +

  310.     (sking-spiece) * (friendkings	- enemykings) +

  311.     //	mobil?

  312.     sdeny	* (n->deny	- f->deny) +

  313.     spin	* (n->pin	- f->pin) +

  314.     sthreat	* (n->threat	- f->threat) +

  315.     sgrad	* (n->gradient	- f->gradient) +

  316.     sback	* (n->back	- f->back) +

  317.     smoc2	* (n->moc2	- f->moc2) +

  318.     smoc3	* (n->moc3	- f->moc3) +

  319.     smoc4	* (n->moc4	- f->moc4) +

  320.     smode2	* (n->mode2	- f->mode2) +

  321.     smode3	* (n->mode3	- f->mode3) +

  322.     sdemmo	* (n->demmo	- f->demmo) +

  323.     scent	* (friendcent	- enemycent) +

  324.     (skcent-scent) * (friendkcent	- enemykcent);

  325.   if (!n->mobil) total += sallpin;

  326. 

  327.   if (!enemypieces) total = 30000;

  328.   else if (friendpieces > enemypieces)

  329.     total += (sadvan*friendpieces)/enemypieces-sadvan;

  330.   else total -= (sadvan*enemypieces)/friendpieces-sadvan;

  331. 

  332.   if (print) {

  333.     printf("\tParent\tNew\tScore\n");

  334.     printf("pieces\t%d\t%d\t%d\n",enemypieces,friendpieces,

  335. 	   spiece*(friendpieces-enemypieces));

  336.     printf("kings\t%d\t%d\t%d\n",enemykings,friendkings,

  337. 	   (sking-spiece)*(friendkings-enemykings));

  338.     printf("mobil\t%d\t%d\n",f->mobil,n->mobil);

  339.     printf("deny\t%d\t%d\t%d\n",f->deny,n->deny,sdeny*(n->deny-f->deny));

  340.     printf("pin\t%d\t%d\t%d\n",f->pin,n->pin,spin*(n->pin-f->pin));

  341.     printf("threat\t%d\t%d\t%d\n",f->threat,n->threat,sthreat*(n->threat-f->threat));

  342.     printf("grad\t%d\t%d\t%d\n",f->gradient,n->gradient,sgrad*(n->gradient-f->gradient));

  343.     printf("back\t%d\t%d\t%d\n",f->back,n->back,sback*(n->back-f->back));

  344.     printf("moc2\t%d\t%d\t%d\n",f->moc2,n->moc2,smoc2*(n->moc2-f->moc2));

  345.     printf("moc3\t%d\t%d\t%d\n",f->moc3,n->moc3,smoc3*(n->moc3-f->moc3));

  346.     printf("moc4\t%d\t%d\t%d\n",f->moc4,n->moc4,smoc4*(n->moc4-f->moc4));

  347.     printf("mode2\t%d\t%d\t%d\n",f->mode2,n->mode2,smode2*(n->mode2-f->mode2));

  348.     printf("mode3\t%d\t%d\t%d\n",f->mode3,n->mode3,smode3*(n->mode3-f->mode3));

  349.     printf("demmo\t%d\t%d\t%d\n",f->demmo,n->demmo,sdemmo*(n->demmo-f->demmo));

  350.     printf("cent\t%d\t%d\t%dn",enemycent,friendcent,scent*(friendcent-enemycent));

  351.     printf("kcent\t%d\t%d\t%d\n",enemykcent,friendkcent,skcent*(friendkcent-enemykcent));

  352.     printf("total:\t\t\t%d\n",total);

  353.   }

  354.   else {

  355.     n->value = total;

  356.     evaluated++;

  357.   }

  358. }	// end of evaluateboard

  359. 

  360. // --------------------- Tree management -----------------

  361. 

  362. node *freelist;

  363. 

  364. node *newnode(void) {

  365.   node *n;

  366.   if (freelist) {

  367.     n = freelist;

  368.     freelist = n->brother;

  369.   }

  370.   else n = (node *)malloc(sizeof(node));

  371.   memset(n,0,sizeof(node));

  372.   nodes++;

  373.   return(n);

  374. }

  375. 

  376. void extract(node *n) {

  377.   node* i = n->father;

  378.   if (i) {

  379.     node* j = i->son;

  380.     if (j==n) i->son = n->brother;

  381.     else while (j) {

  382.       i = j; j = j->brother;

  383.       if (j==n) {i->brother = n->brother; break;}

  384.     }

  385.   }

  386.   n->brother = 0;

  387. }

  388. 

  389. void killnode(node *x) {

  390.   if (!x) return;

  391.   node *y;

  392.   for (y = x; ; y = y->brother) {

  393.     nodes--;

  394.     killnode(y->son); y->son = 0;

  395.     if (!y->brother) break;

  396.   }

  397.   y->brother = freelist;

  398.   freelist = x;

  399. }

  400. 

  401. int seed;		// current random number

  402. 

  403. void insert(node *n) {

  404.   int val = n->value;

  405.   node **pp;

  406.   for (pp = &(n->father->son); *pp; pp = &((*pp)->brother)) {

  407.     int val1 = (*pp)->value;

  408.     if (abs(val-val1) <= noise) {

  409.       seed = (seed*13077+5051)%0100000;

  410.       if ((seed & 070) >= 060) break;

  411.     }

  412.     else if (val > val1) break;

  413.   }

  414.   n->brother = *pp;

  415.   *pp = n;

  416. }

  417. 

  418. // --------------------------------------------------------------

  419. 

  420. void movepiece(node* f, int i, node* jnode) {

  421.   static char jumphappened;

  422. 

  423.   for (int k=0; k<4; k++) {

  424.     int direction = offset[(int)b[i]][k];

  425.     if (!direction) break;

  426.     int j = i+direction;

  427.     if (b[j] == EMPTY) {

  428.       if (!jnode && (!forcejumps || !f->son || !f->son->jump)) {

  429. 	node* n = newnode();

  430. 	n->father = f;

  431. 	n->who = !f->who;

  432. 	n->from = i;

  433. 	n->to = j;

  434. 	piece oldpiece = b[i]; b[i] = EMPTY;

  435. 	if (!(oldpiece&KING) && n->who ? (j>=36) : (j<=8)) {

  436. 	  n->king = 1;

  437. 	  b[j] = oldpiece|KING;

  438. 	}

  439. 	else b[j] = oldpiece;

  440. 	evaluateboard(n,0);

  441. 	insert(n);

  442. 	b[i] = oldpiece; b[j] = EMPTY;

  443.       }

  444.     } else if (((b[j]^b[i])&(WHITE|BLACK))==(WHITE|BLACK) && !b[j+direction]) {

  445.       if (forcejumps && f->son && !f->son->jump) {

  446. 	killnode(f->son);

  447. 	f->son = 0;

  448.       }

  449.       int jumploc = j;

  450.       j += direction;

  451.       node* n = newnode();

  452.       n->father = f;

  453.       n->who = !f->who;

  454.       n->from = i;

  455.       n->to = j;

  456.       n->jump = (1<<(jumploc-10));

  457.       piece oldpiece = b[i]; b[i] = EMPTY;

  458.       if (!(oldpiece&KING) && n->who ? (j>=36) : (j<=8)) {

  459. 	n->king = 1;

  460. 	b[j] = oldpiece|KING;

  461.       }

  462.       else b[j] = oldpiece;

  463.       if (jnode) {

  464. 	n->from = jnode->from;

  465. 	n->jump |= jnode->jump;

  466. 	n->king |= jnode->king;

  467.       }

  468.       piece jumpedpiece = b[jumploc];

  469.       b[jumploc] = EMPTY;

  470.       jumphappened = 0;

  471.       movepiece(f,j,n);

  472.       if (forcejumps && jumphappened) killnode(n);

  473.       else {evaluateboard(n,0); insert(n);}

  474.       b[i] = oldpiece; b[j] = EMPTY;

  475.       b[jumploc] = jumpedpiece;

  476.       jumphappened = 1;

  477.     }

  478.   }

  479. }

  480. 

  481. void expandnode(node *f) {

  482.   if (f->son || f->value > 28000) return;	// already done

  483.   piece turn = f->who ? BLACK : WHITE;

  484.   for (int i=5; i<40; i++) if (b[i]&turn) movepiece(f,i,0);

  485.   if (f->son) {

  486.     f->value = -f->son->value;

  487.     if (f->brother) f->value -= depthpenalty;

  488.   }

  489.   else f->value = 30000;

  490. }

  491. 

  492. void makemove(node *n) {

  493.   b[n->to] = b[n->from];

  494.   if (n->king) b[n->to] |= KING;

  495.   b[n->from] = EMPTY;

  496.   if (n->jump) for(int i=0; i<32; i++) {

  497.     if (n->jump & (1<<i)) b[10+i] = EMPTY;

  498.   }

  499. }

  500. 

  501. int didabort(void);

  502. 

  503. int fullexpand(node *f, int level) {

  504.   if (didabort() || nodes > maxnodes-(maxply*10) || evaluated > maxevaluate) return(0);

  505.   expandnode(f);

  506.   if (!f->son) return(1);

  507.   piece oldboard[45];

  508.   memmove(oldboard,b,sizeof(b));

  509.   node* n = f->son;

  510.   if (!n->jump && n->brother) {if (level<1) return(1); level--;}

  511.   int i;

  512.   node* sons[32]; for (i=0; (sons[i++] = n); n = n->brother);

  513.   int ret = 1;

  514.   for (i=0; ret && (n = sons[i++]);) {

  515.     makemove(n);

  516.     ret = fullexpand(n,level);

  517.     memmove(b,oldboard,sizeof(b));

  518.     extract(n);

  519.     insert(n);

  520.   }

  521.   f->value = -f->son->value;

  522.   return(ret);

  523. }

  524. 

  525. int descend(node *f) {

  526.   static int depth;

  527.   if (didabort() || nodes > maxnodes || depth >= maxply) return(0);

  528.   if (f->son) {

  529.     node* n = f->son;

  530.     makemove(n);

  531.     depth++;

  532.     int ret = descend(n);

  533.     depth--;

  534.     extract(n);

  535.     insert(n);

  536.     f->value = -f->son->value;

  537.     return(ret);

  538.   }

  539.   else {expandnode(f); return(1);}

  540. }

  541. 

  542. char debug;

  543. 

  544. node *calcmove(node *root) {	// return best move after root

  545.   expandnode(root);

  546.   if (!root->son) return(0);	// no move due to loss

  547.   if (debug) printf("calcmove() initial nodes = %d\n",nodes);

  548.   evaluated = 0;

  549.   if (root->son->brother) {

  550.     int x;

  551.     for (x = 1; abs(root->value)<28000 && fullexpand(root,x); x++);

  552.     piece saveboard[45]; memmove(saveboard,b,sizeof(b));

  553.     while (abs(root->value)<28000) {

  554.       x = descend(root);

  555.       memmove(b,saveboard,sizeof(b));

  556.       if (!x) break;

  557.     }

  558.   }

  559.   if (debug) printf(" evaluated %d, nodes = %d\n", evaluated, nodes);

  560.   return(root->son);

  561. }

  562. 

  563. // the actual game state ----------------

  564. 

  565. node *root,*undoroot;

  566. 

  567. piece jumpboards[24][45];	// saved boards for undoing jumps

  568. int nextjump;

  569. 

  570. char user;	// 0 = black, 1 = white

  571. char playing;

  572. char autoplay;

  573. 

  574. void newgame(void) {

  575. 

  576.   int n;

  577.   for (n=0; n<5; n++) b[n] = BLUE;

  578.   for (n=5; n<18; n++) b[n] = WHITE;

  579.   for (n=18; n<27; n++) b[n] = EMPTY;

  580.   for (n=27; n<40; n++) b[n] = BLACK;

  581.   for (n=40; n<45; n++) b[n] = BLUE;

  582.   b[13] = b[22] = b[31] = BLUE;

  583. 

  584.   centralsquares[15] = centralsquares[16] =

  585.     centralsquares[19] = centralsquares[20] =

  586.     centralsquares[24] = centralsquares[25] =

  587.     centralsquares[28] = centralsquares[29] = 1;

  588. 

  589.   // set up initial search tree:

  590.   nextjump = 0;

  591.   killnode(undoroot);

  592.   undoroot = root = newnode();

  593. 

  594.   // make it white's move, so first move is black:

  595.   root->who = 1;

  596.   user = 0;

  597.   playing = 1;

  598. }

  599. 

  600. void domove(node* move) {

  601.   if (move->jump) memmove(jumpboards[nextjump++],b,sizeof(b));

  602.   makemove(move);

  603.   extract(move);

  604.   killnode(root->son);

  605.   root->son = move;

  606.   root = move;

  607.   if (debug) evaluateboard(move,1);

  608. }

  609. 

  610. node* undomove() {

  611.   node *n = root;

  612.   if (n == undoroot) return 0; // no more undo possible

  613.   if (n->jump) memmove(b,jumpboards[--nextjump],sizeof(b));

  614.   else {

  615.     b[n->from] = b[n->to];

  616.     if (n->king) b[n->from] &= (WHITE|BLACK);

  617.     b[n->to] = EMPTY;

  618.   }

  619.   root = n->father;

  620.   killnode(n);

  621.   root->son = 0;

  622.   root->value = 0;	// prevent it from thinking game is over

  623.   playing = 1;

  624.   if (root == undoroot) user = 0;

  625.   return n;

  626. }

  627. 

  628. const char _usermoves[] =

  629. "B1D1F1H1A2C2E2G2??B3D3F3H3A4C4E4G4??B5D5F5H5A6C6E6G6??B7D7F7H7A8C8E8G8??";

  630. #define usermoves(x,y) _usermoves[2*((x)-5)+(y)-1]

  631. 

  632. void dumpnode(node *n, int help) {

  633.   int x = n->from;

  634.   int y = n->to;

  635.   if (help) printf("%c%c %c%c\t- ",

  636. 		   usermoves(x,1),usermoves(x,2),

  637. 		   usermoves(y,1),usermoves(y,2));

  638.   printf("%s %ss from %c%c to %c%c",

  639. 	 n->who ? "White" : "Black",

  640. 	 n->jump ? "jump" : "move",

  641. 	 usermoves(x,1),usermoves(x,2),

  642. 	 usermoves(y,1),usermoves(y,2));

  643.   if (n->jump) {

  644.     for (int i=0; i<32; i++) if (n->jump & (1<<i))

  645.       printf(", %c%c",usermoves(10+i,1),usermoves(10+i,2));

  646.     printf(" removed");

  647.   }

  648.   printf(" (%+d).\n",n->value);

  649. }

  650. 

  651. int abortflag;

  652. 

  653. ////////////////////////////////////////////////////////////////

  654. // VT100 Interface:

  655. #ifdef VT100

  656. 

  657. void positioncursor(int i) {

  658.   printf("\033[%d;%dH",

  659. 	 usermoves(i,2)-'0'+1,

  660. 	 2*(usermoves(i,1)-'A')+1);

  661. }

  662. 

  663. void outpiecename(piece n) {

  664.   printf(n&BLACK ? "\033[1;7m" : "\033[1m");

  665.   putchar(" BW??BW??"[n]);

  666.   putchar(" BW??KK??"[n]);

  667.   printf("\033[0m");

  668. }

  669. 

  670. void VT100board(void) {

  671.   printf("\033<\033[H\033[J\033[10r");

  672.   int l = 0;

  673.   puts(" A B C D E F G H");

  674.   for (int i=0; i<4; i++) {

  675.     int j = 9*i+5;

  676.     int k;

  677.     for (k=0; k<4; k++) {

  678.       printf("\033[7m  \033[0m");

  679.       outpiecename(b[j+k]);

  680.     }

  681.     l++;

  682.     printf("%d\n",l);

  683.     j += 4;

  684.     for (k=0; k<4; k++) {

  685.       outpiecename(b[j+k]);

  686.       printf("\033[7m  \033[0m");

  687.     }

  688.     l++;

  689.     printf("%d\n",l);

  690.   }

  691. }

  692. 

  693. void VT100move(node *n, int) {

  694.   if (!n) return;

  695.   printf("\0337");

  696.   positioncursor(n->from);

  697.   outpiecename(b[n->from]);

  698.   positioncursor(n->to);

  699.   outpiecename(b[n->to]);

  700.   if (n->jump) for(int i=0; i<32; i++) {

  701.     if (n->jump & (1<<i)) {

  702.       positioncursor(10+i);

  703.       outpiecename(b[10+i]);

  704.     }

  705.   }

  706.   printf("\0338");

  707. }

  708. 

  709. int decode(char *m) {

  710.   int i;

  711.   for(i=5; i<=40; i++)

  712.     if (toupper(m[0])==usermoves(i,1) && m[1]==usermoves(i,2)) return(i);

  713.   return(0);

  714. }

  715. 

  716. #include <signal.h>

  717. 

  718. static void sigint(...) {

  719.   abortflag = 1;

  720.   signal(SIGINT,sigint);

  721. }

  722. 

  723. void fixexit(int x) {

  724.   printf("\0337\033[r\0338");

  725.   exit(x);

  726. }

  727. 

  728. // Returns a son, or 0 if no move specified, or root to cause "help"

  729. node *getusermove(void) {

  730.   int i,j;

  731.   node *t;

  732.   char line[100],*m1,*m2;

  733. 

  734.   if (playing)

  735.     printf("\033[1m%s's move?\033[0m ",root->who ? "Black" : "White");

  736.   else

  737.     printf("\033[1mCommand?\033[0m ");

  738.   abortflag = 0;

  739.   if (!fgets(line, sizeof(line), stdin)) {

  740.     putchar('\n');

  741.     if (feof(stdin)) fixexit(0);

  742.     return 0;

  743.   }

  744.   for (m1 = line; *m1 && *m1<=' '; m1++);

  745.   if (!*m1) return(0);

  746.   m2 = m1+1;

  747.   if (*m2) m2++;

  748.   for (; *m2 && *m2<'0'; m2++);

  749.   if (playing && m1[1]>='0' && m1[1]<='9') {

  750.     i = decode(m1);

  751.     j = decode(m2);

  752.     if (i && j) for (t = root->son; t; t = t->brother)

  753.       if (t->from == i && t->to == j) return(t);

  754.     puts("Valid moves are:");

  755.     m1[0] = 'L';

  756.   }

  757.   switch(toupper(m1[0])) {

  758.   case 0: return(0);

  759.   case 'A':

  760.     if (playing) autoplay = 1;

  761.     return(root);

  762.   case 'C':

  763.     puts(copyright);

  764.     break;

  765.   case 'D':

  766.     debug = !debug;

  767.     printf("Debug is now %s.", debug ? "on" : "off");

  768.     break;

  769.   case 'F':

  770.     forcejumps = !forcejumps;

  771.     printf("Forced jumps rule is now %s.",forcejumps ? "on" : "off");

  772.     killnode(root->son); root->son = 0;

  773.     return(0);

  774.   case 'L':

  775.     expandnode(root);

  776.     if (playing) for (t = root->son; t; t = t->brother) dumpnode(t,1);

  777.     break;

  778.   case 'M':

  779.     return(playing ? root : 0);

  780.   case 'N':

  781.     newgame();

  782.     VT100board();

  783.     return(0);

  784.   case 'P':

  785.     printf("I expect the following moves:\n");

  786.     for (t = root->son; t; t = t->son) dumpnode(t,0);

  787.     break;

  788.   case 'Q':

  789.     fixexit(0);

  790.   case 'R':

  791.     VT100board();

  792.     break;

  793.   case 'S':

  794.     user = !user;

  795.     return(root);

  796.   case 'U':

  797.     VT100move(undomove(),1);

  798.     VT100move(undomove(),1);

  799.     return(0);

  800.   case '+':

  801.     maxevaluate = maxnodes = 2*maxevaluate;

  802.     goto J2;

  803.   case '-':

  804.     if (maxevaluate > 1)

  805.       maxevaluate = maxnodes = maxevaluate/2;

  806.   J2: printf("Moves evaluated set to %d.",maxevaluate);

  807.     break;

  808.   default:

  809.     puts(

  810. 	 "A(utoplay)\n"

  811. 	 "C(opyright)\n"

  812. 	 "D(ebug on/off)\n"

  813. 	 "F(orce jumps rule on/off)\n"

  814. 	 "L(ist legal moves)\n"

  815. 	 "M(ake a move for me)\n"

  816. 	 "N(ew game)\n"

  817. 	 "P(redict next few moves)\n"

  818. 	 "Q(uit)\n"

  819. 	 "R(edraw screen)\n"

  820. 	 "S(witch sides)\n"

  821. 	 "U(ndo)\n"

  822. 	 "+	- smarter\n"

  823. 	 "-	- stupider");

  824.     expandnode(root);

  825.     for (t = root->son; t; t = t->brother) dumpnode(t,1);

  826.   }

  827.   return(0);

  828. }

  829. 

  830. int VT100main() {

  831.   signal(SIGINT,sigint);

  832.   VT100board();

  833.   for (;;) {

  834.     if (playing) {

  835.       expandnode(root);

  836.       if (!root->son) {

  837. 	printf("%s has no move.  Game over.",root->who ? "Black" : "White");

  838. 	playing = autoplay = 0;

  839.       }

  840.     }

  841.     node* move;

  842.     if (playing && (autoplay || root->who == user)) {

  843.       move = calcmove(root);

  844.       if (move->value <= -30000) {

  845.  	printf("%s resigns.", move->who ? "White" : "Black");

  846.  	move = 0;

  847.  	playing = autoplay = 0;

  848.       }

  849.     } else {

  850.       move = getusermove();

  851.       if (move == root) move = calcmove(root);

  852.     }

  853.     if (move) {

  854.       dumpnode(move,0);

  855.       domove(move);

  856.       VT100move(move,0);

  857.     }

  858.   }

  859. }

  860. 

  861. #endif

  862. 

  863. ////////////////////////////////////////////////////////////////

  864. // fltk interface:

  865. #ifdef FLTK

  866. 

  867. #include <FL/Fl.H>

  868. #include <FL/Fl_Double_Window.H>

  869. #include <FL/Fl_Bitmap.H>

  870. #include <FL/fl_draw.H>

  871. #include <FL/Fl_Menu_Item.H>

  872. #include <FL/fl_ask.H>

  873. 

  874. //----------------------------------------------------------------

  875. // old 4-level NeXT images have been seperated into bitmaps so they

  876. // can be drawn with arbitrary colors and real transparency.  This is

  877. // rather tedious and perhaps fltk should provide a direct support

  878. // to do this:

  879. 

  880. #include "pixmaps/black_1.xbm"

  881. #include "pixmaps/black_2.xbm"

  882. #include "pixmaps/black_3.xbm"

  883. #include "pixmaps/black_4.xbm"

  884. #include "pixmaps/white_1.xbm"

  885. #include "pixmaps/white_2.xbm"

  886. #include "pixmaps/white_3.xbm"

  887. #include "pixmaps/white_4.xbm"

  888. #include "pixmaps/blackking_1.xbm"

  889. #include "pixmaps/blackking_2.xbm"

  890. #include "pixmaps/blackking_3.xbm"

  891. #include "pixmaps/blackking_4.xbm"

  892. #include "pixmaps/whiteking_1.xbm"

  893. #include "pixmaps/whiteking_2.xbm"

  894. #include "pixmaps/whiteking_3.xbm"

  895. #include "pixmaps/whiteking_4.xbm"

  896. 

  897. Fl_Bitmap *bm[4][4];

  898. 

  899. void make_bitmaps() {

  900.   if (bm[0][0]) return;

  901.   bm[0][0] = new Fl_Bitmap(black_1_bits, black_1_width, black_1_height);

  902.   bm[0][1] = new Fl_Bitmap(black_2_bits, black_1_width, black_1_height);

  903.   bm[0][2] = new Fl_Bitmap(black_3_bits, black_1_width, black_1_height);

  904.   bm[0][3] = new Fl_Bitmap(black_4_bits, black_1_width, black_1_height);

  905.   bm[1][0] = new Fl_Bitmap(white_1_bits, black_1_width, black_1_height);

  906.   bm[1][1] = new Fl_Bitmap(white_2_bits, black_1_width, black_1_height);

  907.   bm[1][2] = new Fl_Bitmap(white_3_bits, black_1_width, black_1_height);

  908.   bm[1][3] = new Fl_Bitmap(white_4_bits, black_1_width, black_1_height);

  909.   bm[2][0] = new Fl_Bitmap(blackking_1_bits, black_1_width, black_1_height);

  910.   bm[2][1] = new Fl_Bitmap(blackking_2_bits, black_1_width, black_1_height);

  911.   bm[2][2] = new Fl_Bitmap(blackking_3_bits, black_1_width, black_1_height);

  912.   bm[2][3] = new Fl_Bitmap(blackking_4_bits, black_1_width, black_1_height);

  913.   bm[3][0] = new Fl_Bitmap(whiteking_1_bits, black_1_width, black_1_height);

  914.   bm[3][1] = new Fl_Bitmap(whiteking_2_bits, black_1_width, black_1_height);

  915.   bm[3][2] = new Fl_Bitmap(whiteking_3_bits, black_1_width, black_1_height);

  916.   bm[3][3] = new Fl_Bitmap(whiteking_4_bits, black_1_width, black_1_height);

  917. }

  918. 

  919. #define ISIZE black_1_width

  920. 

  921. void draw_piece(int which, int x, int y) {

  922.   if (!fl_not_clipped(x,y,ISIZE,ISIZE)) return;

  923.   switch (which) {

  924.   case BLACK: which = 0; break;

  925.   case WHITE: which = 1; break;

  926.   case BLACKKING: which = 2; break;

  927.   case WHITEKING: which = 3; break;

  928.   default: return;

  929.   }

  930.   fl_color(FL_BLACK); bm[which][0]->draw(x, y);

  931.   fl_color(FL_INACTIVE_COLOR); bm[which][1]->draw(x, y);

  932.   fl_color(FL_SELECTION_COLOR); bm[which][2]->draw(x, y);

  933.   fl_color(FL_WHITE); bm[which][3]->draw(x, y);

  934. }

  935. 

  936. //----------------------------------------------------------------

  937. 

  938. class Board : public Fl_Double_Window {

  939.   void draw();

  940.   int handle(int);

  941. public:

  942.   void drag_piece(int, int, int);

  943.   void drop_piece(int);

  944.   void animate(node* move, int backwards);

  945.   void computer_move(int);

  946.   Board(int w, int h) : Fl_Double_Window(w,h) {color(15);}

  947. };

  948. 

  949. #define BOXSIZE 52

  950. #define BORDER 4

  951. #define BOARDSIZE (8*BOXSIZE+BORDER)

  952. #define BMOFFSET 5

  953. 

  954. static int erase_this;  // real location of dragging piece, don't draw it

  955. static int dragging;	// piece being dragged

  956. static int dragx;	// where it is

  957. static int dragy;

  958. static int showlegal;	// show legal moves

  959. 

  960. int squarex(int i) {return (usermoves(i,1)-'A')*BOXSIZE+BMOFFSET;}

  961. int squarey(int i) {return (usermoves(i,2)-'1')*BOXSIZE+BMOFFSET;}

  962. 

  963. void Board::draw() {

  964.   make_bitmaps();

  965.   // -- draw the board itself

  966.   fl_draw_box(box(),0,0,w(),h(),color());

  967.   // -- draw all dark tiles

  968.   fl_color((Fl_Color)10 /*107*/);

  969.   int x; for (x=0; x<8; x++) for (int y=0; y<8; y++) {

  970.     if (!((x^y)&1)) fl_rectf(BORDER+x*BOXSIZE, BORDER+y*BOXSIZE,

  971. 			     BOXSIZE-BORDER, BOXSIZE-BORDER);

  972.   }

  973.   // -- draw outlines around the fileds

  974.   fl_color(FL_DARK3);

  975.   for (x=0; x<9; x++) {

  976.     fl_rectf(x*BOXSIZE,0,BORDER,h());

  977.     fl_rectf(0,x*BOXSIZE,w(),BORDER);

  978.   }

  979.   for (int j = 5; j < 40; j++) if (j != erase_this) {

  980.     draw_piece(b[j], squarex(j), squarey(j));

  981.   }

  982.   if (showlegal) {

  983.     fl_color(FL_WHITE);

  984.     node* n;

  985.     for (n = root->son; n; n = showlegal==2 ? n->son : n->brother) {

  986.       int x1 = squarex(n->from)+BOXSIZE/2-5;

  987.       int y1 = squarey(n->from)+BOXSIZE/2-5;

  988.       int x2 = squarex(n->to)+BOXSIZE/2-5;

  989.       int y2 = squarey(n->to)+BOXSIZE/2-5;

  990.       fl_line(x1,y1,x2,y2);

  991.       fl_push_matrix();

  992.       fl_mult_matrix(x2-x1,y2-y1,y1-y2,x2-x1,x2,y2);

  993.       fl_begin_polygon();

  994.       fl_vertex(0,0);

  995.       fl_vertex(-.3, .1);

  996.       fl_vertex(-.3, -.1);

  997.       fl_end_polygon();

  998.       fl_pop_matrix();

  999.     }

  1000.     int num = 1;

  1001.     fl_color(FL_BLACK);

  1002.     fl_font(FL_BOLD,10);

  1003.     for (n = root->son; n; n = showlegal==2 ? n->son : n->brother) {

  1004.       int x1 = squarex(n->from)+BOXSIZE/2-5;

  1005.       int y1 = squarey(n->from)+BOXSIZE/2-5;

  1006.       int x2 = squarex(n->to)+BOXSIZE/2-5;

  1007.       int y2 = squarey(n->to)+BOXSIZE/2-5;

  1008.       char buf[20]; sprintf(buf,"%d",num);

  1009.       fl_draw(buf, x1+int((x2-x1)*.85)-3, y1+int((y2-y1)*.85)+5);

  1010.       num++;

  1011.     }

  1012.   }

  1013.   if (dragging) draw_piece(dragging, dragx, dragy);

  1014. }

  1015. 

  1016. // drag the piece on square i to dx dy, or undo drag if i is zero:

  1017. void Board::drag_piece(int j, int dx, int dy) {

  1018.   dy = (dy&-2) | (dx&1); // make halftone shadows line up

  1019.   if (j != erase_this) drop_piece(erase_this); // should not happen

  1020.   if (!erase_this) { // pick up old piece

  1021.     dragx = squarex(j); dragy = squarey(j);

  1022.     erase_this = j;

  1023.     dragging = b[j];

  1024.   }

  1025.   if (dx != dragx || dy != dragy) {

  1026.     damage(FL_DAMAGE_ALL, dragx, dragy, ISIZE, ISIZE);

  1027.     damage(FL_DAMAGE_ALL, dx, dy, ISIZE, ISIZE);

  1028.   }

  1029.   dragx = dx;

  1030.   dragy = dy;

  1031. }

  1032. 

  1033. // drop currently dragged piece on square i

  1034. void Board::drop_piece(int j) {

  1035.   if (!erase_this) return; // should not happen!

  1036.   erase_this = 0;

  1037.   dragging = 0;

  1038.   int x = squarex(j);

  1039.   int y = squarey(j);

  1040.   if (x != dragx || y != dragy) {

  1041.     damage(4, dragx, dragy, ISIZE, ISIZE);

  1042.     damage(4, x, y, ISIZE, ISIZE);

  1043.   }

  1044. }

  1045. 

  1046. // show move (call this *before* the move, *after* undo):

  1047. void Board::animate(node* move, int backwards) {

  1048.   if (showlegal) {showlegal = 0; redraw();}

  1049.   if (!move) return;

  1050.   int f = move->from;

  1051.   int t = move->to;

  1052.   if (backwards) {int x = f; f = t; t = x;}

  1053.   int x1 = squarex(f);

  1054.   int y1 = squarey(f);

  1055.   int x2 = squarex(t);

  1056.   int y2 = squarey(t);

  1057.   const int STEPS=35;

  1058.   for (int j=0; j<STEPS; j++) {

  1059.     int x = x1+(x2-x1)*j/STEPS;

  1060.     int y = y1+(y2-y1)*j/STEPS;

  1061.     drag_piece(move->from,x,y);

  1062.     Fl::flush();

  1063.   }

  1064.   drop_piece(t);

  1065.   if (move->jump) redraw();

  1066. }

  1067. 

  1068. int busy; // causes pop-up abort menu

  1069. 

  1070. void Board::computer_move(int help) {

  1071.   if (!playing) return;

  1072.   cursor(FL_CURSOR_WAIT);

  1073.   Fl::flush();

  1074.   busy = 1; abortflag = 0;

  1075.   node* move = calcmove(root);

  1076.   busy = 0;

  1077.   if (move) {

  1078.     if (!help && move->value <= -30000) {

  1079.       fl_message("%s resigns", move->who ? "White" : "Black");

  1080.       playing = autoplay = 0;

  1081.       cursor(FL_CURSOR_DEFAULT);

  1082.       return;

  1083.     }

  1084.     animate(move,0);

  1085.     domove(move);

  1086.   }

  1087.   expandnode(root);

  1088.   if (!root->son) {

  1089.     fl_message("%s has no move", root->who ? "Black" : "White");

  1090.     playing = autoplay = 0;

  1091.   }

  1092.   if (!autoplay) cursor(FL_CURSOR_DEFAULT);

  1093. }

  1094. 

  1095. extern Fl_Menu_Item menu[];

  1096. extern Fl_Menu_Item busymenu[];

  1097. 

  1098. int Board::handle(int e) {

  1099.   if (busy) {

  1100.     const Fl_Menu_Item* m;

  1101.     switch(e) {

  1102.     case FL_PUSH:

  1103.       m = busymenu->popup(Fl::event_x(), Fl::event_y(), 0, 0, 0);

  1104.       if (m) m->do_callback(this, (void*)m);

  1105.       return 1;

  1106.     case FL_SHORTCUT:

  1107.       m = busymenu->test_shortcut();

  1108.       if (m) {m->do_callback(this, (void*)m); return 1;}

  1109.       return 0;

  1110.     default:

  1111.       return 0;

  1112.     }

  1113.   }

  1114.   node *t, *n;

  1115.   static int deltax, deltay;

  1116.   int dist;

  1117.   const Fl_Menu_Item* m;

  1118.   switch (e) {

  1119.   case FL_PUSH:

  1120.     if (Fl::event_button() > 1) {

  1121.       m = menu->popup(Fl::event_x(), Fl::event_y(), 0, 0, 0);

  1122.       if (m) m->do_callback(this, (void*)m);

  1123.       return 1;

  1124.     }

  1125.     if (playing) {

  1126.       expandnode(root);

  1127.       for (t = root->son; t; t = t->brother) {

  1128. 	int x = squarex(t->from);

  1129. 	int y = squarey(t->from);

  1130. 	if (Fl::event_inside(x,y,BOXSIZE,BOXSIZE)) {

  1131. 	  deltax = Fl::event_x()-x;

  1132. 	  deltay = Fl::event_y()-y;

  1133. 	  drag_piece(t->from,x,y);

  1134. 	  return 1;

  1135. 	}

  1136.       }

  1137.     }

  1138.     return 0;

  1139.   case FL_SHORTCUT:

  1140.     m = menu->test_shortcut();

  1141.     if (m) {m->do_callback(this, (void*)m); return 1;}

  1142.     return 0;

  1143.   case FL_DRAG:

  1144.     drag_piece(erase_this, Fl::event_x()-deltax, Fl::event_y()-deltay);

  1145.     return 1;

  1146.   case FL_RELEASE:

  1147.     // find the closest legal move he dropped it on:

  1148.     dist = 50*50; n = 0;

  1149.     for (t = root->son; t; t = t->brother) if (t->from==erase_this) {

  1150.       int d1 = Fl::event_x()-deltax-squarex(t->to);

  1151.       int d = d1*d1;

  1152.       d1 = Fl::event_y()-deltay-squarey(t->to);

  1153.       d += d1*d1;

  1154.       if (d < dist) {dist = d; n = t;}

  1155.     }

  1156.     if (!n) {drop_piece(erase_this); return 1;} // none found

  1157.     drop_piece(n->to);

  1158.     domove(n);

  1159.     if (showlegal) {showlegal = 0; redraw();}

  1160.     if (n->jump) redraw();

  1161.     computer_move(0);

  1162.     return 1;

  1163.   default:

  1164.     return 0;

  1165.   }

  1166. }

  1167. 

  1168. void quit_cb(Fl_Widget*, void*) {exit(0);}

  1169. 

  1170. int FLTKmain(int argc, char** argv) {

  1171.   Fl::visual(FL_DOUBLE|FL_INDEX);

  1172.   Board b(BOARDSIZE,BOARDSIZE);

  1173.   b.color(FL_BACKGROUND_COLOR);

  1174.   b.callback(quit_cb);

  1175.   b.show(argc,argv);

  1176.   return Fl::run();

  1177. } 

  1178. 

  1179. void autoplay_cb(Fl_Widget*bp, void*) {

  1180.   if (autoplay) {autoplay = 0; return;}

  1181.   if (!playing) return;

  1182.   Board* b = (Board*)bp;

  1183.   autoplay = 1;

  1184.   while (autoplay) {b->computer_move(0); b->computer_move(0);}

  1185. }

  1186. 

  1187. #include <FL/Fl_Box.H>

  1188. Fl_Window *copyright_window;

  1189. void copyright_cb(Fl_Widget*, void*) {

  1190.   if (!copyright_window) {

  1191.     copyright_window = new Fl_Window(400,270,"Copyright");

  1192.     copyright_window->color(FL_WHITE);

  1193.     Fl_Box *b = new Fl_Box(20,0,380,270,copyright);

  1194.     b->labelsize(10);

  1195.     b->align(FL_ALIGN_LEFT|FL_ALIGN_INSIDE|FL_ALIGN_WRAP);

  1196.     copyright_window->end();

  1197.   }

  1198.   copyright_window->hotspot(copyright_window);

  1199.   copyright_window->set_non_modal();

  1200.   copyright_window->show();

  1201. }

  1202. 

  1203. void debug_cb(Fl_Widget*, void*v) {

  1204.   debug = !debug;

  1205.   ((Fl_Menu_Item*)v)->flags =

  1206.     debug ? FL_MENU_TOGGLE|FL_MENU_VALUE : FL_MENU_TOGGLE;

  1207. }

  1208. 

  1209. void forced_cb(Fl_Widget*b, void*v) {

  1210.   forcejumps = !forcejumps;

  1211.   ((Fl_Menu_Item*)v)->flags =

  1212.     forcejumps ? FL_MENU_TOGGLE|FL_MENU_VALUE : FL_MENU_TOGGLE;

  1213.   killnode(root->son); root->son = 0;

  1214.   if (showlegal) {expandnode(root); b->redraw();}

  1215. }

  1216. 

  1217. void move_cb(Fl_Widget*pb, void*) {

  1218.   Board* b = (Board*)pb;

  1219.   if (playing) b->computer_move(1);

  1220.   if (playing) b->computer_move(0);

  1221. }

  1222. 

  1223. void newgame_cb(Fl_Widget*b, void*) {

  1224.   showlegal = 0;

  1225.   newgame();

  1226.   b->redraw();

  1227. }

  1228. 

  1229. void legal_cb(Fl_Widget*pb, void*) {

  1230.   if (showlegal == 1) {showlegal = 0; ((Board*)pb)->redraw(); return;}

  1231.   if (!playing) return;

  1232.   expandnode(root);

  1233.   showlegal = 1; ((Board*)pb)->redraw();

  1234. }

  1235. 

  1236. void predict_cb(Fl_Widget*pb, void*) {

  1237.   if (showlegal == 2) {showlegal = 0; ((Board*)pb)->redraw(); return;}

  1238.   if (playing) expandnode(root);

  1239.   showlegal = 2; ((Board*)pb)->redraw();

  1240. }

  1241. 

  1242. void switch_cb(Fl_Widget*pb, void*) {

  1243.   user = !user;

  1244.   ((Board*)pb)->computer_move(0);

  1245. }

  1246. 

  1247. void undo_cb(Fl_Widget*pb, void*) {

  1248.   Board* b = (Board*)pb;

  1249.   b->animate(undomove(),1);

  1250.   b->animate(undomove(),1);

  1251. }

  1252. 

  1253. //--------------------------

  1254. 

  1255. #include <FL/Fl_Slider.H>

  1256. #include <FL/Fl_Value_Output.H>

  1257. 

  1258. Fl_Window *intel_window;

  1259. Fl_Value_Output *intel_output;

  1260. 

  1261. void intel_slider_cb(Fl_Widget*w, void*) {

  1262.   double v = ((Fl_Slider*)w)->value();

  1263.   int n = int(v*v);

  1264.   intel_output->value(n);

  1265.   maxevaluate = maxnodes = n;

  1266. }

  1267. 

  1268. void intel_cb(Fl_Widget*, void*) {

  1269.   if (!intel_window) {

  1270.     intel_window = new Fl_Window(200,25,"Checkers Intelligence");

  1271.     Fl_Slider* s = new Fl_Slider(60,0,140,25);

  1272.     s->type(FL_HOR_NICE_SLIDER);

  1273.     s->minimum(1); s->maximum(500); s->value(50);

  1274.     s->callback(intel_slider_cb);

  1275.     intel_output = new Fl_Value_Output(0,0,60,25);

  1276.     intel_output->value(maxevaluate);

  1277.     intel_window->resizable(s);

  1278.   }

  1279.   intel_window->hotspot(intel_window);

  1280.   intel_window->set_non_modal();

  1281.   intel_window->show();

  1282. }

  1283. 

  1284. //---------------------------

  1285. 

  1286. void stop_cb(Fl_Widget*, void*) {abortflag = 1;}

  1287. 

  1288. void continue_cb(Fl_Widget*, void*) {}

  1289. 

  1290. Fl_Menu_Item menu[] = {

  1291.   {"Autoplay", 'a', autoplay_cb},

  1292.   {"Legal moves", 'l', legal_cb},

  1293.   {"Move for me", 'm', move_cb},

  1294.   {"New game", 'n', newgame_cb},

  1295.   {"Predict", 'p', predict_cb},

  1296.   {"Switch sides", 's', switch_cb},

  1297.   {"Undo", 'u', undo_cb, 0, FL_MENU_DIVIDER},

  1298.   {"Forced jumps rule", 'f', forced_cb, 0, FL_MENU_TOGGLE|FL_MENU_VALUE},

  1299.   {"Debug", 'd', debug_cb, (void *)"d", FL_MENU_TOGGLE},

  1300.   {"Intelligence...", 'i', intel_cb, 0, FL_MENU_DIVIDER},

  1301.   {"Copyright", 'c', copyright_cb},

  1302.   {"Quit", 'q', quit_cb},

  1303.   {0}};

  1304. 

  1305. Fl_Menu_Item busymenu[] = {

  1306.   {"Stop", '.', stop_cb},

  1307.   {"Autoplay", 'a', autoplay_cb},

  1308.   {"Continue", 0, continue_cb},

  1309.   {"Debug", 'd', debug_cb, (void *)"d", FL_MENU_TOGGLE},

  1310.   {"Intelligence...", 'i', intel_cb},

  1311.   {"Copyright", 'c', copyright_cb},

  1312.   {"Quit", 'q', quit_cb},

  1313.   {0}};

  1314. 

  1315. #endif

  1316. 

  1317. ////////////////////////////////////////////////////////////////

  1318. // parts shared by both interface:

  1319. 

  1320. #ifdef FLTK

  1321. #ifdef VT100

  1322. #define BOTH

  1323. #endif

  1324. #endif

  1325. 

  1326. #ifdef BOTH

  1327. int terminal;

  1328. int arg(int, char **argv, int &i) {

  1329.   if (argv[i][1] == 't') {terminal = 1; i++; return 1;}

  1330.   return 0;

  1331. }

  1332. #endif

  1333. 

  1334. int didabort(void) {

  1335. #ifdef FLTK

  1336. #ifdef BOTH

  1337.   if (!terminal)

  1338. #endif

  1339.     Fl::check();

  1340. #endif

  1341.   if (abortflag) {

  1342.     autoplay = 0;

  1343.     abortflag = 0;

  1344.     return 1;

  1345.   }

  1346.   return(0);

  1347. }

  1348. 

  1349. int main(int argc, char **argv) {

  1350.   seed = time(0);

  1351.   newgame();

  1352. #ifdef BOTH

  1353.   int i = 1;

  1354.   if (Fl::args(argc, argv, i, arg) < argc) {

  1355.     fprintf(stderr," -t : use VT100 display\n", Fl::help);

  1356.     exit(1);

  1357.   }

  1358.   if (!getenv("DISPLAY")) terminal = 1;

  1359.   if (!terminal)

  1360. #endif

  1361. #ifdef FLTK

  1362.     return FLTKmain(argc,argv);

  1363. #endif

  1364. #ifdef VT100

  1365.   return VT100main();

  1366. #endif

  1367. }

  1368. 

  1369. //

  1370. // End of "$Id: checkers.cxx 8168 2011-01-02 03:55:23Z matt $".

  1371. //