课程：嵌入式系统原理
学院：软件学院
专业：软件工程
年级：2007 级 1 班
学号：123012007003
姓名：耿魁
2010 年 6 月 24 日
黑白棋
1、引言
在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一
个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。电脑博
弈是人工智能研究的一个方向，到了近 50 年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的
智能逐步向人类智能发起挑战，香农(1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软
件的高速发展，从 1980 开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了 1997 年，IBM 超
级电脑 DeeperBlue 击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重
要旅程碑。
本系统在 ARM 机上，以黑白棋为研究对象，采用人工智能中的推理技术、搜索方法和决策规则，设计
了一个智能的黑白棋系统，实现人机对弈。
2、问题描述
2.1 黑白棋简介
黑白棋，又称苹果棋，翻转棋。黑白棋在西方比较流行，规则也很简单：
1. 开始在 8x8 的棋盘中央各有 2 枚黑棋和白旗，交错成为一个正方形；
2. 一般执黑子者先手，黑白棋手交错下子；
3. 棋手放入棋子后，任何在横线、竖线或斜线上的被棋手所执棋子夹住的所有对手棋子将被吃掉，
转化为棋手所有；
4. 棋手每次放入棋子必须至少能吃掉对方一颗棋子；
5. 若棋手当前无法吃掉对方棋子，则由对手下子；
6. 双方都无法吃掉对方棋子、一方没有旗子、棋盘已经塞满棋子，则比赛结束，旗子数目多者胜。
黑白棋不仅能增强思维能力，提高智力，而且变化多端，非常富有趣味性和消遣性。棋手每步均有多
个位置可以选择，且当前选择对后面的棋盘局势也有着重要的影响。下棋过程中，风云变幻，局势经常改
变。
2.2 设计思路介绍
本实验主要采用搜索方法和贪心策略，包括数据结构、搜索算法和优劣评价函数组成，主要的特点包
括快速的数据结构设计实现、高效率的搜索算法和尽可能有效的评价函数。
3、解决方法
3.1 数据结构
系统主要设计两类的数据结构‐‐‐‐棋盘状态和搜索方向。
棋盘状态：
采用两位数组矩阵存储棋盘状态，主要有三种状态：
⎪
⎩
⎪
⎨
⎧
=
，白棋
，黑棋
，空白
2
1
0
]][[ jimap
搜索方向：
在搜索棋子的时候，需要向周围八个方向搜索，所以采用数组：
dx[8]={-1,-1,0,1,1,1,0,-1}
dy[8]={0,1,1,1,0,-1,-1,-1}
3.2 搜索算法
在人机对弈的过程中，计算机优于人的地方在于其高速的运算速度和巨大的存储容量以及精确的判断
力。因此我们在实现的过程中，就是借助好的数据结构和算法技术在尽可能少的时间内，获得一个最大局
部化乃至全局最优的解。对于标准的黑白棋棋盘，其大小一般为 8x8，共 64 颗棋子，棋手每次可以选择的
位置等于剩余空白棋子的数目，这样整个状态空间将有大约 64！个结点，就目前的计算机技术，是无法计
算和存储如此巨大的状态空间，因此我们只能在有限的空间内寻找一个最优解。
正如人们之间下棋一样，对于一位具有一定水平的棋手，我们每步下子不仅仅是取决于当前落子的状
态，而是要考虑若干步后棋局的变化情况，这也正是棋手之间水平的体现。对于我们搜索算法而言，搜索
的深度越深，计算机的棋力也就越高。尽管如此，即使我们通过搜索预测五步的局面数的话可以达到几百
万。因此我们需要采用一定的贪心策略。
