home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / graphics / gdi / reversi / rev.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  8KB  |  329 lines
  1. //  THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF 
  2. //  ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO 
  3. //  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A 
  4. //  PARTICULAR PURPOSE.
  5. //
  6. //  Copyright (C) 1993-1997  Microsoft Corporation.  All Rights Reserved.
  7. //
  8. //  PROGRAM: Rev.c
  9. //
  10. //  PURPOSE: Helper functions for Reversi Sample Game
  11. //
  12. //  FUNCTIONS:
  13. //  finalscore() - Calculate final score
  14. //  legalcheck() - Return 1 if move legal, else return 0
  15. //  makemove() - Capture enemy pieces
  16. //  score() - Calculate the value of board
  17. //  minmax() - Play human move then recursively play computer move
  18. //
  19. //  SPECIAL INSTRUCTIONS: N/A
  20. //
  21. #include <windows.h>
  22. #include <windowsx.h>
  23. #include <process.h>
  24. #include <stdlib.h>
  25. #include "reversi.h"
  26.  
  27. // declarations of function in reversi.c
  28. VOID NEAR PASCAL paintmove(BYTE b[BoardSize], INT move, INT friendly,
  29.     INT enemy);
  30.  
  31. // variable declarations
  32. extern INT     moves[61];
  33. extern INT     BestMove[max_depth+2];
  34. extern HWND    hWin;
  35. extern HDC     hDisp;
  36. extern INT     depth;
  37. extern INT     direc[];
  38.  
  39.  
  40. //  Indexes for computing scores and whether or not a player has
  41. //  any pieces on the board.  Very order dependant.
  42.  
  43. BYTE PieceFlags[] = {   0x00 ,      // Ignore sides
  44.             0x00 ,      // Ignore blanks
  45.             0x01 ,      // Human has a piece
  46.             0x02 ,      // Computer has a piece
  47.             };
  48.  
  49.             
  50. //
  51. //  The scoring tables are used to evaluate the board
  52. //  position.  The corners of the board change value
  53. //  according to whether a given square is occupied or
  54. //  not.  This can be done dynamically, saving ~ 1K
  55. //  worth of data space but costing an as of yet
  56. //  undetermined performance hit.
  57. //
  58.  
  59. #define B11     11    // Offsets to particular squares
  60. #define B18     18 
  61. #define B81     81 
  62. #define B88     88 
  63.  
  64. #define maskb11     0x08    // Masks used for indexing into Scoring tables.
  65. #define maskb18     0x04
  66. #define maskb81     0x02
  67. #define maskb88     0x01
  68.  
  69.  
  70. //
  71. //  FUNCTION: finalscore()
  72. //
  73. //  PURPOSE:  Calculate final score
  74. //
  75.  
  76. INT NEAR PASCAL finalscore(
  77. BYTE b[],
  78. BYTE friendly,
  79. BYTE enemy)
  80. {
  81.     INT i;
  82.     INT count=0;
  83.  
  84.     for (i=11 ; i<=88 ; i++) {
  85.         if (b[i] == friendly)
  86.             count++;
  87.         else
  88.             if (b[i] == enemy)
  89.                 count--;
  90.     }
  91.     if (count > 0)
  92.         return(win + count);
  93.     else
  94.         if (count < 0)
  95.             return(loss + count);
  96.         else
  97.             return(0);
  98. }
  99.  
  100.  
  101. //
  102. //  FUNCTION: legalcheck()
  103. //
  104. //  PURPOSE:  Return 1 if move legal, else return 0
  105. //
  106.  
  107. INT NEAR PASCAL legalcheck(
  108. BYTE b[],
  109. INT move,
  110. BYTE friendly,
  111. BYTE enemy)
  112. {
  113.    INT sq,d;
  114.    INT *p;
  115.  
  116.    if (b[move] == empty) {
  117.       p=direc;
  118.       while ((d = *p++) != 0) {
  119.           sq=move;
  120.           if (b[sq += d] == enemy) {
  121.              while(b[sq += d] == enemy)
  122.             ;
  123.              if (b[sq] == friendly) return(1);
  124.           }
  125.       }
  126.    }
  127.    return(0);
  128. }
  129.  
  130.  
  131. //
  132. //  FUNCTION: makemove()
  133. //
  134. //  PURPOSE:  Capture enemy pieces
  135. //
  136.  
  137. VOID NEAR PASCAL makemove(
  138. BYTE b[],
  139. INT move,
  140. BYTE friendly,
  141. BYTE enemy)
  142. {
  143.    INT sq,d;
  144.    INT *p;
  145.  
  146.    if (move != PASS) {
  147.       p=direc;
  148.       while ((d = *p++) != 0) {
  149.           sq=move;
  150.           if (b[sq += d] == enemy) {
  151.             while(b[sq += d] == enemy)
  152.             ;
  153.             if (b[sq] == friendly)
  154.                 while(b[sq -= d] == enemy)
  155.                    b[sq]=friendly;
  156.           }
  157.       }
  158.       b[move]=friendly;
  159.    }
  160. }
  161.  
  162.  
  163. //
  164. //  FUNCTION: score()
  165. //
  166. //  PURPOSE:  Calculate the value of board
  167. //
  168.  
  169. INT NEAR PASCAL score(
  170. BYTE b[],
  171. BYTE friendly,
  172. BYTE enemy)
  173. {
  174.     INT *pvalue;
  175.     BYTE *pb;
  176.     INT fpoints=0;
  177.     INT epoints=0;
  178.     INT ecount=0;
  179.     BYTE bv;
  180.     INT v,b11,b18,b81,b88;
  181.  
  182.     static INT value[79] = {     99, -8,  8,  6,  6,  8, -8, 99,000,
  183.                 000, -8,-24, -4, -3, -3, -4,-24, -8,000,
  184.                 000,  8, -4,  7,  4,  4,  7, -4,  8,000,
  185.                 000,  6, -3,  4,  0,  0,  4, -3,  6,000,
  186.                 000,  6, -3,  4,  0,  0,  4, -3,  6,000,
  187.                 000,  8, -4,  7,  4,  4,  7, -4,  8,000,
  188.                 000, -8,-24, -4, -3, -3, -4,-24, -8,000,
  189.                 000, 99, -8,  8,  6,  6,  8, -8, 99,infin};
  190.  
  191.     static INT value2[79]= {     99, -8,  8,  6,  6,  8, -8, 99,000,
  192.                 000, -8,-24,  0,  1,  1,  0,-24, -8,000,
  193.                 000,  8,  0,  7,  4,  4,  7,  0,  8,000,
  194.                 000,  6,  1,  4,  1,  1,  4,  1,  6,000,
  195.                 000,  6,  1,  4,  1,  1,  4,  1,  6,000,
  196.                 000,  8,  0,  7,  4,  4,  7,  0,  8,000,
  197.                 000, -8,-24,  0,  1,  1,  1,-24, -8,000,
  198.                 000, 99, -8,  8,  6,  6,  8, -8, 99,infin};
  199.  
  200.     pb = &b[11];
  201.     b11 = *pb;
  202.     b18 = b[18];
  203.     b81 = b[81];
  204.     b88 = b[88];
  205.  
  206.     if ((b11 != empty) || (b18 != empty) || (b81 != empty) || (b88 != empty)) {
  207.     pvalue = value2;
  208.  
  209.     if (b11 == empty) {
  210.         value2[12-11] = -8;  value2[21-11] = -8;  value2[22-11] = -24;
  211.     } else {
  212.         value2[12-11] = 12;  value2[21-11] = 12;  value2[22-11] = 8;
  213.     }
  214.  
  215.     if (b18 == empty) {
  216.         value2[17-11] = -8;  value2[28-11] = -8;  value2[27-11] = -24;
  217.     } else {
  218.         value2[17-11] = 12;  value2[28-11] = 12;  value2[27-11] = 8;
  219.     }
  220.  
  221.     if (b81 == empty) {
  222.         value2[82-11] = -8;  value2[71-11] = -8;  value2[72-11] = -24;
  223.     } else {
  224.         value2[82-11] = 12;  value2[71-11] = 12;  value2[72-11] = 8;
  225.     }
  226.  
  227.     if (b88 == empty) {
  228.         value2[87-11] = -8;  value2[78-11] = -8;  value2[77-11] = -24;
  229.     } else {
  230.         value2[87-11] = 12;  value2[78-11] = 12;  value2[77-11] = 8;
  231.     }
  232.     } else {
  233.     pvalue = value;
  234.     }
  235.  
  236.     while((v=*pvalue++) != infin) {
  237.        bv = *pb++;
  238.        if (bv == friendly)
  239.        fpoints += v;
  240.        else if (bv == enemy) {
  241.            epoints += v;
  242.        ecount++;
  243.        }
  244.  
  245.     }
  246.     if (!ecount)          // any enemy pieces on the board?
  247.        return(win);       // if not, we just won!
  248.     else
  249.        return(fpoints-epoints);
  250. }
  251.  
  252.  
  253. //
  254. //  FUNCTION: minmax()
  255. //
  256. //  PURPOSE:  Play human move then recursively play computer move 
  257. //
  258.  
  259. INT NEAR PASCAL minmax(
  260. BYTE b[max_depth + 2][100],
  261. INT move,
  262. BYTE friendly,
  263. BYTE enemy,
  264. INT ply,
  265. INT vmin,
  266. INT vmax)
  267. {
  268.     BYTE *pCurrent, *pPrevious, *pSource, *pDest;
  269.     INT *pMoves;
  270.     INT *pBestMove;
  271.     INT i;
  272.     INT sq, value, cur_move;
  273.     INT count=0;    // not used !
  274.  
  275.     pPrevious = &b[ply][0];
  276.     pCurrent =  &b[ply+1][0];
  277.  
  278.     pSource = &b[ply][11];
  279.     pDest =   &b[ply+1][11];
  280.     for (i=11 ; i<=88 ; i++) *pDest++=*pSource++;
  281.  
  282.     pBestMove = &BestMove[ply];
  283.     if (move == PASS) {
  284.         if (ply == depth) {
  285.             pMoves = moves;
  286.             while((sq = *pMoves++) != 0) {
  287.                 if (legalcheck(pCurrent,sq,enemy,friendly))
  288.                     return(score(pCurrent,friendly,enemy));
  289.             }
  290.             return(finalscore(pCurrent,friendly,enemy));
  291.         }
  292.     }
  293.     else {
  294.         if (ply == 0) {
  295.             hDisp = GetDC(hWin);
  296.             paintmove(pCurrent,move,friendly,enemy);
  297.             ReleaseDC(hWin, hDisp);
  298.         }
  299.         else {
  300.             makemove(pCurrent,move,friendly,enemy);
  301.             if (ply == depth) return(score(pCurrent,friendly,enemy));
  302.         }
  303.     }
  304.     pMoves = moves;
  305.     cur_move = PASS;
  306.     *pBestMove = PASS;
  307.     while((sq = *pMoves++) != 0) {
  308.         if (legalcheck(pCurrent,sq,enemy,friendly)) {
  309.            cur_move = sq;
  310.            value = minmax(b,cur_move,enemy,friendly,ply+1,-vmax,-vmin);
  311.            if (value > vmin) {
  312.               vmin = value;
  313.               *pBestMove = cur_move;
  314.               if (value >= vmax) goto cutoff;   // alpha-beta cutoff
  315.            }
  316.         }
  317.     }
  318.     if (cur_move == PASS) {
  319.         if (move == PASS)        // two passes in a row mean game is over
  320.             return(finalscore(pCurrent,friendly,enemy));
  321.         else {
  322.             value = minmax(b,PASS,enemy,friendly,ply+1,-vmax,-vmin);
  323.             if (value > vmin) vmin = value;
  324.         }
  325.     }
  326. cutoff:
  327.     return(-vmin);
  328. }
  329.