home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Games / reve / rev_ip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  16.2 KB  |  585 lines
  1.  
  2. /*  @(#)rev_ip.c 1.14 91/11/07
  3.  *
  4.  *  Copyright (C) 1990, 1991 - Yves Gallot - all rights reserved.
  5.  *
  6.  *  Permission is granted to copy this source, for redistribution
  7.  *  in source form only, provided the news headers in "substantially
  8.  *  unaltered format" are retained, the introductory messages are not
  9.  *  removed, and no monies are exchanged.
  10.  *
  11.  *  Permission is also granted to copy this source, without the
  12.  *  news headers, for the purposes of making an executable copy by
  13.  *  means of compilation, provided that such copy will not be used
  14.  *  for the purposes of competition in any othello tournaments, without
  15.  *  prior permission from the authors.
  16.  *
  17.  *  No responsibility is taken for any errors on inaccuracies inherent
  18.  *  either to the comments or the code of this program, but if reported
  19.  *  (see README file), then an attempt will be made to fix them.
  20.  */
  21.  
  22. #include <stdio.h>
  23. #include <signal.h>
  24. #include <setjmp.h>
  25. #include <sys/types.h>
  26. #include "reve.h"
  27.  
  28. #define NOTE_DELTA  50
  29. #define INF        1000000000
  30.  
  31. #define max(x,y) ((x)>(y)?x:y)
  32. #define min(x,y) ((x)<(y)?x:y)
  33.  
  34. extern int debug ;
  35. extern int saveres ;
  36. extern time_t timeleft, time() ;
  37. extern int damier[NIVEAUMAX][64] ;
  38. extern int tacouleur, macouleur ;
  39. extern int mnb, profmax, max_depth ;
  40. extern long c1, c2, c3 ;
  41.  
  42. extern int node_count ;
  43. static int tot_node_count ;
  44. static int top_note ;        /* Best note found at top level of search */
  45.  
  46. /*  These global variables are only used in the play_reve routine. We place
  47.  *  them here as their values might otherwise be clobbered by some longjmp
  48.  *  implementations.
  49.  */  
  50. static int note, oldnote, oldnote2 ;
  51. static int oldprofmax, win_top, win_bot ;
  52.  
  53. /*  Reve structure. Play_Reve evaluates a board and returns a move and a note
  54.  *  for a given color.
  55.  *  It makes an interface between graphic variables and Reve heart variables.
  56.  *  It computes a timing function, depending on level used.
  57.  *  Then an Alpha-Beta pruning is called and stopped when no time left to Reve.
  58.  *  JePlonge and TuPlonges are typical F and G functions of an Alpha-Beta.
  59.  *  "Plonger dans un arbre" is the french translation of "to descend in a
  60.  *  tree", so I Descend and You Descend.
  61.  */
  62.  
  63. /*  Modified by Robert Cohen, 10 Jan 1991
  64.  *  Changed search list reordering to make the principal variation
  65.  *  of the previous iteration the first path tried at each level
  66.  *  of the iterative deepening search.
  67.  *  
  68.  *  Added aspiration using failsoft alpha-beta to search.
  69.  *  Now tries search window of oldnote +- NOTE_DELTA
  70.  */
  71.  
  72. static int cpiinit[60] = { 0, 0, 7, 7,
  73.                            2, 2, 5, 5, 2, 2, 3, 3,
  74.                            4, 4, 5, 5, 1, 1, 3, 3,
  75.                            4, 4, 6, 6, 1, 1, 2, 2,
  76.                            5, 5, 6, 6, 0, 0, 0, 0,
  77.                            2, 3, 4, 5, 2, 3, 4, 5,
  78.                            7, 7, 7, 7, 1, 1, 6, 6,
  79.                            0, 0, 1, 1, 6, 6, 7, 7
  80.                          } ;
  81.  
  82. static int cpjinit[60] = { 0, 7, 0, 7,
  83.                            2, 5, 2, 5, 3, 4, 2, 5,
  84.                            2, 5, 3, 4, 3, 4, 1, 6,
  85.                            1, 6, 3, 4, 2, 5, 1, 6,
  86.                            1, 6, 2, 5, 2, 3, 4, 5,
  87.                            0, 0, 0, 0, 7, 7, 7, 7,
  88.                            2, 3, 4, 5, 1, 6, 1, 6,
  89.                            1, 6, 0, 7, 0, 7, 1, 6
  90.                          } ;
  91.  
  92. /*  Total amount of time (in minutes) to allow, at this level of difficulty.
  93.  *  The time allocation function is not used at level 1.
  94.  */
  95.  
  96. static int timevals[MAXDIFF] = { 0, 1, 3, 5, 10, 15, 20, 30, 60 } ;
  97.  
  98. static int cpi[60], cpj[60], cpk[60], cpf[60] ;
  99. static int cpi2[60], cpj2[60], cpk2[60] ;
  100. static int cpmaxi[NIVEAUMAX][NIVEAUMAX] ;
  101.  
  102. static int locallevel = -1 ;
  103. static firsttime, timeused, allotime ;
  104.  
  105. jmp_buf jumper ;
  106.  
  107. static void catcher P(()) ;
  108.  
  109. static long jeplonge P((int, long, long)) ;
  110. static long tuplonges P((int, long, long)) ;
  111. extern long evalue P((int)) ;
  112.  
  113.  
  114. static void
  115. catcher()
  116. {
  117.   longjmp(jumper, 1) ;
  118. }
  119.  
  120.  
  121. int
  122. play_reve(board, color, level, rtnmv, rtnnote)
  123. int *board, color, level, *rtnmv ;
  124. long *rtnnote ;
  125. {
  126.   register int *d0, *d1 ;
  127.   register int k, cp ;
  128.   register int count ;
  129.   FILE *dp, *fp ;
  130.   int pass ;
  131.  
  132.   if (debug == TRUE)
  133.     if ((dp = fopen("reve.debug", "a")) == NULL)
  134.       debug = FALSE ;
  135.  
  136.   for (k = 0; k < 60; k++)
  137.     {
  138.       cpi[k] = cpiinit[k] ;
  139.       cpj[k] = cpjinit[k] ;
  140.       cpk[k] = 8 * cpi[k] + cpj[k] ;
  141.     }
  142.  
  143.   d0 = damier[0] ;
  144.   d1 = damier[1] ;
  145.  
  146.   for (k = 0; k < 64; k++)
  147.     {
  148.            if (board[k] == BLACK) d0[k] = BLACK ;
  149.       else if (board[k] == WHITE) d0[k] = WHITE ;
  150.       else                        d0[k] = FREE ;
  151.     }
  152.  
  153.   if (color == WHITE)
  154.     {
  155.       macouleur = WHITE ;
  156.       tacouleur = BLACK ;
  157.     }
  158.   else
  159.     {
  160.       macouleur = BLACK ;
  161.       tacouleur = WHITE ;
  162.     }
  163.  
  164.   if (jepeuxjouer(0) == FALSE)
  165.     {
  166.       *rtnmv = -1 ;
  167.       return ;
  168.     }
  169.  
  170.   mnb = 1 ;
  171.   for (k = 0; k < 64; k++)
  172.     if ((k != 27) && (k != 28) && (k != 35) && (k != 36))
  173.       if ((d0[k] == WHITE) || (d0[k] == BLACK))
  174.         {
  175.           mnb++ ;
  176.           cp = 0 ;
  177.           while (cpk[cp] != k) cp++ ;
  178.           for ( ; cp < 59; cp++)
  179.             {
  180.               cpi[cp] = cpi[cp + 1] ;
  181.               cpj[cp] = cpj[cp + 1] ;
  182.               cpk[cp] = cpk[cp + 1] ; 
  183.             }
  184.         }
  185.  
  186.   if ((locallevel != level) || (mnb == 1) || (mnb == 2))
  187.     {
  188.       timeleft = timevals[level-1] * 60 ;
  189.       locallevel = level ;
  190.     }
  191.  
  192.   k = 0 ;
  193.   for (cp = 0; cp <= 60 - mnb; cp++)
  194.     if (d0[cpk[cp]] == JPJ) k++ ;
  195.  
  196.   count = note = 0 ;
  197.   timeused = 1 ;
  198.   profmax = max_depth - 1 ;
  199.  
  200.   if (((k == 1) && (mnb < 52)) || (mnb == 1))
  201.     {
  202.       for (cp = 0; d0[cpk[cp]] != JPJ; cp++) continue ;
  203.       cpi[0] = cpi[cp] ;
  204.       cpj[0] = cpj[cp] ;
  205.       cpk[0] = cpk[cp] ;
  206.     }
  207.   else if (mnb == 2)
  208.     {
  209.       if (d0[2 * 8 + 3] == BLACK)
  210.         {
  211.           cpi[0] = 4 ;
  212.           cpj[0] = 2 ;
  213.         }
  214.       else if (d0[3 * 8 + 2] == BLACK)
  215.         {
  216.           cpi[0] = 2 ;
  217.           cpj[0] = 4 ;
  218.         }
  219.       else if (d0[4 * 8 + 5] == BLACK)
  220.         {
  221.           cpi[0] = 5 ;
  222.           cpj[0] = 3 ;
  223.         }
  224.       else if (d0[5 * 8 + 4] == BLACK)
  225.         {
  226.           cpi[0] = 3 ;
  227.           cpj[0] = 5 ;
  228.         }
  229.       cpk[0] = cpi[0] * 8 + cpj[0] ;
  230.     }
  231.   else if (mnb == 3)
  232.     {
  233.       if (d0[4 * 8 + 2] == WHITE)
  234.         {
  235.           cpi[0] = 5 ;
  236.           cpj[0] = 3 ;
  237.         }
  238.       else if (d0[2 * 8 + 2] == WHITE)
  239.         {
  240.           cpi[0] = 3 ;
  241.           cpj[0] = 2 ;
  242.         }
  243.       else if (d0[2 * 8 + 4] == WHITE)
  244.         {
  245.           cpi[0] = 3 ;
  246.           cpj[0] = 5 ;
  247.         }
  248.       cpk[0] = cpi[0] * 8 + cpj[0] ;
  249.     }
  250.   else
  251.     {
  252.       allotime = timeleft * 4 / (61 - mnb) ;
  253.       firsttime = time((time_t *) NULL) ;
  254.       tot_node_count = 0 ;
  255.       pass = 0 ;
  256.  
  257.       win_top = win_bot = oldnote = oldprofmax = 0 ;
  258.  
  259.       SIGNAL(SIGALRM, catcher) ;
  260.  
  261.       if (setjmp(jumper) != 0)
  262.         {
  263.           if (debug)
  264.             {
  265.               FPRINTF(dp, "%d nodes visited when interrupted", node_count) ;
  266.               FPRINTF(dp, " at ply %d, note = %d\n", profmax, top_note) ;
  267.             }
  268.           tot_node_count += node_count ;
  269.  
  270.           if (top_note <= win_bot || top_note >= win_top)
  271.             {
  272.  
  273. /*  Didn't find move at this level so restore principal variation from
  274.  * last level.
  275.  */
  276.               if (debug)
  277.                 FPRINTF(dp, "no valid move found in window %d - %d\n",
  278.                         win_bot, win_top) ;
  279.               note = oldnote ;
  280.               profmax = oldprofmax ;
  281.               for (k = 0; k < profmax; k++)
  282.                 {
  283.                   cpi[k] = cpi2[k] ;
  284.                   cpj[k] = cpj2[k] ;
  285.                   cpk[k] = cpk2[k] ;
  286.                 }
  287.             }
  288.           else
  289.             {
  290.  
  291. /* Copy from principal variation into cpi... */
  292.  
  293.               for (k = 0; k < profmax; k++)
  294.                 {
  295.                   cpi2[k] = cpi[cpmaxi[0][k]] ;
  296.                   cpj2[k] = cpj[cpmaxi[0][k]] ;
  297.                   cpk2[k] = cpk[cpmaxi[0][k]] ;
  298.                 }
  299.               for (k = 0; k < profmax; k++)
  300.                 {
  301.                   cpi[k] = cpi2[k] ;
  302.                   cpj[k] = cpj2[k] ;
  303.                   cpk[k] = cpk2[k] ;
  304.                 }
  305.               profmax = -profmax ;
  306.               note = top_note ;
  307.             }
  308.           goto trap ;
  309.         }
  310.  
  311.       do
  312.         {
  313.           oldnote2 = oldnote ;
  314.           oldnote = note ;
  315.           oldprofmax = profmax ;
  316.           top_note = -INF ;
  317.           node_count = 0 ;
  318.  
  319.           if ((int) (allotime - timeused) > 2)
  320.             ALARM((unsigned) (allotime - timeused)) ;
  321.  
  322.           profmax++ ;
  323.           pass++ ;
  324.  
  325.           c1 = 312 + 6 * (mnb + profmax - 1) ;
  326.           if (mnb + profmax - 1 < 25)
  327.             c2 = 50 + 2 * (mnb + profmax - 1) ;
  328.           else
  329.             c2 = 75 + mnb + profmax - 1 ;
  330.           c3 = 99 ;
  331.  
  332.           if (profmax > 53 - mnb)
  333.             {
  334.               profmax = 61 - mnb ;
  335.               allotime = timeleft * 2 / 3 ;
  336.               if ((int) (allotime - timeused) > 2)
  337.                 ALARM((unsigned) (allotime - timeused)) ;
  338.             }
  339.  
  340.           if (pass > 2 && profmax < 61 - mnb)
  341.             {
  342.  
  343. /* Use aspiration search */
  344.  
  345.               if (abs(oldnote2) < NOTE_DELTA * 2)
  346.                 {
  347.                   win_bot = oldnote2 - NOTE_DELTA ;
  348.                   win_top = oldnote2 + NOTE_DELTA ;
  349.                 }
  350.               else
  351.                 {
  352.                   win_bot = min(oldnote2 * 1.5, oldnote2 / 2) ;
  353.                   win_top = max(oldnote2 * 1.5, oldnote2 / 2) ;
  354.                 }
  355.               note = jeplonge(0, win_bot, win_top) ;
  356.               if (note >= win_top)
  357.                 {
  358.                   if (debug)
  359.                     {
  360.                       FPRINTF(dp, "failing high, note = %d, ", note) ;
  361.                       FPRINTF(dp, "win top = %d, wasted nodes visited = %d\n",
  362.                               win_top, node_count) ;
  363.                     }
  364.                   win_top = INF ;
  365.                   win_bot = note ;
  366.                   top_note = -INF ;
  367.                   note = jeplonge(0, win_bot, win_top) ;
  368.                 }
  369.               else if (note <= win_bot)
  370.                 {
  371.                   if (debug)
  372.                     {
  373.                       FPRINTF(dp, "failing low, note = %d, ", note) ;
  374.                       FPRINTF(dp, "win bot = %d, wasted nodes visited = %d\n",
  375.                               win_bot, node_count) ;
  376.                     }
  377.                   win_bot = -INF ;
  378.                   win_top = note ;
  379.                   top_note = -INF ;
  380.                   note = jeplonge(0, win_bot, win_top) ;
  381.                 }
  382.             }
  383.           else
  384.             {
  385.               win_bot = -INF ;
  386.               win_top = INF ;
  387.               note = jeplonge(0, win_bot, win_top) ;
  388.             }
  389.  
  390.           ALARM(0) ;
  391.           if (cpmaxi[0][0] == 0) count += 2 ;
  392.           else            count = 1 ;
  393.  
  394.           for (cp = 0; cp <= 60 - mnb; cp++) cpf[cp] = TRUE ;
  395.           for (k = 0; k < profmax; k++)
  396.              {
  397.                cpi2[k] = cpi[cpmaxi[0][k]] ;
  398.                cpj2[k] = cpj[cpmaxi[0][k]] ;
  399.                cpk2[k] = cpk[cpmaxi[0][k]] ;
  400.                cpf[cpmaxi[0][k]] = FALSE ;
  401.              }
  402.            k = profmax ;
  403.            for (cp = 0; cp <= 60 - mnb; cp++)
  404.              if (cpf[cp] == TRUE)
  405.                {
  406.                  cpi2[k] = cpi[cp] ;
  407.                  cpj2[k] = cpj[cp] ;
  408.                  cpk2[k] = cpk[cp] ;
  409.                  k++ ;
  410.                }
  411.            for (cp = 0; cp <= 60 - mnb; cp++)
  412.              {
  413.                cpi[cp] = cpi2[cp] ;
  414.                cpj[cp] = cpj2[cp] ;
  415.                cpk[cp] = cpk2[cp] ;
  416.              }
  417.  
  418.           timeused = time((time_t *) NULL) - firsttime ;
  419.           if (debug)
  420.             {
  421.               FPRINTF(dp, "%d nodes visited at ply %d,", node_count, profmax) ;
  422.               FPRINTF(dp, " window %0.4g - %0.4g,",
  423.                       (float) win_bot, (float) win_top) ;
  424.               FPRINTF(dp, " note = %d, best move = <%c-%c>\n",
  425.                       note, 'A' + cpj[0], '1' + cpi[0]) ;
  426.             }
  427.           tot_node_count += node_count ;
  428.           if ((mnb == 4) && (profmax > 2)) break ;
  429.         }
  430.       while ((timeused * count < allotime * 4 / 5) && (profmax != 61 - mnb)) ;
  431.  
  432. trap:
  433.  
  434.       timeused = time((time_t *) NULL) - firsttime ;
  435.       if (timeused == 0) timeused = 1 ;
  436.  
  437.       if (debug)
  438.         {
  439.           FPRINTF(dp, "total nodes visited was %d, time used was %d secs,",
  440.                   tot_node_count, timeused) ;
  441.           FPRINTF(dp, " %d nodes/sec\n", tot_node_count / timeused) ;
  442.           FPRINTF(dp, "alloc'ed time was %d, time left = %d\n",
  443.                   allotime, timeleft - timeused);
  444.           FPRINTF(dp, "best move sequence: ") ;
  445.           for (k = 0; k < abs(profmax); k++)
  446.             FPRINTF(dp, "<%c-%c>, ", 'A' + cpj[k], '1' + cpi[k]) ;
  447.           FPRINTF(dp, "\n") ;
  448.         }
  449.     }
  450.  
  451.   if (*rtnmv == TRUE) timeleft -= timeused ;
  452.   if ((int) timeleft < 0) timeleft = 0 ;
  453.  
  454.   if (saveres)
  455.     {
  456.       if ((mnb == 1) || (mnb == 2))
  457.         {
  458.           fp = fopen("reve.res", "w") ;
  459.           FPRINTF(fp, "\n") ;
  460.           FCLOSE(fp) ;
  461.         }
  462.       fp = fopen("reve.res", "a") ;
  463.       FPRINTF(fp, "%2d, <%c-%c>, ", mnb, 'A' + cpj[0], '1' + cpi[0]) ;
  464.       FPRINTF(fp, "nt : %5d, pmax : %3d, tmleft : %d, level : %d, ",
  465.                note,     profmax,    timeleft, level) ;
  466.       FPRINTF(fp, "exp : <%c-%c>\n", 'A' + cpj[1], '1' + cpi[1]) ;
  467.       FCLOSE(fp) ;
  468.     }
  469.  
  470.   *rtnmv = cpk[0] ;
  471.   *rtnnote = note ;
  472.   if (debug) FCLOSE(dp) ;
  473. }
  474.  
  475.  
  476. /*  If interrupted, global variables top_note contains the best note
  477.  *  found, cpmaxi[0] contains the principal variation.
  478.  */
  479.  
  480. static long
  481. jeplonge(niv, alpha, beta)
  482. int niv ;
  483. long alpha, beta ;
  484. {
  485.   register int *d0, *d1 ;
  486.   register int k, cp ;
  487.   register long lnote, note ;
  488.   int atime;
  489.  
  490.   d0 = damier[niv] ;
  491.   d1 = damier[niv + 1] ;
  492.  
  493.   note = -INF ;
  494.  
  495.   for (cp = 0; cp <= 60 - mnb; cp++)
  496.     {
  497.       if (d0[cpk[cp]] == JPJ)
  498.         {
  499. #ifdef hp9000s300                
  500.           for (k = 0; k < 64; k++) damier[niv + 1][k] = damier[niv][k] ;
  501. #else
  502.           for (k = 0; k < 64; k++) d1[k] = d0[k] ;
  503. #endif
  504.           jejoueen(cpi[cp], cpj[cp], niv + 1) ;
  505.           if (niv == profmax - 1) lnote = evalue(niv + 1) ;
  506.           else if (tupeuxjouer(niv + 1) == TRUE)
  507.             lnote = tuplonges(niv + 1, max(note,alpha), beta) ;
  508.           else if (jepeuxjouer(niv + 1) == TRUE)
  509.             lnote = jeplonge(niv + 1, max(note,alpha), beta) ;
  510.           else
  511.             lnote = evalue(niv + 1) ;
  512.           if (lnote > note)
  513.             {
  514.               if (niv == 0)
  515.                 {
  516.                   atime = alarm(0) ;
  517.                   note = lnote ;
  518.                   for (k = niv + 1; k < profmax; k++)
  519.                     cpmaxi[niv][k] = cpmaxi[niv+1][k] ;
  520.                   cpmaxi[niv][niv] = cp ;
  521.                   top_note = note ;
  522.                   show_best(cpk[cp],note) ;
  523.                   ALARM(atime) ;
  524.                 }
  525.               else
  526.                 {
  527.                   note = lnote ;
  528.                   for (k = niv + 1; k < profmax; k++)
  529.                     cpmaxi[niv][k] = cpmaxi[niv+1][k] ;
  530.                   cpmaxi[niv][niv] = cp ;
  531.                 }
  532.             }
  533.           if (note >= beta) return note ;
  534.         }
  535.     }
  536.  
  537.   return note ;
  538. }
  539.  
  540.  
  541. static long
  542. tuplonges(niv, alpha, beta)
  543. int niv ;
  544. long alpha, beta ;
  545. {
  546.   register int *d0, *d1 ;
  547.   register int k, cp ;
  548.   register long lnote, note ;
  549.  
  550.   d0 = damier[niv] ;
  551.   d1 = damier[niv + 1] ;
  552.  
  553.   note = INF ;
  554.  
  555.   for (cp = 0; cp <= 60 - mnb; cp++)
  556.     {
  557.       if (d0[cpk[cp]] == TPJ)
  558.         {
  559. #ifdef hp9000s300                
  560.           for (k = 0; k < 64; k++) damier[niv + 1][k] = damier[niv][k] ;
  561. #else                            
  562.           for (k = 0; k < 64; k++) d1[k] = d0[k] ;
  563. #endif                           
  564.           tujouesen(cpi[cp], cpj[cp], niv + 1) ;
  565.           if (niv == profmax - 1) lnote = evalue(niv + 1) ;
  566.           else if (jepeuxjouer(niv + 1) == TRUE)
  567.             lnote = jeplonge(niv + 1, alpha, min(note,beta)) ;
  568.           else if (tupeuxjouer(niv + 1) == TRUE)
  569.             lnote = tuplonges(niv + 1, alpha, min(note,beta)) ;
  570.           else
  571.             lnote = evalue(niv + 1) ;
  572.           if (lnote < note)
  573.             {
  574.               note = lnote ;
  575.               for (k = niv + 1; k < profmax; k++)
  576.                 cpmaxi[niv][k] = cpmaxi[niv+1][k] ;
  577.               cpmaxi[niv][niv] = cp;
  578.             }
  579.           if (note <= alpha) return note ;
  580.         }
  581.     }
  582.  
  583.   return note ;
  584. }
  585.