先弄明白数据的结构：
创新互联建站主营济宁网站建设的网络公司,主营网站建设方案,成都app软件开发公司,济宁h5成都微信小程序搭建,济宁网站营销推广欢迎济宁等地区企业咨询
MantisChessDef.h里的东西一定要先看一下， 否则会摸不到头脑的。
还有棋盘坐标：
象棋棋盘大小9x10,为了便于编程，规定棋盘每条边留有一个元素的边界。
这样棋盘大小（包括边界）变成11x12。棋盘x坐标轴向右，y轴向下。
黑棋永远在上方，在标准开局时左上角的黑车坐标是（1，1）。
局面用这三个变量表示:
static POINT g_pointChessman[32]; //棋子坐标
static int g_iChessmanMap[11][12]; //棋位状态
static int g_iSide; //轮到哪方走
智能部分有几个函数的前三个参数就是这个东西, 应该不难理解吧?
---------------------------------------------------------------------------------------
search函数:
先说明一下， 经常有朋友问我要原理, 但我公开源代码是给大家一个参考， 而不是什么教程，所以我不想说那些理论的东西。
基本原理是α-β搜索， 很多人工智能的教科书上都有讲到， 没看过的的赶快去找一本来啃一啃；
虽然这些书上的文字大多晦涩难懂，但毕竟讲得明明白白。
没有书的朋友请发挥一下主观能动性， 去找一找，不要来问我要， 因为我也没有。
我在这里只分析一下search函数:
弄懂α-β搜索后来看看这个博弈树， 看怎么编程实现它。
先规定一下， 我们用一个整数表示局面的好坏.
这个数越大说明局面对 "走棋方" 越有利，0表示双方实力相等。
1a( 1) ┬ 2a(-1) ┬ 3a(-1)
│ └ 3b( 1)
└ 2b(-5) ┬ 3c( 2)
├ 3d(-4)
└ 3e( 5)
分析一下这棵树，有这么个特点: 父结点的值 = -MAX(子结点的值)
我们还知道1、每个结点对应一个局面。2、底层的结点的值是"估"出来的。
于是我们可以写出伪代码了:
伪代码: 搜索一个结点下的分支， 得到这个结点的值。
参数: 局面，搜索深度
返回值:结点的值
int search(局面，int depth)
{
if(depth!=0)//不是底层结点
{
枚举出所有子结点(列出所有走法);
int count=子结点数；
int maxvalue= -∞;
for(int i=0;icount;i++)//遍历所有结点
{
算出子结点局面;
maxvalue=max(maxvalue，search(子结点局面,depth-1));
}
return -maxvalue;
}
else //是底层结点
{
return 估计值;
}
}
这就是搜索算法的框架， 用到了递归。
MantisChess的智能部分函数都在MantisChessThink.cpp里， 其中search是搜索， 跟上面的这个search差不多，我把它copy出来注释一下：
int Search(int tmap[11][12],POINT tmanposition[32],int tside,int man, POINT point,int upmax,int depth)
{
//前面的三个参数就是局面。
//man 和point 是走法，用来计算本结点的局面。 这里是把计算局面放在函数的开头，跟上面的伪代码不太一样。
//upmax: up - 上一层， max - 最大值， 这是α-β的剪枝用到的东西， 后面再讲。
//depth: 搜索深度
int ate,cur,maxvalue,curvalue,xs,ys;
int count;
//#####################这一段是计算本结点的局面#########################################
ate=32;
//移动棋子:
xs=tmanposition[man].x;ys=tmanposition[man].y; //原坐标
if (SideOfMan[tmap[point.x][point.y]]==!tside) //目标点有对方的棋子
{
ate=tmap[point.x][point.y]; //记录下被吃掉的棋子
if(ate==0 || ate==16)
{
return 9999;
}
tmanposition[ate].x=0; //目标点的棋子被吃掉
}
tmap[point.x][point.y]=man; //这两行是:
tmap[xs][ys]=32; //在map上的移动
tmanposition[man]=point;
tside=!tside;
//####################################################################################
depth--;
if(depth0) //不是底层结点
{
int chessman[125];
POINT targetpoint[125];
if(EnumList(tmap,tmanposition,tside,chessman,targetpoint,count)) //枚举出所有子结点(列出所有走法)
{
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//这里是剪枝(不是α-β剪枝), 原理是在正式搜索之前先用较浅的搜索来得到误差较大的值
//然后根据这些值来对子结点排序， 只保留最好的S_WIDTH个结点进行正式搜索。
//显然，这个剪枝有一定的风险
if(depth=2 countS_WIDTH+2)
{
int value[125];
cur=0;
maxvalue=-10000;
while(cur count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],-10000,depth-2);
value[cur]=curvalue;
if(curvaluemaxvalue)maxvalue=curvalue;
cur ++;
}
::Mantis_QuickSort(value,chessman,targetpoint,0,count-1); //排序
count=S_WIDTH;//剪枝
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
maxvalue=-10000;
cur=0;
while(cur count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],maxvalue,depth);
if(curvaluemaxvalue)maxvalue=curvalue;
if(curvalue=-upmax)goto _ENDSUB; //α-β剪枝, 符合剪枝条件的就Cut掉。 这里用了goto语句了， 千万别学我。
cur ++;
}
}
else maxvalue=9800;
}
else //是底层结点
{
maxvalue=Value(tmap,tmanposition,tside); //估值
}
_ENDSUB:
//返回之前要恢复父结点的局面
//####################################################################################
tmanposition[man].x=xs; //这两行是:
tmanposition[man].y=ys; //在face上的恢复
tmap[xs][ys]=man; //在map上的恢复
if(ate!=32)
{
tmanposition[ate]=point;
tmap[point.x][point.y]=ate;
}
else tmap[point.x][point.y]=32;
tside=!tside;
//####################################################################################
return -maxvalue;
}
上面的代码用到了α-β剪枝, 举个例子就明白了:
还是这个博弈树，从上往下遍历。
1a( 1) ┳ 2a(-1) ┳ 3a(-1)
┃ ┗ 3b( 1)
┗ 2b(-5) ┯ 3c( 2)
├ 3d(-4)
└ 3e( 5)
2a遍历完后 upmax=-1, 继续遍历完3c后返回2b， 发现3c=2-upmax, 这时就不用管3d和3e了, 因为无论他们的值是多少 2b=-max(3c,3d,3e)2a 一定成立,
也就是说2b可以安全地剪掉。这就是α-β剪枝。
从上面的代码来看我的MantisChess算法与标准的α-β剪枝搜索并没有什么不同， 只不过加了排序和剪枝而已。
package com.plague.math;
import java.lang.Math;
public class Chess {
private final static int CHESS_NUMBER = 64;
private int total;
public Chess () {
System.out.println("国王的赏赐，其实，问题是这样的：" +
"在国际象棋的棋盘上，第一格放一粒米，第二格放2粒米，第三个放四粒米。。。最后国王要赏赐多少米");
for (int i = 0; i CHESS_NUMBER; i++) {
total += Math.pow(2.0,(double)i);
}
System.out.println("国王的赏赐是："+total);
}
public static void main(String[] args) {
Chess c1 = new Chess();
}
}
呵呵，开始我也觉得没有破绽，后来发现了软件也会出昏招。原来原理很简单，只是把基本的开局定式以及常见的对弈拆解局面转换成数据库函数，当出现数据库招数，便调出同类型的宏功能。说到底，只是电脑软件做到了更多的对弈棋局收集，把相关的招数进行了数码汇编。比如：仙人指路开局，软件就会自动把存储在数据库中的符合这一定式类型的所有函数自动调出，选择基本应招（根据用户选手游戏难度不同，软件也会选择相应招数致胜比率和复杂程度）。所以按一般局面和软件玩，就等于和一个熟读兵法的谋士作战，很难赢。你会有看不透，想不到的时候，软件按步就班，数据库就是它的眼睛和脑袋。但是编制软件的并不是一流大师，他们手头上有的都是找得到的棋局，但是棋盘千变万化，有很多招式不可能存在软件中，所以软件也会碰到出昏招的时候。我们可以做一个小实验，两台电脑玩相同的象棋游戏，如果以A电脑进行先手，B电脑进行后手，以B电脑的招式来和A电脑下。百分之九十九的机率是和棋。如果我们用自己的方式操作B电脑和A电脑进行至中局（有一方有多子优势），然后再让两台电脑自己下，肯定有一台电脑是输的。你就会发现输的电脑下的棋局很一般，因为它还是在以应对的形式开展，试问没有优势的情况下，那台数据库一样的电脑软件会出现奇招嘛？也就是说软件也是会输的。我记得国际象棋那个深蓝也输给过卡斯帕罗夫，然后那个更深的蓝赢了卡斯帕罗夫。还是赢在数据采集啊。
import java.awt.*;
import javax.swing.*;
public class Chessboard extends JApplet {
int baseXPosition, baseYPosition;
int currentXPosition, currentYPosition;
public void init() {
baseXPosition = 40; // 棋盘的开始x位置
baseYPosition = 40; // 棋盘的开始y位置
setBackground(Color.black); // 设置背景颜色黑色
}
public void paint(Graphics g) { // 绘制棋盘
currentXPosition = baseXPosition; // currentXPosition当前的x位置
currentYPosition = baseYPosition; // currentYPosition当前的y位置
for (int row = 0; row 8; row++) {
currentXPosition = baseXPosition + row * 40;
for (int column = 0; column 8; column++) {
if ((column + row) % 2 == 0)
g.setColor(Color.white); // 设置棋盘格子的颜色
else
g.setColor(Color.red); // 设置棋盘格子的颜色
currentYPosition = baseXPosition + column * 40;
g.drawRect(currentXPosition,currentYPosition,40,40);//;代码4 //在当前位置绘制棋盘的格子；每个格子的大小是40*40像
g.fillRect(currentXPosition,currentYPosition,40,40);
}
}
}
}
import java.awt.Color;
import javax.swing.*;
public class Chess extends JPanel
{// 继承面板类
public Chess(int grids,int gridsize)
{//grids:行数和列数, gridsize:单元格的高和宽
super(null);
for(int i=0; igrids; i++)
{
for(int j=0; jgrids; j++)
{
JLabel l = new JLabel();//生成标签实例
l.setSize(gridsize,gridsize);
l.setLocation(i*gridsize,j*gridsize);
if((i+j)%2==0)
{ //当小方格的坐标和刚好是偶数时，
l.setBackground(Color.black); //设置为方格为黑色
l.setOpaque(true); //设置为不透明
}
l.setBorder(BorderFactory.createLineBorder(Color.black)); //设置边界为黑色
add(l);//将l标签添加到面板
}
}
}
public static void main(String[] args)
{
JFrame f = new JFrame();
f.setSize(658,677); //边框的长和宽
f.setLocationRelativeTo(null); //设置窗口相对于指定组件的位置
f.add(new Chess(8,80));
f.setVisible(true);
}
}