home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / benchmar / 1992 < prev    next >
Encoding:
Internet Message Format  |  1993-01-23  |  34.9 KB
  1. Path: sparky!uunet!olivea!pagesat!netsys!agate!dog.ee.lbl.gov!news!marlin!aburto
  2. From: aburto@nosc.mil (Alfred A. Aburto)
  3. Newsgroups: comp.benchmarks
  4. Subject: Fhourstones Benchmark C Source Code
  5. Message-ID: <1993Jan22.204529.818@nosc.mil>
  6. Date: 22 Jan 93 20:45:29 GMT
  7. Expires: Mon, 15 Feb 1993 08:00:00 GMT
  8. Distribution: comp.arch, comp.benchmarks
  9. Organization: Naval Ocean Systems Center, San Diego
  10. Lines: 1443
  11.  
  12. # This is a shell archive.  Remove anything before this line, then unpack
  13. # it by saving it into a file and typing "sh file".  To overwrite existing
  14. # files, type "sh file -c".  You can also feed this as standard input via
  15. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  16. # will see the following message at the end:
  17. #        "End of shell archive."
  18. # Contents:  MANIFEST Makefile README best.c best.h c4.c c4.h input
  19. #   mach.c play.c play.h trans.c
  20. # Wrapped by tromp@wolf.cwi.nl on Wed Jan 20 11:44:49 1993
  21. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  22. if test -f 'MANIFEST' -a "${1}" != "-c" ; then 
  23.   echo shar: Will not clobber existing file \"'MANIFEST'\"
  24. else
  25. echo shar: Extracting \"'MANIFEST'\" \(570 characters\)
  26. sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
  27. X-rw-r--r--  1 tromp         929 Jan 20 11:11 Makefile
  28. X-rw-r--r--  1 tromp        2724 Jan 20 11:44 README
  29. X-rw-r--r--  1 tromp        2669 Jan 19 11:32 best.c
  30. X-rw-r--r--  1 tromp        3409 Oct 23 13:54 best.h
  31. X-rw-r--r--  1 tromp        3307 Jan 20 09:37 c4.c
  32. X-rw-r--r--  1 tromp         600 Jan 19 11:32 c4.h
  33. X-rw-r--r--  1 tromp          14 Aug 29 18:32 input
  34. X-rw-------  1 tromp        7335 Dec  4 19:22 mach.c
  35. X-rw-r--r--  1 tromp        2236 Oct 15 12:16 play.c
  36. X-rw-r--r--  1 tromp        1443 Aug 20 12:33 play.h
  37. X-rw-r--r--  1 tromp        4179 Jan 19 11:53 trans.c
  38. END_OF_FILE
  39. if test 570 -ne `wc -c <'MANIFEST'`; then
  40.     echo shar: \"'MANIFEST'\" unpacked with wrong size!
  41. fi
  42. # end of 'MANIFEST'
  43. fi
  44. if test -f 'Makefile' -a "${1}" != "-c" ; then 
  45.   echo shar: Will not clobber existing file \"'Makefile'\"
  46. else
  47. echo shar: Extracting \"'Makefile'\" \(929 characters\)
  48. sed "s/^X//" >'Makefile' <<'END_OF_FILE'
  49. X# current options include SMALL.
  50. XDEFINES = -DUNIX -DSMALL
  51. XFLAGS = -O $(DEFINES)
  52. XFILES = Makefile README \
  53. X        best.c best.h c4.c c4.h input mach.c play.c play.h trans.c
  54. X
  55. XCC = cc $(FLAGS)
  56. X
  57. Xc4        : c4.o trans.o best.o play.o mach.o
  58. X        $(CC) -o c4 c4.o trans.o best.o play.o mach.o
  59. X
  60. Xc4.o        : c4.c c4.h Makefile
  61. X        $(CC) -c c4.c
  62. X
  63. Xtrans.o        : trans.c c4.h Makefile
  64. X        $(CC) -c trans.c
  65. X
  66. Xbest.o        : best.c c4.h best.h Makefile
  67. X        $(CC) -c best.c
  68. X
  69. Xplay.o        : play.c c4.h play.h Makefile
  70. X        $(CC) -c play.c
  71. X
  72. Xmach.o        : mach.c Makefile
  73. X        $(CC) -c mach.c
  74. X
  75. X# use the following for optimization levels that preclude separate compilation
  76. Xtogether    : c4.c c4.h trans.c best.c best.h play.c play.h mach.c Makefile
  77. X        $(CC) -o c4 c4.c trans.c best.c play.c mach.c
  78. X
  79. XMANIFEST    : $(FILES)
  80. X        ls -l $(FILES) > MANIFEST
  81. X
  82. Xshar        : $(FILES) MANIFEST
  83. X        shar -o c4.shar MANIFEST $(FILES)
  84. X
  85. Xtar        : $(FILES) MANIFEST
  86. X        tar -cf c4.tar MANIFEST  $(FILES)
  87. X        compress c4.tar
  88. END_OF_FILE
  89. if test 929 -ne `wc -c <'Makefile'`; then
  90.     echo shar: \"'Makefile'\" unpacked with wrong size!
  91. fi
  92. # end of 'Makefile'
  93. fi
  94. if test -f 'README' -a "${1}" != "-c" ; then 
  95.   echo shar: Will not clobber existing file \"'README'\"
  96. else
  97. echo shar: Extracting \"'README'\" \(2724 characters\)
  98. sed "s/^X//" >'README' <<'END_OF_FILE'
  99. X                    The FHOURSTONES benchmark
  100. X
  101. X
  102. XThis benchmark is distilled from my pet application `c4', a connect-4 solver.
  103. XIt features a streamlined implementation of exhaustive alpha-beta
  104. Xsearch using the history heuristic and a space optimized hashtable.
  105. X
  106. XSome technical bits:
  107. XOf the full 49 bit lock that describes a connect-4 position, only 32 are
  108. Xstored in the hashtable entry while the remaining 17 are subsumed in the
  109. Xhash-address. To also accomodate 8 fold probing, a minimum of a million
  110. Xhash table entries are required. The benchmark uses just over 5Mb, unlikely
  111. Xto fit into any sort of cache in the foreseeable future.
  112. XThis makes the Fhourstones measure relatively immune to huge cache sizes.
  113. X
  114. XThe potentially expensive modulo operations are implemented with repeated
  115. Xtable lookup. The use of small integer sizes is available as an option.
  116. X
  117. XAlthough this benchmark, like nsieve, emphasizes random access performance,
  118. Xit also exercises standard scalar performance; the recursive alpha-beta
  119. Xcalls, incremental threat table computations, history table updates, and
  120. Xmove-reordering represent a fair mix of scalar operations.
  121. X
  122. XThe benchmark input is a relatively difficult 12-ply position.
  123. XThe output should look like:
  124. X
  125. Xoptions:    small ints
  126. XSolving 12-ply position after 444333377755 . . .
  127. Xscore = 7 (+)  work = 21
  128. X3871322 pos / 98.7 sec = 39227 p/s
  129. Xstore rate = 0.914
  130. X- 0.211  < 0.422  = 0.059  > 0.054  + 0.254
  131. X 56765  376940  173046  174816  121323   70603   38079   19252
  132. X  9741    4853    2393    1147     537     291     116      54
  133. X    30      16       3       2       3       1       0       0
  134. X     0       0       0       0       0       0       0       0
  135. X
  136. XThe first line shows which program-specific options are active.
  137. XCurrently, only one is supported: -DSMALL makes the program use
  138. Xchars and shorts in moderately sized arrays of small integers.
  139. XThe benefit of this option is machine-specific; sometimes it's better and
  140. Xsometimes it's worse.
  141. XThe 2nd line says which positions is being solved (input ends with =),
  142. Xor tested for a 1st player win (+) or for a 2nd player win (-). Due to
  143. Xthe transposition table and history heuristic, the reduced searches are not
  144. Xnecessarily faster.
  145. XThe next line indicates the score of the position and a logarithmic measure
  146. Xof difficulty on a scale from 0 to 31.
  147. XThe fourth line shows the machine performance;
  148. Xof all the output, only the last 2 numbers on this line
  149. Xshould differ from the above output.
  150. XThe store rate gives the percentage of positions actually entered
  151. Xin the transposition table versus those offered to it.
  152. XThe rest of the output shows the final distribution of positions in
  153. Xthe transposition table with respect to
  154. Xscore (line 6) and work (lines 7-10).
  155. END_OF_FILE
  156. if test 2724 -ne `wc -c <'README'`; then
  157.     echo shar: \"'README'\" unpacked with wrong size!
  158. fi
  159. # end of 'README'
  160. fi
  161. if test -f 'best.c' -a "${1}" != "-c" ; then 
  162.   echo shar: Will not clobber existing file \"'best.c'\"
  163. else
  164. echo shar: Extracting \"'best.c'\" \(2669 characters\)
  165. sed "s/^X//" >'best.c' <<'END_OF_FILE'
  166. X/* alpha beta search
  167. X   (c) 1992 John Tromp
  168. X*/
  169. X
  170. X#include "c4.h"
  171. X
  172. X#define BONUS        1
  173. X
  174. Xint window;    /* 0 = [-,+]    1 = [=,+]   2 = [-,=] */
  175. Xstatic uint8 alp[] = {WIN2, DRAW, WIN2},
  176. X             bet[] = {WIN1, WIN1, DRAW};
  177. Xstatic uint8 xkiller[64], okiller[64];
  178. X
  179. Xextern B8 r, columns, height;
  180. Xextern uint8 xthrcnt[], othrcnt[], colthr[], *moves;
  181. Xextern int plycnt;
  182. Xextern u_int posed;
  183. Xextern void makemovx(),makemovo(),backmovx(),backmovo();
  184. Xextern int transpose(), transtore();
  185. Xextern void emptyht();
  186. X
  187. Xu_int nodes;
  188. X
  189. Xvoid initbest()
  190. X{
  191. X}
  192. X
  193. Xstatic FILE *BOOKFILE;
  194. X
  195. Xint bookin()
  196. X{
  197. X  static int buf5 = 1;
  198. X  static int nrle;
  199. X  int score;
  200. X
  201. X  if (buf5 == 1) {
  202. X    if (nrle) {
  203. X      buf5 = 242;
  204. X      nrle--;
  205. X    } else if ((buf5 = getc(BOOKFILE)) > 242) {
  206. X      nrle = buf5 - 242;
  207. X      buf5 = 242;
  208. X    }
  209. X    buf5 += 243;
  210. X  }
  211. X  score = 3 + 2 * (buf5 % 3);
  212. X  buf5 /= 3;
  213. X  return score;
  214. X}
  215. X
  216. X#define ME    1
  217. X#define OPP    2
  218. X#define BOOKME    bookx
  219. X#define BOOKOPP booko
  220. X#define ABME    abx
  221. X#define ABOPP    abo
  222. X#define THRME    xthrcnt
  223. X#define THROPP    othrcnt
  224. X#define IWIN    WIN2
  225. X#define ILOSE    WIN1
  226. X#define MAKEMOV    makemovx
  227. X#define BACKMOV    backmovx
  228. X#define WORST    8
  229. X#define KILLER    xkiller
  230. X#define WRSTBND    beta
  231. X#define BESTBND    alpha
  232. X#define IMPRVS    <
  233. X#define NOWORSE    <=
  234. X#define NOLOSE    DRIN2
  235. X#include "best.h"
  236. X
  237. X#define ME    2
  238. X#define OPP    1
  239. X#define BOOKME    booko
  240. X#define BOOKOPP    bookx
  241. X#define ABME    abo
  242. X#define ABOPP    abx
  243. X#define THRME    othrcnt
  244. X#define THROPP    xthrcnt
  245. X#define IWIN    WIN1
  246. X#define ILOSE    WIN2
  247. X#define MAKEMOV    makemovo
  248. X#define BACKMOV    backmovo
  249. X#define WORST    0
  250. X#define KILLER    okiller
  251. X#define WRSTBND    alpha
  252. X#define BESTBND    beta
  253. X#define IMPRVS    >
  254. X#define NOWORSE    >=
  255. X#define NOLOSE    DRIN1
  256. X#include "best.h"
  257. X
  258. Xvoid loadbook()
  259. X{
  260. X  BOOKFILE = fopen("book.8", "r");
  261. X  if (BOOKFILE == NULL) {
  262. X    printf("File book.8 not found.\n");
  263. X    exit(0);
  264. X  }
  265. X  nodes = 0;
  266. X  booko();
  267. X  if (getc(BOOKFILE) != EOF) {
  268. X    printf("File book.8 corrupt.\n");
  269. X    exit(0);
  270. X  }
  271. X  fclose(BOOKFILE);
  272. X}
  273. X
  274. Xint best()
  275. X{
  276. X  int i,(*myab)();
  277. X  uint8 *mythrcnt;
  278. X  int me,x,work,score;
  279. X  u_int poscnt;
  280. X
  281. X  nodes = 0;
  282. X  if (plycnt & 1) {
  283. X    mythrcnt = xthrcnt;
  284. X    myab = abx;
  285. X    me = 1;
  286. X  } else {
  287. X    mythrcnt = othrcnt;
  288. X    myab = abo;
  289. X    me = 2;
  290. X  }
  291. X  for (i = 0; i = r[i]; ) {
  292. X    if (mythrcnt[height[i]] || colthr[columns[i]] == me)
  293. X      return (plycnt&1) ? WIN2 : WIN1;
  294. X  }
  295. X  if (x = transpose(columns)) {
  296. X    score = SCORE(x);
  297. X    if (EXACT(score))
  298. X      return score;
  299. X  }
  300. X  for (i=0; i<64; i++)
  301. X     okiller[i] = xkiller[i] = 0x80;
  302. X  emptyht();
  303. X  score = myab(alp[window], bet[window]);
  304. X  poscnt = posed;
  305. X  for (work=1; poscnt>>=1; work++) ;    /* work = log of #positions stored */
  306. X  return work << 3 | score;        /* normally bestofall */
  307. X}
  308. END_OF_FILE
  309. if test 2669 -ne `wc -c <'best.c'`; then
  310.     echo shar: \"'best.c'\" unpacked with wrong size!
  311. fi
  312. # end of 'best.c'
  313. fi
  314. if test -f 'best.h' -a "${1}" != "-c" ; then 
  315.   echo shar: Will not clobber existing file \"'best.h'\"
  316. else
  317. echo shar: Extracting \"'best.h'\" \(3409 characters\)
  318. sed "s/^X//" >'best.h' <<'END_OF_FILE'
  319. Xint BOOKME()
  320. X{
  321. X  int score,bestscore,i,x,threat;
  322. X
  323. X  nodes++;
  324. X  if (x = transpose(columns))
  325. X    return SCORE(x);
  326. X
  327. X  if (plycnt >= 8) {
  328. X    for (threat=i=0; i=r[i]; ) {
  329. X      if (THRME[height[i]] || colthr[columns[i]]==ME)
  330. X        return IWIN;
  331. X      if (THROPP[height[i]] || colthr[columns[i]]==OPP)
  332. X        threat = threat << 3 | i;
  333. X    }
  334. X    if (threat > 7)
  335. X      return ILOSE;
  336. X    if (!threat) {
  337. X      score = bookin();
  338. X      transtore(columns, score, 31);
  339. X      return score;
  340. X    }
  341. X    MAKEMOV(threat);
  342. X    score = BOOKOPP();
  343. X    BACKMOV();
  344. X    return score;
  345. X  }
  346. X  for (bestscore=WORST,i=0; i=r[i]; ) {
  347. X    if (THRME[height[i]] || colthr[columns[i]]==ME) {
  348. X      bestscore = IWIN;
  349. X      continue;
  350. X    }
  351. X    MAKEMOV(i);
  352. X    if ((score = BOOKOPP()) IMPRVS bestscore)
  353. X      bestscore = score;
  354. X    BACKMOV();
  355. X  }
  356. X  transtore(columns, bestscore, 1);
  357. X  return bestscore;
  358. X}
  359. X
  360. Xint ABME(alpha, beta)
  361. Xint alpha, beta;
  362. X{
  363. X  register int besti,i,j,k,l,val,score;
  364. X  int x,v,work;
  365. X  int rr[8];
  366. X  u_int poscnt;
  367. X
  368. X  nodes++;
  369. X#if ME == 2        /* O to move can be drawn */
  370. X  if (!r[0])
  371. X    return DRAW;
  372. X#endif
  373. X  for (i = j = 0; i = r[i];) {
  374. X    if (THROPP[height[i]] || colthr[columns[i]]) { /* ignore case of colthr */
  375. X      if (THROPP[height[i]-8])
  376. X        return ILOSE;
  377. X      j = rr[0] = i;        /* forget other moves */
  378. X      while (i = r[i])
  379. X        if (THROPP[height[i]] || colthr[columns[i]])
  380. X          return ILOSE;
  381. X      break;
  382. X    }
  383. X    if (!THROPP[height[i]-8])
  384. X      j = rr[j] = i;
  385. X  }
  386. X  if (!j)
  387. X    return ILOSE;
  388. X  if (j == rr[0]) {
  389. X    MAKEMOV(j);
  390. X    score = ABOPP(alpha, beta);
  391. X    BACKMOV();
  392. X    return score;
  393. X  }
  394. X  if (x = transpose(columns)) {
  395. X    score = SCORE(x);
  396. X    if (score == DRIN2) {
  397. X      if ((beta = DRAW) <= alpha)
  398. X        return score;
  399. X    } else if (score == DRIN1) {
  400. X      if ((alpha = DRAW) >= beta)
  401. X        return score;
  402. X    } else return score;
  403. X  }
  404. X  poscnt = posed;
  405. X  score = WORST;    /* try to get the best bound if score > beta */
  406. X  for (i = rr[j] = 0; rr[i]; ) {
  407. X    for (j = i, val = 0; k = rr[j]; j = k) {
  408. X      v = KILLER[height[k]];           /* truly dynamic move ordering! */
  409. X      if (k == LASTMOVE)        /* make same column attractive */
  410. X        v += BONUS;
  411. X      if (v > val) {
  412. X        val = v;
  413. X        l = j;                          /* l ::= predecessor of best */
  414. X      }
  415. X    }
  416. X    if (i != l) {
  417. X      rr[l] = rr[k = rr[l]];              /* move best */
  418. X      rr[k] = rr[i];
  419. X      i = rr[i] = k;
  420. X    } else i = rr[i];
  421. X
  422. X    MAKEMOV(i);
  423. X    val = ABOPP(alpha, beta);
  424. X    BACKMOV();
  425. X    if (val IMPRVS score) {
  426. X      besti = i;
  427. X      if ((score = val) IMPRVS WRSTBND && (WRSTBND = val) NOWORSE BESTBND) {
  428. X        if (score == DRAW && rr[i])
  429. X          score = NOLOSE;
  430. X        break;
  431. X      }
  432. X    }
  433. X  }
  434. X  for (j = i = 0; (i = rr[i]) != besti; j++)
  435. X    KILLER[height[i]]--;            /* punish bad killers */
  436. X  KILLER[height[besti]] += j;
  437. X  poscnt = posed - poscnt;
  438. X  for (work=1; poscnt>>=1; work++) ;    /* work = log of #positions stored */
  439. X  if (x) {
  440. X    if (score == DRIN1+DRIN2 - SCORE(x))    /* combine < and > */
  441. X      score = DRAW;
  442. X    (void)transrestore(columns, score, work);
  443. X  } else (void)transtore(columns, score, work);
  444. X  return score;
  445. X}
  446. X
  447. X#undef ME
  448. X#undef OPP
  449. X#undef BOOKME
  450. X#undef BOOKOPP
  451. X#undef ABME
  452. X#undef ABOPP
  453. X#undef THRME
  454. X#undef THROPP
  455. X#undef IWIN
  456. X#undef ILOSE
  457. X#undef MAKEMOV
  458. X#undef BACKMOV
  459. X#undef WORST
  460. X#undef KILLER
  461. X#undef WRSTBND
  462. X#undef BESTBND
  463. X#undef IMPRVS
  464. X#undef NOWORSE
  465. X#undef NOLOSE
  466. END_OF_FILE
  467. if test 3409 -ne `wc -c <'best.h'`; then
  468.     echo shar: \"'best.h'\" unpacked with wrong size!
  469. fi
  470. # end of 'best.h'
  471. fi
  472. if test -f 'c4.c' -a "${1}" != "-c" ; then 
  473.   echo shar: Will not clobber existing file \"'c4.c'\"
  474. else
  475. echo shar: Extracting \"'c4.c'\" \(3307 characters\)
  476. sed "s/^X//" >'c4.c' <<'END_OF_FILE'
  477. X/*
  478. X * Fhourstones connect-4 solver
  479. X *
  480. X * implementation of the well-known game
  481. X * played on a vertical board of 7 columns by 6 rows,
  482. X * where 2 players take turns in dropping counters in a column.
  483. X * the first player to get four of his counters
  484. X * in a horizontal, vertical or diagonal row, wins the game.
  485. X * if neither player has won after 42 moves, then the game is drawn.
  486. X *
  487. X * This software is copyright (c) 1992 by
  488. X *      John Tromp
  489. X *      Lindenlaan 33
  490. X *      1701 GT Heerhugowaard
  491. X *      Netherlands
  492. X * E-mail: tromp@cwi.nl
  493. X *
  494. X * This notice must not be removed.
  495. X * This software must not be sold for profit.
  496. X * You may redistribute if your distributees have the
  497. X * same rights and restrictions.
  498. X */
  499. X
  500. X
  501. X#include "c4.h"
  502. X
  503. Xstatic
  504. Xint history[43],    /* history of current game */
  505. X    movenr;        /* number of counters played in current game */
  506. X
  507. Xstatic
  508. Xint error,        /* invalid user input */
  509. X    gameover;        /* game has been drawn or won */
  510. Xextern int window;    /* search window */
  511. X
  512. Xvoid initall()
  513. X{
  514. X  extern void initbest(),inittrans(),initplay();
  515. X
  516. X  initbest();
  517. X  inittrans();
  518. X  initplay();
  519. X}
  520. X
  521. Xvoid game()
  522. X{
  523. X  extern void newgame();
  524. X
  525. X  movenr = gameover = 0;
  526. X  newgame();
  527. X}
  528. X
  529. Xvoid play(n)
  530. Xint n;
  531. X{
  532. X  extern int depth();
  533. X  extern void makemovx(),makemovo();
  534. X
  535. X   if (error = n < 1 || n > 7 || !depth(n) || gameover)
  536. X      return;
  537. X   if (history[movenr] != n)
  538. X   {  history[movenr] = n;
  539. X      history[movenr+1] = 0;     /* end of variation */
  540. X   }
  541. X   if (++movenr & 1)
  542. X     makemovo(n);
  543. X   else
  544. X     makemovx(n);
  545. X   gameover = haswon() || movenr == 42;
  546. X}
  547. X
  548. Xmain()
  549. X{
  550. X  int c,i,result;
  551. X  extern int best();
  552. X  extern void loadbook(),htstat();
  553. X  extern u_int nodes;
  554. X  double timearray[3];
  555. X  extern int dtime();
  556. X
  557. X  initall();
  558. X#ifdef BOOK
  559. X  loadbook();
  560. X#endif
  561. X  (void)printf("options:");
  562. X#ifdef SMALL
  563. X  (void)printf("    small ints");
  564. X#endif
  565. X  (void)printf("\n");
  566. X  for (;;) {
  567. X    game();
  568. X    while ((c = getchar()) != EOF) {
  569. X      if (c >= '1' && c <= '7')
  570. X        c -= '0';
  571. X      else if (c >= 'A' && c <= 'G')
  572. X        c -= ('A' - 1);
  573. X      else if (c >= 'a' && c <= 'g')
  574. X        c -= ('a' - 1);
  575. X      else if (c == '=' || c == '+' || c == '-' ||
  576. X               (error = c != ' ' && c != '\t' && c != '\n'))
  577. X        break;
  578. X      else continue;
  579. X      play(c);
  580. X      if (error) {
  581. X        (void)printf("illegal move.\n");
  582. X        break;
  583. X      }
  584. X    }
  585. X    if (c == EOF)
  586. X      break;
  587. X    if (error) {
  588. X      error = 0;
  589. X      continue;
  590. X    }
  591. X    if (gameover) {
  592. X      (void)printf("Game is over.\n");
  593. X      continue;
  594. X    }
  595. X
  596. X    switch (c) {
  597. X    case '-':
  598. X      window = 2;
  599. X      (void)printf("Looking for 2nd player win in");
  600. X      break;
  601. X    case '=':
  602. X      window = 0;
  603. X      (void)printf("Solving");
  604. X      break;
  605. X    case '+':
  606. X      window = 1;
  607. X      (void)printf("Looking for 1st player win in");
  608. X      break;
  609. X    }
  610. X    (void)printf(" %d-ply position after ", movenr);
  611. X    for (i = 0; i < movenr; i++)
  612. X      (void)printf("%d", history[i]);
  613. X    (void)printf(" . . .\n");
  614. X
  615. X    dtime(timearray);
  616. X    result = best();        /* expect work << 3 | score */
  617. X    dtime(timearray);
  618. X    (void)printf("score = %d (%c)  work = %d\n", result&7,
  619. X           "   -<=>+"[result&7], result>>3);
  620. X    (void)printf("%u pos / %.1f sec = %d p/s\n",
  621. X             nodes, timearray[1], (int)((double)nodes/timearray[1]));
  622. X    htstat();
  623. X  }
  624. X  return 0;
  625. X}
  626. END_OF_FILE
  627. if test 3307 -ne `wc -c <'c4.c'`; then
  628.     echo shar: \"'c4.c'\" unpacked with wrong size!
  629. fi
  630. # end of 'c4.c'
  631. fi
  632. if test -f 'c4.h' -a "${1}" != "-c" ; then 
  633.   echo shar: Will not clobber existing file \"'c4.h'\"
  634. else
  635. echo shar: Extracting \"'c4.h'\" \(600 characters\)
  636. sed "s/^X//" >'c4.h' <<'END_OF_FILE'
  637. X/* type-definitions
  638. X   (c) 1992 John Tromp
  639. X*/
  640. X
  641. X#include <sys/types.h>
  642. X#include <stdio.h>
  643. Xextern void exit();
  644. X
  645. Xextern char *calloc();
  646. X#define allocate(N, T)  ((T *)calloc((unsigned)N,sizeof(T)))
  647. X#define UNK        2
  648. X#define WIN2        3
  649. X#define DRIN2        4
  650. X#define DRAW        5
  651. X#define DRIN1        6
  652. X#define WIN1        7
  653. X#define EXACT(S)    ((S)==WIN2 || (S)==DRAW || (S)==WIN1)
  654. X#define SCORE(X)    ((X) & 7)
  655. X#define WORK(X)        ((X) >> 3)
  656. X#define LASTMOVE        moves[plycnt-1]
  657. X
  658. X#ifdef SMALL
  659. Xtypedef u_char uint8;
  660. Xtypedef u_short uint16;
  661. X#else
  662. Xtypedef int uint8;
  663. Xtypedef int uint16;
  664. X#endif
  665. Xtypedef uint8 B8[8];
  666. Xtypedef u_char hashentry;
  667. END_OF_FILE
  668. if test 600 -ne `wc -c <'c4.h'`; then
  669.     echo shar: \"'c4.h'\" unpacked with wrong size!
  670. fi
  671. # end of 'c4.h'
  672. fi
  673. if test -f 'input' -a "${1}" != "-c" ; then 
  674.   echo shar: Will not clobber existing file \"'input'\"
  675. else
  676. echo shar: Extracting \"'input'\" \(14 characters\)
  677. sed "s/^X//" >'input' <<'END_OF_FILE'
  678. X444333377755=
  679. END_OF_FILE
  680. if test 14 -ne `wc -c <'input'`; then
  681.     echo shar: \"'input'\" unpacked with wrong size!
  682. fi
  683. # end of 'input'
  684. fi
  685. if test -f 'mach.c' -a "${1}" != "-c" ; then 
  686.   echo shar: Will not clobber existing file \"'mach.c'\"
  687. else
  688. echo shar: Extracting \"'mach.c'\" \(7335 characters\)
  689. sed "s/^X//" >'mach.c' <<'END_OF_FILE'
  690. X/*****************************************************/
  691. X/* Various machine dependent timer routines.         */
  692. X/* Al Aburto, aburto@marlin.nosc.mil, 26 Sep 1992    */
  693. X/*                                                   */
  694. X/* dtime(p) outputs the elapsed time seconds in p[1] */
  695. X/* from a call of dtime(p) to the next call of       */
  696. X/* dtime(p).  Use CAUTION as some of these routines  */
  697. X/* will mess up when timing across the hour mark!!!  */
  698. X/*                                                   */
  699. X/* For timing I use the 'user' time whenever         */
  700. X/* possible. Using 'user+sys' time is a separate     */
  701. X/* issue.                                            */
  702. X/*                                                   */
  703. X/* Example Usage:                                    */
  704. X/* [Timer options added here]                        */
  705. X/* double RunTime, TimeArray[3];                     */
  706. X/* main()                                            */
  707. X/* {                                                 */
  708. X/* dtime(TimeArray);                                 */ 
  709. X/* [routine to time]                                 */
  710. X/* dtime(TimeArray);                                 */
  711. X/* RunTime = TimeArray[1];                           */
  712. X/* }                                                 */
  713. X/* [Timer code added here]                           */
  714. X/*****************************************************/
  715. X
  716. X/***************************************************************/
  717. X/* Timer options. You MUST uncomment one of the options below  */
  718. X/* or compile, for example, with the '-DUNIX' option.          */
  719. X/***************************************************************/
  720. X/* #define Amiga       */
  721. X/* #define UNIX        */
  722. X/* #define UNIX_Old    */
  723. X/* #define VMS         */
  724. X/* #define BORLAND_C   */
  725. X/* #define MSC         */
  726. X/* #define MAC         */
  727. X/* #define IPSC        */
  728. X/* #define FORTRAN_SEC */
  729. X/* #define GTODay      */
  730. X/* #define CTimer      */
  731. X
  732. X/******************************/
  733. X/* Timer code.                */
  734. X/******************************/
  735. X/*******************/
  736. X/*  Amiga dtime()  */
  737. X/*******************/
  738. X#ifdef Amiga
  739. X#include <ctype.h>
  740. X#define HZ 50
  741. X
  742. Xdtime(p)
  743. Xdouble p[];
  744. X{
  745. X   double q;
  746. X
  747. X   struct   tt {
  748. X      long  days;
  749. X      long  minutes;
  750. X      long  ticks;
  751. X   } tt;
  752. X
  753. X   q = p[2];
  754. X
  755. X   DateStamp(&tt);
  756. X
  757. X   p[2] = ( (double)(tt.ticks + (tt.minutes * 60L * 50L)) ) / (double)HZ;
  758. X   p[1] = p[2] - q;
  759. X   
  760. X   return 0;
  761. X}
  762. X#endif
  763. X
  764. X/*****************************************************/
  765. X/*  UNIX dtime(). This is the preferred UNIX timer.  */
  766. X/*  Provided by: Markku Kolkka, mk59200@cc.tut.fi    */
  767. X/*  HP-UX Addition by: Bo Thide', bt@irfu.se         */
  768. X/*****************************************************/
  769. X#ifdef UNIX
  770. X#include <sys/time.h>
  771. X#include <sys/resource.h>
  772. X
  773. X#ifdef hpux
  774. X#include <sys/syscall.h>
  775. X#define getrusage(a,b) syscall(SYS_getrusage,a,b)
  776. X#endif
  777. X
  778. Xstruct rusage rusage;
  779. X
  780. Xdtime(p)
  781. Xdouble p[];
  782. X{
  783. X   double q;
  784. X
  785. X   q = p[2];
  786. X
  787. X   getrusage(RUSAGE_SELF,&rusage);
  788. X
  789. X   p[2] = (double)(rusage.ru_utime.tv_sec);
  790. X   p[2] = p[2] + (double)(rusage.ru_utime.tv_usec) * 1.0e-06;
  791. X   p[1] = p[2] - q;
  792. X   
  793. X   return 0;
  794. X}
  795. X#endif
  796. X
  797. X/***************************************************/
  798. X/*  UNIX_Old dtime(). This is the old UNIX timer.  */
  799. X/*  Use only if absolutely necessary as HZ may be  */
  800. X/*  ill defined on your system.                    */
  801. X/***************************************************/
  802. X#ifdef UNIX_Old
  803. X#include <sys/types.h>
  804. X#include <sys/times.h>
  805. X#include <sys/param.h>
  806. X
  807. X#ifndef HZ
  808. X#define HZ 60
  809. X#endif
  810. X
  811. Xstruct tms tms;
  812. X
  813. Xdtime(p)
  814. Xdouble p[];
  815. X{
  816. X   double q;
  817. X
  818. X   q = p[2];
  819. X
  820. X   times(&tms);
  821. X
  822. X   p[2] = (double)(tms.tms_utime) / (double)HZ;
  823. X   p[1] = p[2] - q;
  824. X   
  825. X   return 0;
  826. X}
  827. X#endif
  828. X
  829. X/*********************************************************/
  830. X/*  VMS dtime() for VMS systems.                         */
  831. X/*  Provided by: RAMO@uvphys.phys.UVic.CA                */
  832. X/*  Some people have run into problems with this timer.  */
  833. X/*********************************************************/
  834. X#ifdef VMS
  835. X#include time
  836. X
  837. X#ifndef HZ
  838. X#define HZ 100
  839. X#endif
  840. X
  841. Xstruct tbuffer_t
  842. X       {
  843. X    int proc_user_time;
  844. X    int proc_system_time;
  845. X    int child_user_time;
  846. X    int child_system_time;
  847. X       };
  848. Xstruct tbuffer_t tms;
  849. X
  850. Xdtime(p)
  851. Xdouble p[];
  852. X{
  853. X   double q;
  854. X
  855. X   q = p[2];
  856. X
  857. X   times(&tms);
  858. X
  859. X   p[2] = (double)(tms.proc_user_time) / (double)HZ;
  860. X   p[1] = p[2] - q;
  861. X   
  862. X   return 0;
  863. X}
  864. X#endif
  865. X
  866. X/******************************/
  867. X/*  BORLAND C dtime() for DOS */
  868. X/******************************/
  869. X#ifdef BORLAND_C
  870. X#include <ctype.h>
  871. X#include <dos.h>
  872. X#include <time.h>
  873. X
  874. X#define HZ 100
  875. Xstruct time tnow;
  876. X
  877. Xdtime(p)
  878. Xdouble p[];
  879. X{
  880. X   double q;
  881. X
  882. X   q = p[2];
  883. X
  884. X   gettime(&tnow);
  885. X
  886. X   p[2] = 60.0 * (double)(tnow.ti_min);
  887. X   p[2] = p[2] + (double)(tnow.ti_sec);
  888. X   p[2] = p[2] + (double)(tnow.ti_hund)/(double)HZ;
  889. X   p[1] = p[2] - q;
  890. X   
  891. X   return 0;
  892. X}
  893. X#endif
  894. X
  895. X/**************************************/
  896. X/*  Microsoft C (MSC) dtime() for DOS */
  897. X/**************************************/
  898. X#ifdef MSC
  899. X#include <time.h>
  900. X#include <ctype.h>
  901. X
  902. X#define HZ CLK_TCK
  903. Xclock_t tnow;
  904. X
  905. Xdtime(p)
  906. Xdouble p[];
  907. X{
  908. X   double q;
  909. X
  910. X   q = p[2];
  911. X
  912. X   tnow = clock();
  913. X
  914. X   p[2] = (double)tnow / (double)HZ;
  915. X   p[1] = p[2] - q;
  916. X   
  917. X   return 0;
  918. X}
  919. X#endif
  920. X
  921. X/*************************************/
  922. X/*  Macintosh (MAC) Think C dtime()  */
  923. X/*************************************/
  924. X#ifdef MAC
  925. X#include <time.h>
  926. X
  927. X#define HZ 60
  928. X
  929. Xdtime(p)
  930. Xdouble p[];
  931. X{
  932. X   double q;
  933. X
  934. X   q = p[2];
  935. X
  936. X   p[2] = (double)clock() / (double)HZ;
  937. X   p[1] = p[2] - q;
  938. X   
  939. X   return 0;
  940. X}
  941. X#endif
  942. X
  943. X/************************************************************/
  944. X/*  iPSC/860 (IPSC) dtime() for i860.                       */
  945. X/*  Provided by: Dan Yergeau, yergeau@gloworm.Stanford.EDU  */
  946. X/************************************************************/
  947. X#ifdef IPSC
  948. Xextern double dclock();
  949. X
  950. Xdtime(p)
  951. Xdouble p[];
  952. X{
  953. X   double q;
  954. X
  955. X   q = p[2];
  956. X
  957. X   p[2] = dclock();
  958. X   p[1] = p[2] - q;
  959. X   
  960. X   return 0;
  961. X}
  962. X#endif
  963. X
  964. X/**************************************************/
  965. X/*  FORTRAN dtime() for Cray type systems.        */
  966. X/*  This is the preferred timer for Cray systems. */
  967. X/**************************************************/
  968. X#ifdef FORTRAN_SEC
  969. X
  970. Xfortran double second();
  971. X
  972. Xdtime(p)
  973. Xdouble p[];
  974. X{
  975. X   double q,v;
  976. X
  977. X   q = p[2];
  978. X
  979. X   second(&v);
  980. X   p[2] = v;
  981. X   p[1] = p[2] - q;
  982. X   
  983. X   return 0;
  984. X}
  985. X#endif
  986. X
  987. X/***********************************************************/
  988. X/*  UNICOS C dtime() for Cray UNICOS systems.  Don't use   */
  989. X/*  unless absolutely necessary as returned time includes  */
  990. X/*  'user+system' time.  Provided by: R. Mike Dority,      */
  991. X/*  dority@craysea.cray.com                                */
  992. X/***********************************************************/
  993. X#ifdef CTimer
  994. X#include <time.h>
  995. X
  996. Xdtime(p)
  997. Xdouble p[];
  998. X{
  999. X   double    q;
  1000. X   clock_t   t;
  1001. X
  1002. X       q = p[2];
  1003. X
  1004. X       t = clock();
  1005. X
  1006. X       p[2] = (double)t / (double)CLOCKS_PER_SEC;
  1007. X       p[1] = p[2] - q;
  1008. X
  1009. X       return 0;
  1010. X}
  1011. X#endif
  1012. X
  1013. X/********************************************/
  1014. X/* Another UNIX timer using gettimeofday(). */
  1015. X/* However, getrusage() is preferred.       */
  1016. X/********************************************/
  1017. X#ifdef GTODay
  1018. X#include <sys/time.h>
  1019. X
  1020. Xstruct timeval tnow;
  1021. X
  1022. Xdtime(p)
  1023. Xdouble p[];
  1024. X{
  1025. X   double q;
  1026. X
  1027. X   q = p[2];
  1028. X
  1029. X   gettimeofday(&tnow,NULL);
  1030. X   p[2] = (double)tnow.tv_sec + (double)tnow.tv_usec * 1.0e-6;
  1031. X   p[1] = p[2] - q;
  1032. X
  1033. X   return 0;
  1034. X}
  1035. X#endif
  1036. X
  1037. END_OF_FILE
  1038. if test 7335 -ne `wc -c <'mach.c'`; then
  1039.     echo shar: \"'mach.c'\" unpacked with wrong size!
  1040. fi
  1041. # end of 'mach.c'
  1042. fi
  1043. if test -f 'play.c' -a "${1}" != "-c" ; then 
  1044.   echo shar: Will not clobber existing file \"'play.c'\"
  1045. else
  1046. echo shar: Extracting \"'play.c'\" \(2236 characters\)
  1047. sed "s/^X//" >'play.c' <<'END_OF_FILE'
  1048. X/* internal move routines 
  1049. X   (c) 1992 John Tromp
  1050. X*/
  1051. X
  1052. X#include "c4.h"
  1053. X
  1054. X#define xdiabase   (xdias+6)
  1055. X#define odiabase   (odias+6)
  1056. X
  1057. Xstatic B8 linit = {7,6,5,4,0,3,2,1},
  1058. X          rinit = {4,7,6,5,3,2,1,0};
  1059. Xstatic uint8 msafe[43];
  1060. Xstatic uint8 four[128];
  1061. Xstatic uint16 xrows[8], orows[8], xdias[21], odias[21];
  1062. Xstatic uint8 initdias[21] = {0,0,0,1,2,3,5,6,7,0,0,0,1,2,3,5,6,7,0,0,0};
  1063. Xstatic uint8 typemask[8] = {0, 0x78, 0x7c, 0x7e, 0x7f, 0x3f, 0x1f, 0x0f};
  1064. Xstatic uint8 thrcols[1024];
  1065. X
  1066. Xint plycnt;
  1067. XB8 l, r, columns, height;
  1068. Xuint8 *moves = msafe+1;
  1069. Xuint8 xthrcnt[64],othrcnt[64],colthr[128];
  1070. X
  1071. Xvoid inithrcols()     /* compute threat columns */
  1072. X{
  1073. X  int i,j,m,t;
  1074. X
  1075. X  for (i = 0; i < 0x80; i++)
  1076. X    for (j = 0x80 | i; j >= 0x10; j >>= 1)
  1077. X      if ((j & 0xf) == 0xf) {
  1078. X        four[i] = 1;
  1079. X        break;
  1080. X      }
  1081. X  for (i = 0; i < 0x80; i++)
  1082. X    if (!four[i])                /* no 4 connected */
  1083. X      for (j = 1, m = 0x80; m >>= 1; j++)    /* try 4th stone */
  1084. X        if (four[i | m])            /* threat */
  1085. X          for (t = 1; t < 8; t++)        /* update relevant types */
  1086. X            if (typemask[t] & m)
  1087. X              thrcols[t << 7 | i] = thrcols[t << 7 | i] << 3 | j;
  1088. X}
  1089. X
  1090. Xvoid initcolthr()     /* compute column threats */
  1091. X{
  1092. X  int i;
  1093. X
  1094. X  for (i=0x8; i<0x40; i+=8) {
  1095. X    colthr[i] = 1;        /* threat for player2?! */
  1096. X    colthr[i+7] = 2;        /* threat for player1?! */
  1097. X  }
  1098. X}
  1099. X
  1100. Xvoid newgame()
  1101. X{
  1102. X  int i;
  1103. X
  1104. X  plycnt = 0;
  1105. X  for (i=0; i<21; i++)
  1106. X    xdias[i] = odias[i] = initdias[i] << 7;
  1107. X  for (i=0; i<8; i++) {
  1108. X    height[i] = 7*8 + i;
  1109. X    xrows[i] = orows[i] = 4 << 7;
  1110. X    columns[i] = 1;
  1111. X    l[i] = linit[i];
  1112. X    r[i] = rinit[i];
  1113. X  }
  1114. X  for (i=0; i<64; i++) {
  1115. X    othrcnt[i] = xthrcnt[i] = 0;
  1116. X  }
  1117. X}
  1118. X
  1119. Xvoid initplay()
  1120. X{
  1121. X  inithrcols();
  1122. X  initcolthr();
  1123. X  newgame();
  1124. X}
  1125. X
  1126. Xint depth(n)    /* returns 0 (full) through 6 (empty) */
  1127. Xint n;
  1128. X{
  1129. X  return (height[n]>>3) - 1;
  1130. X}
  1131. X
  1132. Xint haswon()
  1133. X{
  1134. X  if (plycnt < 7)
  1135. X    return 0;
  1136. X  return ((plycnt & 1) ? othrcnt : xthrcnt)[height[LASTMOVE]+8];
  1137. X}
  1138. X
  1139. X#define BACKMOV    backmovx
  1140. X#define MAKEMOV    makemovx
  1141. X#define ROWS    xrows
  1142. X#define DIABASE    xdiabase
  1143. X#define THRCNT    xthrcnt
  1144. X#define BIT
  1145. X#include "play.h"
  1146. X
  1147. X#define BACKMOV    backmovo
  1148. X#define MAKEMOV    makemovo
  1149. X#define ROWS    orows
  1150. X#define DIABASE    odiabase
  1151. X#define THRCNT    othrcnt
  1152. X#define BIT    | 1
  1153. X#include "play.h"
  1154. END_OF_FILE
  1155. if test 2236 -ne `wc -c <'play.c'`; then
  1156.     echo shar: \"'play.c'\" unpacked with wrong size!
  1157. fi
  1158. # end of 'play.c'
  1159. fi
  1160. if test -f 'play.h' -a "${1}" != "-c" ; then 
  1161.   echo shar: Will not clobber existing file \"'play.h'\"
  1162. else
  1163. echo shar: Extracting \"'play.h'\" \(1443 characters\)
  1164. sed "s/^X//" >'play.h' <<'END_OF_FILE'
  1165. Xvoid BACKMOV()
  1166. X{
  1167. X  u_int mask,d,hi,h;
  1168. X  int n,v;
  1169. X
  1170. X  n = moves[--plycnt];
  1171. X  if ((hi = height[n] += 8) < 24)
  1172. X    l[r[n]]=r[l[n]]=n;
  1173. X  h = hi>>3;
  1174. X  columns[n] >>= 1;
  1175. X  mask = ~(0x80 >> n);
  1176. X  ROWS[h] = (d = ROWS[h]) & mask;
  1177. X  if (v = thrcols[d]) {
  1178. X    --THRCNT[hi+((v&7)-n)];
  1179. X    if (v >>= 3)
  1180. X      --THRCNT[hi+(v-n)];
  1181. X  }
  1182. X  if (d = DIABASE[n+h]) {
  1183. X    DIABASE[n+h] = d & mask;
  1184. X    if (v = thrcols[d]) {
  1185. X      --THRCNT[hi-7*((v&7)-n)];
  1186. X      if (v >>= 3)
  1187. X        --THRCNT[hi-7*(v-n)];
  1188. X    }
  1189. X  }
  1190. X  if (d = DIABASE[n-h]) {
  1191. X    DIABASE[n-h] = d & mask;
  1192. X    if (v = thrcols[d]) {
  1193. X      --THRCNT[hi+9*((v&7)-n)];
  1194. X      if (v >>= 3)
  1195. X        --THRCNT[hi+9*(v-n)];
  1196. X    }
  1197. X  }
  1198. X}
  1199. X
  1200. Xvoid MAKEMOV(n) 
  1201. Xint n;
  1202. X{
  1203. X  u_int mask,d,hi,h;
  1204. X  int v;
  1205. X
  1206. X  moves[plycnt++] = n;
  1207. X  hi = height[n];
  1208. X  h = hi>>3;
  1209. X  if ((height[n] = hi-8) < 16)
  1210. X    l[r[l[n]]=r[n]]=l[n];
  1211. X  columns[n] = columns[n] << 1 BIT;
  1212. X  mask = 0x80 >> n;
  1213. X  d = ROWS[h] |= mask;
  1214. X  if (v = thrcols[d]) {
  1215. X    ++THRCNT[hi+((v&7)-n)];
  1216. X    if (v >>= 3)
  1217. X      ++THRCNT[hi+(v-n)];
  1218. X  }
  1219. X  if (d = DIABASE[n+h]) {
  1220. X    DIABASE[n+h] = d |= mask;
  1221. X    if (v = thrcols[d]) {
  1222. X      ++THRCNT[hi-7*((v&7)-n)];
  1223. X      if (v >>= 3)
  1224. X        ++THRCNT[hi-7*(v-n)];
  1225. X    }
  1226. X  }
  1227. X  if (d = DIABASE[n-h]) {
  1228. X    DIABASE[n-h] = d |= mask;
  1229. X    if (v = thrcols[d]) {
  1230. X      ++THRCNT[hi+9*((v&7)-n)];
  1231. X      if (v >>= 3)
  1232. X        ++THRCNT[hi+9*(v-n)];
  1233. X    }
  1234. X  }
  1235. X}
  1236. X
  1237. X#undef BACKMOV
  1238. X#undef MAKEMOV
  1239. X#undef ROWS
  1240. X#undef DIABASE
  1241. X#undef THRCNT
  1242. X#undef BIT
  1243. END_OF_FILE
  1244. if test 1443 -ne `wc -c <'play.h'`; then
  1245.     echo shar: \"'play.h'\" unpacked with wrong size!
  1246. fi
  1247. # end of 'play.h'
  1248. fi
  1249. if test -f 'trans.c' -a "${1}" != "-c" ; then 
  1250.   echo shar: Will not clobber existing file \"'trans.c'\"
  1251. else
  1252. echo shar: Extracting \"'trans.c'\" \(4179 characters\)
  1253. sed "s/^X//" >'trans.c' <<'END_OF_FILE'
  1254. X/* transposition table routines 
  1255. X   (c) 1992 John Tromp
  1256. X*/
  1257. X
  1258. X#include "c4.h"
  1259. X
  1260. X#define HTSIZE  1050011        /* not to be messed with:-) */
  1261. X#define HTD    (HTSIZE & 0xfffff)
  1262. X#define STRNG    (HTD/8)
  1263. X#define STD    (0x100-STRNG)
  1264. X#ifndef    PROBES
  1265. X#define PROBES    8
  1266. X#endif
  1267. X
  1268. Xstatic u_int *ht;            /* hash locks */
  1269. Xstatic hashentry *he;            /* hash entries */
  1270. Xstatic u_int stride;
  1271. Xstatic u_int htindex, lock, hits;
  1272. Xstatic u_int works[32];
  1273. Xstatic u_int typecnt[8];                /* bound type stats */
  1274. X
  1275. Xtypedef struct {
  1276. X  unsigned htmod:24;
  1277. X  unsigned stmod: 8;
  1278. X} mods;
  1279. X
  1280. Xstatic mods mulmod[0x402];
  1281. X
  1282. Xu_int posed;                /* counts transtore calls */
  1283. X
  1284. Xvoid inittrans()
  1285. X{
  1286. X  int i, htm, stm;
  1287. X
  1288. X  ht = allocate(HTSIZE,u_int);
  1289. X  he = allocate(HTSIZE,hashentry);
  1290. X  if (ht == NULL || he == NULL) {
  1291. X    printf("Out of memory; failed to allocate %d bytes.\n",
  1292. X       HTSIZE * (sizeof(u_int) + sizeof(hashentry)));
  1293. X    exit(0);
  1294. X  }
  1295. X
  1296. X  for (i = htm = stm = 0; i < 0x402; i++) {
  1297. X    mulmod[i].htmod = htm;
  1298. X    mulmod[i].stmod = stm;
  1299. X    if ((htm -= HTD) < 0)
  1300. X      htm += HTSIZE;
  1301. X    if ((stm += STD) >= STRNG)
  1302. X      stm -= STRNG;
  1303. X  }
  1304. X}
  1305. X
  1306. Xvoid emptyht()
  1307. X{
  1308. X  int i;
  1309. X
  1310. X  for (i=0; i<HTSIZE; i++)
  1311. X    if (he[i] < 0xf8)           /* leave book-entries intact */
  1312. X      he[i] &= 0x07;
  1313. X  posed = hits = 0;
  1314. X}
  1315. X
  1316. Xdouble hitrate()
  1317. X{
  1318. X  return posed ? (double)hits/(double)posed : 0.0;
  1319. X}
  1320. X
  1321. Xvoid hash(pos)
  1322. XB8 pos;
  1323. X{
  1324. X  register u_int htemp,stemp,t,t1,t2;
  1325. X
  1326. X  t1 = (pos[1] << 7 | pos[2]) << 7 | pos[3];
  1327. X  t2 = (pos[7] << 7 | pos[6]) << 7 | pos[5];
  1328. X  
  1329. X  if (t1 > t2) {
  1330. X    lock = (t1 << 7 | pos[4]) << 4 | t2 >> 17;
  1331. X    t = t2 & 0x7ffff;
  1332. X  } else {
  1333. X    lock = (t2 << 7 | pos[4]) << 4 | t1 >> 17;
  1334. X    t = t1 & 0x7ffff;
  1335. X  }
  1336. X  htemp = (lock >> 2 & 0xfffff) + mulmod[lock >> 22].htmod;
  1337. X  htemp = ((htemp & 0x7ff) << 9 | (t >> 10)) + mulmod[htemp >> 11].htmod;
  1338. X  if (htemp >= HTSIZE)
  1339. X    htemp -= HTSIZE;
  1340. X  htemp = ((htemp & 0x3ff) << 10 | (t & 0x3ff)) + mulmod[htemp >> 10].htmod;
  1341. X  htindex = htemp >= HTSIZE ? htemp - HTSIZE : htemp;
  1342. X  
  1343. X  stemp = (lock >> 16 & 0xff) + mulmod[lock >> 24].stmod;
  1344. X  stemp = (lock >>  8 & 0xff) + mulmod[stemp].stmod;
  1345. X  stemp = (lock       & 0xff) + mulmod[stemp].stmod;
  1346. X  if (stemp >= STRNG && (stemp -= STRNG) >= STRNG)
  1347. X    stemp -= STRNG;
  1348. X  stride = stemp + 0x20000;
  1349. X}
  1350. X
  1351. Xint transpose(pos)
  1352. XB8 pos;
  1353. X{
  1354. X  int i,x;
  1355. X
  1356. X  hash(pos);
  1357. X  for (x=htindex, i=0; i < PROBES; i++) {
  1358. X    if (ht[x] == lock)                /* CACHE MISS! */
  1359. X      return he[x];
  1360. X    if ((x += stride) >= HTSIZE)
  1361. X      x -= HTSIZE;
  1362. X  }
  1363. X  return 0;
  1364. X}
  1365. X
  1366. Xint transrestore(pos,score,work)
  1367. XB8 pos;
  1368. Xint score,work;
  1369. X{
  1370. X  register int i,x;
  1371. X
  1372. X  posed++;
  1373. X  hash(pos);
  1374. X  for (x=htindex, i=0; i < PROBES; i++) {
  1375. X    if (ht[x] == lock) {               /* CACHE MISS! */
  1376. X      hits++;
  1377. X      he[x] = work << 3 | score;
  1378. X      return 1;
  1379. X    }
  1380. X    if ((x += stride) >= HTSIZE)
  1381. X      x -= HTSIZE;
  1382. X  }
  1383. X  for (x=htindex, i=0; i < PROBES; i++) {
  1384. X    if (work > WORK(he[x])) {
  1385. X      hits++;
  1386. X      ht[x] = lock;
  1387. X      he[x] = work << 3 | score;
  1388. X      return 1;
  1389. X    }
  1390. X    if ((x += stride) >= HTSIZE)
  1391. X      x -= HTSIZE;
  1392. X  }
  1393. X  return 0;         /* not good enough to replace existing entries */
  1394. X}
  1395. X
  1396. Xint transtore(pos,score,work)
  1397. XB8 pos;
  1398. Xint score,work;
  1399. X{
  1400. X  register int i,x;
  1401. X
  1402. X  posed++;
  1403. X  hash(pos);
  1404. X  for (x=htindex, i=0; i < PROBES; i++) {
  1405. X    if (work > WORK(he[x])) {
  1406. X      hits++;
  1407. X      ht[x] = lock;
  1408. X      he[x] = work << 3 | score;
  1409. X      return 1;
  1410. X    }
  1411. X    if ((x += stride) >= HTSIZE)
  1412. X      x -= HTSIZE;
  1413. X  }
  1414. X  return 0;         /* not good enough to replace existing entries */
  1415. X}
  1416. X
  1417. Xdouble rate(S)
  1418. Xint S;
  1419. X{
  1420. X  u_int total;
  1421. X  int i;
  1422. X
  1423. X  for (total=i=0; i<8; i++)
  1424. X    total += typecnt[i];
  1425. X  return total ? (double)typecnt[S]/(double)total : 0.0;
  1426. X}
  1427. X
  1428. Xvoid htstat()      /* some statistics on hash table performance */
  1429. X{
  1430. X  int i;
  1431. X
  1432. X  for (i=0; i<32; i++)
  1433. X    works[i] = 0;
  1434. X  for (i=0; i<8; i++)
  1435. X    typecnt[i] = 0;
  1436. X  for (i=0; i<HTSIZE; i++) {
  1437. X    works[WORK(he[i])]++;
  1438. X    if (WORK(he[i]))
  1439. X      typecnt[SCORE(he[i])]++;
  1440. X  }
  1441. X  (void)printf("store rate = %.3f\n",hitrate());
  1442. X  (void)printf("- %5.3f  < %5.3f  = %5.3f  > %5.3f  + %5.3f\n",
  1443. X            rate(WIN2),rate(DRIN2),rate(DRAW),rate(DRIN1),rate(WIN1));
  1444. X  for (i=0; i<32; i++)
  1445. X    (void)printf("%6u%c",works[i],(i&7)==7?'\n':'\t');
  1446. X}
  1447. END_OF_FILE
  1448. if test 4179 -ne `wc -c <'trans.c'`; then
  1449.     echo shar: \"'trans.c'\" unpacked with wrong size!
  1450. fi
  1451. # end of 'trans.c'
  1452. fi
  1453. echo shar: End of shell archive.
  1454. exit 0
  1455.