黑白棋回溯算法及论文

•Alpha-Beta剪枝(Alpha-Beta pruning) 对于一般的最大最小搜索，即使每一步只有很少的下法，搜索的位置也会增长非常快；在大多数的中局棋形中，每步平均有十个位置可以下棋，于是假设搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，极大地限制了电脑的棋力。于是采用了一个方法，叫“alpha-beta剪枝”，它大为减少了检测的数目，提高电脑搜索的速度。各种各样的这种算法用于所有的强力Othello程序。(同样用于其他棋类游戏，如国际象棋和跳棋)。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。 •估值 这是一个程序中最重要的部分，如果这个模块太弱，则就算算法再好也没有用。我将要叙述三种不同的估值函数范例。我相信，大多数的Othello程序都可以归结于此。 棋格表：这种算法的意思是，不同的棋格有不同的值，角的值大而角旁边的格子值要小。忽视对称的话，棋盘上有10个不同的位置，每个格子根据三种可能性赋值：黑棋、白棋和空。更有经验的逼近是在游戏的不同阶段对格子赋予不同的值。例如，角在开局阶段和中局开始阶段比终局阶段更重要。采用这种算法的程序总是很弱(我这样认为)，但另一方面，它很容易实现，于是许多程序开始采用这种逼近。 基于行动力的估值：这种更久远的接近有很强的全局观，而不像棋格表那样局部化。观察表明，许多人类玩者努力获得最大的行动力(可下棋的数目)和潜在行动力(临近对手棋子的空格，见技巧篇)。如果代码有效率的话，可以很快发现，它们提高棋力很多。 基于模版的估值 ：正如上面提及的，许多中等力量的程序经常合并一些边角判断的知识，最大行动力和潜在行动力是全局特性，但是他们可以被切割成局部配置，再加在一起。棋子最少化也是如此。这导致了以下的概括：在估值函数中仅用局部配置(模版)，这通常用单独计算每一行、一列、斜边和角落判断，再加在一起来实现。 估值合并：一般程序的估值基于许多的参数，如行动力、潜在行动力、余裕手、边角判断、稳定子。但是怎么样将他们合并起来得到一个估值呢？一般采用线性合并。设a1，a2，a3，a4为参数，则估值s：=n1*a1+n2*a2+n3*a3+n4*a4。其中n1，n2，n3，n4为常数，术语叫“权重”(weight)，它决定了参数的重要性，它们取决于统计值。

/**********************************************/
/*               黑白棋源代码                 */
/*              TC2.0下运行通过               */
/*         采用深度搜索边角权值算法           */
/**********************************************/
# include 
# include 
# include 
# include 
# include 
# include 

# define BGCOLOR		  1    /* 背景颜色*/
# define COLOR_WHITECHESS 0    /*白棋棋子的颜色*/
# define COLOR_BLACKCHESS 15   /*黑棋棋子的颜色*/
# define COLOR_LINE 	  15   /*棋盘线的颜色*/
# define MINBOXSIZE       30   /*棋盘每一格边长*/
# define MAXSIZE          300  /*棋盘的大小 （1+8+1）*25 */
# define SCCOL            50   /*棋盘左上角的坐标*/
# define SCROW            60

# define VK_LEFT   0x4b00		/* 按键码*/
# define VK_RIGHT  0x4d00
# define VK_DOWN   0x5000
# define VK_UP     0x4800
# define VK_SPACE  0x3920
# define VK_ESC    0x011b

# define MAX_TREE_SIZE 15
# define INF		   1000

int TREE_LEVEL=7;
int empty_num=0;
int num_user=2;              /*得分统计*/
int num_computer=2;
int gbwzc=5gbwzr=5;         /*光标的初始位置*/
int present_p_v[10][10];     /*当前格的位置及其权值*/
char again=‘0‘;              /*用来判断游戏是否需要重新开始*/

int l=0k=0;

/*初始棋盘布局*/
int gril[10][10]=
    {{0000000000}
     {0000000000}
     {0000000000}
     {0000000000}
     {0000120000}
     {0000210000}
     {0000000000}
     {0000000000}
     {0000000000}
     {0000000000}
    };
/*初始棋盘权值*/
int gril_value[10][10]=
    {{0000000000}
     {076-49159915-49760}
     {0-49-494444-49-490}
     {015484484150}
     {0944444490}
     {0944444490}
     {015484484150}
     {0-49-494444-49-490}
     {076-49159915-49760}
     {0000000000}
    };
/*************************************************************/
/****************用到的汉字***********************************/
char zuo16S[]={
/* 以下是 ‘左‘ 的 16点阵宋体 字模，32 byte */
  0x020x000x030x000x020x000xFF0xFE
  0x020x000x020x000x040x000x040x00
  0x0F0xF80x080x800x100x800x100x80
  0x200x800x400x800xBF0xFE0x000x00
};

char you16S[]={
/* 以下是 ‘右‘ 的 16点阵宋体 字模，32 byte */
  0x020x000x020x000x020x000xFF0xFE
  0x040x000x040x000x080x000x180x00
  0x2F0xF80x480x080x880x080x080x08
  0x080x080x0F0xF80x080x080x000x00
};

char shang16S[]={
/* 以下是 ‘上‘ 的 16点阵宋体 字模，32 byte */
  0x000x000x010x000x010x000x010x00
  0x010x000x010x000x010xF80x010x00
  0x010x000x010x000x010x000x010x00
  0x010x000x010x040x7F0xFE0x000x00
};

char xia16S[]={
/* 以下是 ‘下‘ 的 16点阵宋体 字模，32 byte */
  0x000x040x7F0xFE0x010x000x010x00
  0x010x000x010xC00x010x600x010x30
  0x010x200x010x000x010x000x010x00
  0x010x000x010x000x010x000x000x00
};

char yi16S[]={
/* 以下是 ‘移‘ 的 16点阵宋体 字模，32 byte */
  0x0C0x400x7

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      90112  2005-06-16 09:58  中英文翻译.doc

     文件       5363  1988-08-29 10:00  EGAVGA.BGI

     文件      30517  2005-06-15 14:25  final.c

     文件      45909  2005-06-15 14:25  FINAL.EXE

     文件      24685  2005-06-01 09:34  Test15.c

     文件     561664  2005-06-14 07:27  回溯算法及其基本应用.ppt

     文件      24064  2005-06-16 09:59  回溯算法及其基本应用的文献综述.doc

     文件    3307520  2005-06-16 11:42  论文正文.doc

----------- ---------  ---------- -----  ----

              4089834                    8