人工智能早期研究给人的深刻印象是博羿,1956年,Samnel研制了一个西洋跳
棋程序,该程序“天生”下跳棋水平很低,远远不是Samuel的对手.但它有学习能力,
能从棋谱中学习,也能在实践中总结提高.经过三年的“学习”,该程序与1959年打败
了Samuel;又经过三年,打败了美国一个州的冠军.值的注意的是,虽然下棋至多
只能算是一项体育运动,下棋的程序似乎只是一种游戏程序,Samuel工作的意义十分重
大:它同时刺激了“搜索”和“机器学习”这两个人工智能重要领域的发展.用“井字棋”
游戏很容易说明“搜索”的基本概念.下棋过程中可能(即规则允许)出现的每一种格局
在搜索中被称为一个“状态”.所有状态分为三类:(1)初始态,如(a);(2)终
x ! !
___!_____!_____
! ! 数据挖掘研究院
___!_____!____
! !
! !
(a)
X ! !
___!_____!_____
! O !
___!_____!____
! ! 数据挖掘实验室
! !
(b)
x ! !
___!_____!_____
x ! o !
___!_____!____
! !
! ! 数据挖掘交友
(c)
x ! !
___!_____!_____
x ! o !
___!_____!____
o ! !
! !
(d) 数据挖掘论坛
x !x ! o
___!_____!_____
x ! o !
___!_____!____
o ! !
! !
(e)
止态,如(e);(3)中间状态,如(b)、(c)、(d).某些状态之间存在着“直接后
继”关系,如(b)是(a)的直接后继,(c)是(b)的直接后继;但(d)不是(c)的直
接后继.在井字棋游戏中,直接后继关系是由一次合法的走步决定的,如
X在方在新状态即格局(a)的左上角下一个X则产生该状态的直接后继即格局(b).
所有状态直接后继关系联接而成的有向图称为搜索空间.显然,搜索空间中每一条
从初始状态到任一终止状态的路经代表一次完整的下棋过程.某方获胜的终止专态
称为该方的目标状态.于是,游戏中任一方要考虑的问题是:怎样由当前状态(目前
所处的格局)达到自己的目标状态?
一般地,任一状态的直接后继不唯一.如图一中的状态(c),对先到方X来说,可选的
走法有7种.对其中的每一种选择,后到方O有6种走法.如此类推,为了确定最佳走法,
需要考虑大量的可能情形(即从当前状态出发达到终止状态的状态序列).人工智能智
能中的“搜索”所要研究的问题是:怎样“有效地”从上述大量的可能情形中选出最
佳方案.
|
