民间棋类计算机博弈

民间棋类计算机博弃

徐心和徐长明

东北大学机舞博弃研究重

2007年7月

主要内＜

♦:♦什么是计算机悔弃r机赛博界）?

机器博弃的艰苦历程与辉煌成果

♦:♦氏同棋类计算机博界

——机器博弃的入门课

♦:♦计算机是如何实现博弃过程的？

♦:♦机器博弃的技术构成与内涵

♦:♦开梭机器博弃活动的意义与展篁

东北大学机器博弈研究室

什么是计算机博弈?

讨算机博弃，机器悔界

ComputerGames

主要是指计算机下棋、航牌

----像人一样的思维

景先提出的就是计算机下

国际象棋、勒婵的棋等各种棋类

东北大学机器博弈研究室

机器博弈是一个特殊的研究领域

♦:♦它是非常实际的计算机科学与技术的研究课题

♦:♦它是非常畲于挑战性的人工智能领域的研究方向

♦:♦它来不得任何理想化和虚假成分

♦:♦它是现代博弃论所不能斛决的动态博弃技术

♦:♦它是需求牵引的典型课题，具有很强的泛化能力

1为它是人工智能的基本问题

。它具有广阔的应用前景——对策问题

（控制，决策、对策）

东北大学机器博弈研究室

机器博弈的艰苦历程与辱煌成果

国际象棋——

❖景先提出的计算机应用课题之一

❖计算机前聚所关注的研究课题

❖半个世纪的艰苦拼砂

❖IBM深蓝的辉煌业绩

❖继续向新的高峰攀誉

东北大学机器博弈研究室

追寻历史的踪迹

♦:*1946年第一台电子计算机

问世于美国。

冯・诺依曼

g教学家

g计算机之父

g提出极大极小定理

g为除征机器的正确性和性能，

首先为它编写了象棋程序

东北大学机器博弈研究室

«Programmingacomputerforplayingchess》,

Shannon,1950

♦“用极大极小值算法可以找到想下的棋,

但由于这个游戏的变化太多，不可能披奈

到终结点，所以就要寻找一种合逡的方法

只技奈部分节点，然后就可以到新该走哪

步棋，进而走棋”

♦：♦现代计算机博弃的理论基础

东北大学机器博弈研究室

许多人在努力

东北大学机器博弈研究室

他们来自于何方？

❖Canada、America、England、China、

Japan>Holland>Mexico....

UniversityofAlberta,Universityof

Wisconsin,UniversityofMaryland,

MIT,UniversityofTokyo,University

ofAlbama,UniversityofCalifornia,

ErasmusUniversity,Cambrige

University.......

东北大学机器博弈研究室

世纪之战

8深蓝之父

61997年深蓝战触

卡斯帕罗夫

东北大学机器博弈研究室

东北大学机器博弈研究室

电脑棋手：永不停歇的挑战!

♦2001年“更弗里茨”击败了除了克拉

姆尼克之外的所有排名世界前十佳的

棋手。

♦:BOOZ年10月“更弗里茨”与世界棋王

克拉姆尼克在巴林交手,双方以4比4

战平。

年1至2月“更年少者”与卡斯帕

罗夫在纽约较量，3比3战平。

东北大学机器博弈研究室

克拉姆尼科最新赛事(2006.11)

连续三届奥林匹克冠军Kramnik2-4DeepFritz

的公回…皿

EMANN

TheDuel：manmachine

Kramnikvs.

DeepFritzHES

须知：深弗里茨比当年“深蓝”运算能力快2个数量级

东北大学机器博弈研究室

棋类机器博弈的发展

机基博寺涉及的范倒:

Othello臭塞罗

Checkers西译跳棋

Go-moku五子棋

Chess国际象棋

Chinesechess中国象棋

Shigo日本将棋

Go圈棋

东北大学机器博弈研究室

领域在延伸

♦Checkers的译跳棋

