回复于:2001-08-10 20:40:08
dot99 转
五子棋算法探讨
--------------------------------------------------------------------------------
近来随着计算机的快速发展,各种棋类游戏被纷纷请进了电脑,使得那些喜爱下棋,
又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高,大有与人
脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力
的代表;其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜
爱;而我们今天将向大家介绍的是五子棋的算法。
当我们与电脑对战时,您知道这些软件是怎样象人脑一样进行思考的吗?前不久我
曾编写过一个五子棋的游戏,在这里就以此为例和大家一起探讨探讨。
总的来说(我们假定您熟悉五子棋的基本规则),要让电脑知道该在哪一点下子,
就要根据盘面的形势,为每一可能落子的点计算其重要程度,也就是当这子落下后会形
成什么棋型(如:“冲四”、“活三”等),然后通览全盘选出最重要的一点,这便是
最基本的算法。当然,仅靠当前盘面进行判断是远远不够的,这样下棋很容易掉进玩家
设下的陷阱,因为它没有考虑以后的变化。所以在此基础上我们加入递归调用,即:在
电脑中预测出今后几步的各种走法,以便作出最佳选择,这也是我们下棋时常说的“想
了几步”。如此一来您的程序便具有一定的水平了。什么?不信!过来试试吧!
总体思路弄清之后,下面进行具体讨论:
一:数据结构
先来看看数据结构,我们需要哪些变量?
首先得为整个棋盘建立一张表格用以记录棋子信息,我们使用一个 15*15 的二维数组
Table[15][15] (15*15 是五子棋棋盘的大小),数组的每一个元素对应棋盘上的一个交叉
点,用‘0’表示空位、‘1’代表己方的子、‘2’代表对方的子;这张表也是今后分析
的基础。
在此之后还要为电脑和玩家双方各建立一张棋型表 Computer[15][15][4]和 Player[15][15][4],
用来存放棋型数据,就是刚才所说的重要程度,比如用‘20’代表“冲四”的点,用‘15’
代表“活三”的点,那么在计算重要性时,就可以根据 20> 15 得出前者比后者重要,下子
时电脑便会自动选择“冲四”的点。那为什么棋型表要使用三维数组呢?因为棋盘上的每
一个点都可以与横、竖、左斜、右斜四个方向的棋子构成不同的棋型,所以一个点总共有
- 1
- 2
前往页