♦Chinesechess中国象樵

♦Go圈棋

♦Shogi0本将棋，目本象棋

Poker纸牌游戏

Othello

。Sokoban

❖LinesofactionHexAwariAmatons

RosamboDomineering...

东北大学机器博弈研究室

机器博弈的艰苦历程与辉煌成果

♦中国象棋----

被爱情遗忘的角落

♦:♦机器博弃工作者新的挑战

❖可喜的初战胜利

♦:♦还有很长的路要走

♦:♦围棋的机器博弃水平还彳艮低

东北大学机器博弈研究室

台湾电脑象棋之父

前台湾大学

资讯工程余教授

许舜钦

80年代开始

机器博奔研究

“Elephant”

现在台南长荣大学

东北大学机器博弈研究室

中国电脑围棋的骄傲

中山大学化学系

陈志行教授

“手微”

一汇编语言

1995J996J997

连续3年

6项世界冠军

v电脑圈棋小洞天〉

东北大学机器博弈研究室

新的挑战-----connect6

♦台湾交通大学教授吴故成

g六子棋发明人

侬公平的游戒

♦：♦六子棋相关网站

/web

东北大学机器博弈研究室

聘靖许峰雄博士报告、名誉教授、顾问

C2004.5.14J

东北大学机器博弈研究室

10thCOMPUTEROLYMPIAD

棋天大圣

勇夺

世界第三

东北大学机器博弈研究室

挑战特级象棋大师卜风迎

东北大学机器博弈研究室

ComputerOlympiad11夺冠

东北大学机器博弈研究室

浪潮杯首届中国计算机博弈锦标赛

棋天大圣

勇夺

全国冠I军

2006.8.8

东北大学机器博弈研究室

浪潮杯首届中国象棋人机大战

对阵5佳象棋大师

卜风波

徐天红

柳大华

法强

注译

2006年8月90

国家臭林匹克中心

综合编

东北大学机器博弈研究室

人机大战终极PK(2006815)

中国象棋第一人许银川VS棋天大圣

东北大学机器博弈研究室

ComputerOlympiad12夺冠

东北大学机器博弈研究室

棋天大圣获得

又一个世界冠军

并与台湾棋王吴贵临

国际大师战成平局

2007年7月

东北大学机器博弈研究室

民间棋类计算机博弈

♦:♦最简单的机器博弃项国

——机器博弃入门课

♦:♦麻雀虽小，五脏俱全

♦:♦从一个实例出发----牛角棋

东北大学机器博弈研究室

民间棋类的特点

规则简单，假家易入门；

不受专业知短限制；

♦:♦棋盘小,棋子少，复杂度不高;

♦:♦输赢家易识别,局面京易判断;

♦:♦完全信息，编程相对简单；

♦：♦人工智能的“果蝇”O

东北大学机器博弈研究室

牛角棋

牛角棋广泛见于各地，别

名较多，如憋死牛、憋死

井、娃娃下山、娘子下山

等。

♦:♦棋盘形状及棋佳数同也稍

有差异。但是棋子、棋规

都相同。

东北大学机器博弈研究室

牛角棋棋规

红子可上可下，可左可右,

一次一步,只能走向空优,

不得重合与跳跃3

❖蓝子只上不下，可左可右,

一次一步,只能走向会住,

不得重合与跳跳；

♦:♦胜负到新：憋无憋不死？

东北大学机器博弈研究室

红先红胜（7步）

东北大学机器博弈研究室

红先蓝雁

（18步）

为什么输赢？需要不断地摸索经除，试睑所有的局面。

东北大学机器博弈研究室

博弃思维过程红方先手

展开博弃树

红

方

走

ll\\IIW棋

东北大学机器博弈研究室

计算机是如何实现博弈过程的？

计算机如何进行博弃思维?

如何编写机器博弃程序？

东北大学机器博弈研究室

计算机如何进行博弈思维?

♦:♦如何存储思维信息？棋盘、棋子、棋

局、博弃树

♦:♦如何判新局面的胜负？

♦:♦如何展开博弃树？

♦:♦如何选择当前的看法？

♦:♦如何褊写程序？

♦:♦如何总结博弃的规律？

东北大学机器博弈研究室

如何存储思维信息?

编玛----数据结构

♦棋盘编玛r棋佳编吗）

♦棋子编玛

♦初始局面的表示

棋枚向量:(100000023)

♦棋子向量:(089)

东北大学机器博弈研究室

S°=(0,8,9)

棋局演化的形式化描述

♦状思变量S0=(P：,P；,P：)棋子向量表示

初始状态S。=(0,8,9)

♦状态障化方程S〃­1

.：.其中力+1为棋子i第〃+7步的看法r算子)

♦:♦着法规则：

红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃；

蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；

东北大学机器博弈研究室

看法的形式化描述

/：几=月±1,EH*e[0,9]

q?：瑶]=尸一1,P'=P、2e[0,9]

P\=，2+iG[2,8]cP；=even

产琛|=厅一1,P；「P；-2e[0,9]

P：1=£.3+1G[2,8]nP：=even

通过扫描棋盘，如果“落址”为空住，便是合法看法（算子）O

东北大学机器博弈研究室

如何判断局面的胜负？

♦:♦红雁：“逃出”

P->P-orb>P；

♦:♦蓝雁：“憋死”

Se=(?/，用=(0,2)D(0,2,1)

和棋----

局面的无限次重复

东北大学机器博弈研究室

如何展开博弈树?

红方先手

红

方

走

棋

东北大学机器博弈研究室

如何表示博弈树?

(0&9)

(2&9)(1,8,9)

(2,7,9)・(2,6,9)・(2,&7)

。z—-s^3Z4*sx。-s―z—3X4-z-0*s-3s4

333s3■93339s»

777766668888

393933939・3・

999999997777

东北大学机器博弈研究室

两种不同的展开方式

广度

优先

东北大学机器博弈研究室

两种不同的展开方式

深皮

优先

东北大学机器博弈研究室

广度优先的展开与存储

东北大学机器博弈研究室

深度优先的展开与存储

东北大学机器博弈研究室

如何选择当前的看法？

♦在展开的博弃树中披亲——博弃技奈引擎

♦:♦如果红方走棋，他总要找到博弃树中最好

的棋局,而在考虑对方（蓝方）走棋时,

就要考虑最坏的局面，因为双方都是理智

的博亲者，不应该抱有任何侥幸的心理。

♦:♦如果给每个棋局打分，邢红方可以称得上

是MAX方，蓝方便是MIN方。

东北大学机器博弈研究室

深度为3的博弈树

层教

Ply=O

Ply=1

Ply=2

Ply=3

图例：

东北大学机器博弈研究室

极大极小搜索

找到最佳路役与最佳看法

MAX

MIN

MAX

东北大学机器博弈研究室

从极大极小搜索到负极大值搜索

CurrentbestPVandbestmove

Alpha剪枝

找到最佳路径与最佳看法

MAX4a=4

MIN

MAX584623

东北大学机器博弈研究室

B■剪枝ru

由此产生豪佳路位和景佳看法

MIN

MAX

MIN

东北大学机器博弈研究室

B■剪枝C2J

由此产生豪佳路位和景佳看法

MIN

MAX

MIN

负极大值形式的Alpha-beta梗素

♦:.Alpha的含义：当前方已经存在某个看法,

其估值至少为alpha；

♦:*Beta的含义：对手存在着某个看法，令当前

方的着法的估值无论如何也越不过beta。

♦负极大值形式的alpha-beta剪枝只有beta剪

枝。

东北大学机器博弈研究室

(alpha,betaJ窗口

•负极大值条件下的(alpha,betaJ窗口

东北大学机器博弈研究室

(alpha,betaJ窗口

An

东北大学机器博弈研究室

博弈树枝索过程

BestPV

MoveGeneration

MakeMove

Cutoff

Meration

131189

ove

ation

东北大学机器博弈研究室

人

机

对

,弈

信

息

流

程

东北大学机器博弈研究室

计算引擎主要模块

基本模块

数

据

着法博弈树局面

结

构

相关搜索估值

「

,、

静

基

子

棋

启

态

力

盘

着

着

着

本

发

同

历

子

棋

配

法

法

法a

式

型

史

生

子

选

力

排

8合

表

搜

表

序

成

择

表

估

估

搜

索

示

值

值

索

东北大学机器博弈研究室

计算引擎程序的编写

♦:♦首先需要解决的算法分析与设计

♦:♦然后考虑算法的实现与编程

r编程语言，设计，编码,调试）

♦:♦遵照软件工程学的思想

♦:♦在程序设计方法学上下功夫

。学习人工智能的先进理论与技术

—这是所有专业所於需的！

东北大学机器博弈研究室

东北大学机器博弈研究室

棋子的表示

#defineREDSTONE0

#defineBLUESTONE11

#defineBLUESTONE22

东北大学机器博弈研究室

局面的表示（一）

初始局面的表示

intboard[10]=

(

REDSTONE,

0,0,0,0,

0,0,0,

BLUESTONE1,

BLUESTONE2,

｝；

东北大学机器博弈研究室

局面的表示（二）

♦初始局面的表示

记录有子的交叉点编号

(stoneIntersectionisi)

intsi[3]=

(

0,8,9

｝；

(注意off-by-one^

东北大学机器博弈研究室

等价的局面表示

等价的初始局面

intsi[3]=

(

0,8,9

｝；

intsi[3]=

(

0,9,8

东北大学机器博弈研究室

看法的表示

绝对看法的三个要素

Piece:哪个棋子

From：出发点编号

To：I标点的编号

东北大学机器博弈研究室

着法的表示

相对看法更方便

Piece：哪个棋子

To：同标点的编号

涵义：PieceTo

佳：543210

东北大学机器博弈研究室

看法生成

♦:♦着法生成是和棋类知M关系最为紧密的部分

♦:♦看法生成是博弃树展开和技奈的先决条件

♦:♦着法生成是博弃程序中一个相当复杂而且耗

费运算时间的部分

♦:♦通过前好的数据结构(棋盘表示，看法表

示),可以显著地提高生成的速度

♦:♦看法生成、实现(makemove)、评估、选择

之后,还要恢复到父节A(unmakemove)

东北大学机器博弈研究室

看法生成（一）

棋盘扫描法

〃以红子为例

for(eachpiece)

(

if((piecej+l<=9)

&&NoStoneAt(piecej+1))

*moveList++=piecCj+1;

if((O<=piecerl)

&&NoStoneAt(piecej-1))

*moveList++=piece”；

东北大学机器博弈研究室

看法生成（二）

预置表法

intpreTabIel21|10][5]=

/*redstonemovestable*/

{2,1,INV},{2,3,0,INV),

(4,3,1,0,INV},(5,4,2,1,INV},

{6,5,3,2,INV),{7,6,4,3,INV),

{8,7,5,4,INV),{9,8,6,5,INV},

{9,7,6,INV},{8,7,INV),

/*bluestonemovestable*/

{INV},{0,INV),

{3,1,0,INV},{2,1,INV),

{2,3,5,INV),{3,4,INV),

{4,5,7,INV},{5,6,INV),

{6,7,9,INV},{7,8,INV},

）；

东北大学机器博弈研究室

看法生成(二)

使用预置表法须注意：

根据牛角棋的规则，从预

置表中提取的看法需做如下合

法性判断：

preTablefcolor][from][i]!=

si[j]；

(其中,0<=/<=4;j=0,1,2)

[piece,from]->[piece,to]

东北大学机器博弈研究室

博弈树的展开与恢复

生成子节点局面

MakeMove()

椒铺子节点局面

r恢复到父节点)

UnmakeMove()

东北大学机器博弈研究室

牛角棋的搜索算法

负极大值形式的alpha-beta按奈算法

intSearchfintdepth,intalpha,intbeta,intwtm)

Iif(depth<0)

ReturnEvaluation;

if(gameOver)

returnEvaluation;

〃逐一展开各子树

for(eachMovem)

(

MakeMove(m);

val=-Search(depth-l,-beta,-alpha,!vvtm);

UnmakeMove(m);

-if(alpha<val)〃找到更好的看法

alpha=val;

if(alpha>=beta)//剪枝

returnalpha;

returnalpha;

东北大学机器博弈研究室

基

本

搜

索

流

程

东北大学机器博弈研究室

算法优化

♦博弃树是根在上部向下遹归产生的一棵

包含所有可能的对弃过程的技素树，是

完全技素树，包含了所有可能的博弃状

态

♦:♦但是，有些情况我们不希堡重复救奈，

比如重复出现的局面（状思J

东北大学机器博弈研究室

东北大学机器博弈研究室

循环局面的处理

技奈过程中循环局面的出现

若i<4则无循环,注意

Path[i]与Path[i-4]的关余

Path

16926927917916900000

0123456789

东北大学机器博弈研究室

循环局面的处理

e建立一个顺序表，命名为Path。

但每次披奈前将唯一表示当前局面的值存入表中

e若当前层为i,到新Path[i]是否等于Path[i-4]

e若相等，则剪枝，不等则继续技奈

e搜亲结束，将Path[i]赋值为0

e较复杂棋类，如象棋，一般用hash表实现循环局面的处

理。

东北大学机器博弈研究室

评估(-)

利条件

红方胜的条件：

(sifREDSTONE]==8)||(sifREDSTONE]==9))

蓝方雁的条件：

((si[REDSTONE]==0)&&

((sifBLUESTONEl]+si[BLUESTONE2])==3))

东北大学机器博弈研究室

棋局评估一胜负提前判别

不难看出，短兵相接，谁动谁输。

可以整理判据，放到程序当中。

东北大学机器博弈研究室

评估（二）

♦：♦其它人类知M

GS影响府负的重要条件

8局势细微变化的索件

GS举例

1)红子突破，红胜

((si[REDSTONE]>si[BLUESTONEl])||

(si[REDSTONE]>si[BLUESTONE2]))

2J蓝走红胜

((wtm==BLUE)&&

((si[REDSTONE]&1==0)&&

((si[BLUESTONEl]==si[REDSTONE]+l)&&

(si[BLUESTONE2]==si[REDSTONE]+2)||

(si[BLUESTONEl]==si[REDSTONE]+2)&&

(si[BLUESTONE2]==si[REDSTONE]+l))))

东北大学机器博弈研究室

如何编写机器博弈程序？

会下棋，下好棋——了解规则，槿得棋局的好坏，

区分看法的好坏，如何能够克敌制胜，如何立于不

败之地。

♦:♦掌援计算机博弃的基本知出----棋局与看法表示的

数据结构，着法生成与棋局评估，悔弃树，果佳路

役与景佳看法等。

♦:♦按照软件工程靖写程序——需求分析，总体设计，

详细设计，褊玛调试，设计文才我软件维护，条统

优化等等。

东北大学机器博弈研究室

计算引擎程序的编写

♦:♦首先需要解决的算法分析与设计

然后考虑算法的实现与编程

r编程语言，设计，编玛，调试j

♦：♦■照软件工程学的思想

♦:♦/■程序设计方法学上下功夫

♦:♦学习人工智能的先进理论与技术

——这是所有专业所必需的！

东北大学机器博弈研究室

如何总结博弈的规律？

♦:♦通过博奔树展开，考虑到分校教不大4,阶双教有限

（10步