井字棋（英文名Tic-Tac-Toe）
井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。
想起小时候上课喜欢玩井字棋，只要一张草稿纸、一支笔、同桌两人就可以玩了。上体育课，也可以拿着树枝在沙坑里玩。但一直感觉这游戏太简单了，后来接触了五子棋，着迷了一阵，但水平总是很差，便也不玩了。
一字棋游戏极小极大分析法
设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。
用叉号表示MAX，用圆圈代表MIN。
比如右图中就是MIN取胜的棋局。
为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：
设棋局为P，估价函数为e(P)。
(1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)
(2) 若P是MAX必胜的棋局，则e(P)＝+∞。
(3) 若P是B必胜的棋局，则e(P)＝-∞。
比如P如右图示,则e(P)=6-4=2
要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局
都是相同的棋局(在博弈中，一宇棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。图315画出了经过两层搜索生成的博弈树，静态估值记在端节点下面，倒推值记在圆圈内。
由于右图所示位置具有最大的倒推值，它应当选取为MAX的第一步（正好是MAX的最好的优先走步）。
现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层，产生如图316所示的搜索图。
现在图中MAX有两个可能“最好的”优先走步，假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索，产生如图317所示的树。
在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为—∞。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。
按极大极小算法编程下一字棋的演示(右图，可以点击 *** 作)．．．
我们就利用Visual Basic编写一个“井字棋”的小游戏。
设计思路
首先，我们要知道，“井字棋”游戏是一款典型的棋类游戏，游戏时一方式是电脑，另一方是玩家。所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。这是我们要考虑的第一个问题。
其次，由于与玩家对战的是计算机，所以我们要编写一个过程（Chuqi），它可以使程序模拟人的思维与人下棋（其实就是“人工智能”的体现），这个Chuqi过程也是本游戏软件的关键。此外，我们还要编写两个过程（Lianxian和Shuying），Lianxian过程用来时刻判断棋盘中是否有三个棋子连成一线；Shuying过程用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。
以上几个问题就是该“井字棋”游戏实现的关键思路。
>“井字棋”游戏（又叫“三子棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。“井字棋”的棋盘很简单，是一个3×3的格子，很像中国文字中的“井”字，所以得名“井字棋”。“井字棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“井字棋”是一方首先三子连成一线就胜利。
井字棋（英文名Tic-Tac-Toe）
井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。
想起小时候上课喜欢玩井字棋，只要一张草稿纸、一支笔、同桌两人就可以玩了。上体育课，也可以拿着树枝在沙坑里玩。但一直感觉这游戏太简单了，后来接触了五子棋，着迷了一阵，但水平总是很差，便也不玩了。
一字棋游戏极小极大分析法
设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。
用叉号表示MAX，用圆圈代表MIN。
比如右图中就是MIN取胜的棋局。
为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：
设棋局为P，估价函数为e(P)。
(1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)
(2) 若P是MAX必胜的棋局，则e(P)＝+∞。
(3) 若P是B必胜的棋局，则e(P)＝-∞。
比如P如右图示,则e(P)=6-4=2
要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局
都是相同的棋局(在博弈中，一宇棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。图315画出了经过两层搜索生成的博弈树，静态估值记在端节点下面，倒推值记在圆圈内。
由于右图所示位置具有最大的倒推值，它应当选取为MAX的第一步（正好是MAX的最好的优先走步）。
现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层，产生如图316所示的搜索图。
现在图中MAX有两个可能“最好的”优先走步，假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索，产生如图317所示的树。
在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为—∞。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。
按极大极小算法编程下一字棋的演示(右图，可以点击 *** 作)．．．
我们就利用Visual Basic编写一个“井字棋”的小游戏。
设计思路
首先，我们要知道，“井字棋”游戏是一款典型的棋类游戏，游戏时一方式是电脑，另一方是玩家。所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。这是我们要考虑的第一个问题。
其次，由于与玩家对战的是计算机，所以我们要编写一个过程（Chuqi），它可以使程序模拟人的思维与人下棋（其实就是“人工智能”的体现），这个Chuqi过程也是本游戏软件的关键。此外，我们还要编写两个过程（Lianxian和Shuying），Lianxian过程用来时刻判断棋盘中是否有三个棋子连成一线；Shuying过程用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。
以上几个问题就是该“井字棋”游戏实现的关键思路。
QQ:744192659
邮箱:zhuwentao1996@livecn
一、实验题目
五子棋游戏。
二、问题分析
五子棋是双人博弈棋类益智游戏，由围棋演变而来，属纯策略型。棋盘通常1515，即15行，15列，共225个交叉点，即棋子落点；棋子由黑白两色组成，黑棋123颗，白棋122颗。游戏规则为黑先白后，谁先五子连成一条直线谁赢，其中直线可以是横的、纵的、45度、135度。
本次Java编程我的目的是现实人机对战，即游戏者一方是人，另一方计算机。这就要求程序不仅要具备五子棋的基本界面，还要编程指导计算机与人进行对弈。为了使程序尽可能智能，我采用了贪心策略、传统搜索算法、极大极小博弈树算法，对应游戏玩家的3个等级：简单、中等、困难。
三、功能设计
我的程序基本功能是实现人机对弈五子棋。人和电脑交替下棋，谁先五子连成一条直线谁就赢。下面是我程序的功能模块：
1等级设置
核心功能是实现不同策略与算法的对比运用，纯贪心策略实现简单等级对手，直接搜索算法实现中等等级对手，极大极小博弈树算法实现困难等级对手。对应程序中的3选1单选按钮。
2悔棋功能
模拟栈机制实现人悔棋，不限步长的悔棋。对应程序中的悔棋按钮。
3棋面绘制
根据不同机计算机的屏幕分辨率，绘制逼真的棋盘。
4引入
两张古典的人物，生动模拟对弈双方。人物旁的黑白棋钵显示黑白棋归属。
5背景设置
支持用户选择背景，包括棋盘、棋盘边框、窗口边框，彰显个性。
6音乐播放
下棋时有棋子落地的声音，一方胜利时有五子连成一片的声音。同时在设置背景时相应的改变整个对弈过程中的背景音乐。
7时间显示
在棋盘正上方有一模拟文本框显示当前棋局用时。
8其他小功能
支持和棋、认输、开启新游戏、退出游戏等 *** 作。
四、数据结构与算法设计
数据结构部分
1当前棋局的存储结构
我的五子棋程序选择通常用到的15行15列棋盘，可以开二维数组PositionFlag = new int[15][15]，PositionFlag[i][j]为0表示(i,j)点尚无棋，为1表示(i,j)点是人的棋子，为2表示(i,j)点是机器的棋子。之所以选择二维数组，主要原因有两点：
1本程序需要频繁随机访问1515的交叉点，对应查询该点状态以及改变该点状态，随机访问是数组的特点。
21515=225开二维数组的内存需求相对现在内存为2G及以上的计算机完全可以接受，且数组实现简单、 *** 作方便。
基于以上两点，尽管创建动态的顺序表—链表可能可以节省少量内存（可以只存当前有棋的点，原数组对应位置为0的点可以不存），但选择数组的优势完全在上述两点体现了出来。
2实现悔棋 *** 作的数据结构
由于每次悔棋只需回退当前几步，后进先出原则，这正是栈这种典型数据结构的设计思想，于是我选择栈。我自己先写了用自定义数组模拟的栈，但由于是学Java语言且由于悔棋的存储空间需要随当前步数增大而增大（由于每局最多下225步，即最多要悔225步，所以自己开个225的数组完全可以避免存储空间自增长的问题且内存完全可以接受，之所以不用自定义数组而用ArrayList类主要是为了尝试Java中STL的用法），所有我最终改为用Java类库中的ArrayList类。
确定用ArrayList类实现栈机制后就必须考虑每个ArrayList单元具体存储什么。刚开始我存储的是当前的棋局，即整个局面，而每个局面对应一个二维数组，这样是很占用内存的。试想一下，在最坏情况下，225个ArrayList单元，每个单元存放一个1515的二维数组，尽管2251515在Java的内存管理机制下不会爆栈，但也是极不划算的。之所以说不划算，是因为有更好的解决方案。由于每次悔棋只是在回退倒数一步，多步悔棋只需循环回退，所以可以只存储当前棋局最后一步的下法，对应一个二维点，完全可以自定义一个二维坐标类chessOneStep。
算法设计部分
Java语言是面向对象的语言。我在进行五子棋游戏编程是总共传创建了11个自定义的类。在编写程序的过程中，我有一个明显的体验就是面向对象编程就是一项有关对象设计和对象接口技术，很多关键的技术就是如何设计自定义的对象。
下面我先概括给出我的所有类的作用：
1mainFrame类：主框架类，我应用程序的入口；
2chessPositon类：主控类，这个类是我程序的核心类，负责控制双方的下棋，以及调用其他的类完成当前棋局的显示绘制；
3chessPanel类：面板类，调用其他底层类完成当前棋局的显示绘制；
4chessBoard类：棋盘绘制类，负责棋盘的绘制；
5chessImage类：文件类，包含各种资源（背景、背景音乐）以及静态全局变量（public static Type）；
6chessButton类：组件类，定义各种组件，包括按钮、单选按钮、文本框等；
7chessMusic类：音乐类，负责调用Java库类完成背景音乐、下棋音乐、取胜音乐等的播放；
8chessPiece类：棋局类，定义棋局二维数组数据结构并完成相关 *** 作；
9chessList类：栈类，完成悔棋等 *** 作；
10 chessOneStep类：棋子类，定义每步坐标以及下在该处获得的估价值；
11myCompare类：排序类，完成chessOneStep类的自定义排序
详细设计
1mainFrame类
作为我的五子棋程序的主类，mainFrame类主要实例化相关的对象，如chessbutton,chessborad等，从而完成框架的创建。更重要的是实例化chessposition，这是本程序的核心类，控制游戏双方行棋过程完成人机互动下棋，然后将MyChessPosition与鼠标响应addMouseListener（）关联起来。
2chessMusic类
一个好的游戏必须给人一种身临其境的感觉，而声音是营造这种氛围的重要因素。参照网上各游戏运行商的音乐配置，我选择相关逼真的声音。包括背景音乐、下棋棋子落到棋盘发出的声音以及一方胜出的配乐。所有这些功能的实现，依赖于自定义的chessMusic类，采用AudioInputStream配合Clip的方式完成音乐播放的软硬件工作，然后定义两个接口chessmusic(String Name)和Stop(),前者完成播放功能，后者完成关闭当前音乐功能。因为音频文件相对较大，而我的程序提供在不同背景乐之间切换的功能，所以在打开另一个音频文件之前必须关闭前一个正在播放的音频文件，防止出现溢出。
3chessImage类
适当的动画或能给游戏玩家带来美的体验。所以我的五子棋程序界面在不失和谐的前提下引入了尽可能多的，包括对弈双方、棋钵等。引入的具体工作通过语句import javaximageioImageIO完成。同时，由于要在用到它的类中被访问，为了避免频繁调用函数，我直接将相关联的对象定义为public static，表明是公用的、静态的。进一步引申开去，我将程序中用到的静态全局变量都定义在chessImage类中。具体如下：
public static Date begin;//每局开始时间
public static Date cur;//每局结束时间
public static chessOneStep LineLeft;//结束端点1
public static chessOneStep LineRight;//结束端点2
public static boolean IsGameOver;//是否只有一方获胜
public static int ColorOfBackGround[][]= {{255, 227, 132},{0,255,127},{218,165,32}};//背景颜色
public static int ColorOfWindows[][]= {{ 60,179,113},{245,245,245},{122,122,122}};//背景颜色
public static int WitchMatch;//背景搭配
public static String MusicOfBackGround;//背景音乐
public static int CurrentStep;//记录当前步数
public static int Rank;//设置难度等级
public static boolean IsSurrender;//判断是否认输
public static boolean IsTie;//判断是否认输
public static String Message;//输出提示信息
public static Image IconImage;// 图标
public static Image blackBoard;//白棋盘
public static Image whiteBoard;//黑棋盘
public static Image blackChess;// 白棋棋子
public static Image whiteChess;// 白棋棋子
public static Image RightPlayer;//白棋棋罐
public static Image LeftPlayer;//白棋玩家头像
public static String path = "src/";// 的保存路径
4chessButton类
这个是程序的组件类。定义了各种功能键，完善程序功能，营造逼真的人机对战游戏效果。分为3类：效果。。
(1)、按钮组件
本程序有5个按钮，支持和棋、认输、新游戏、退出、悔棋等。认输和和棋按钮终止当前的棋局，给出相应的提示信息；退出按钮调用系统Systemexit(0)的函数正常返回；悔棋按钮调用后面要介绍的chessList类实现悔棋；新游戏按钮则刷新当前棋局准备下一轮，要将记录当前棋局的二维数组全部置0，刷新当前棋局开始时间等。
(2)、单选按钮组件
游戏界面支持设置个性化界面，包括背景颜色与背景音乐，跟重要的一点是设置难度（简单、中等、困难）。单选按钮只能多选一。背景颜色主要是存储相关颜色搭配方案的RGB颜色，开2维数组，即对应RGB3原色数组的一维数组，然后通过改变WitchMatch全局变量的值来有用户自己选择颜色搭配，不同的颜色搭配对应不同的背景音乐表达一致的主题。难度设置主要是改变计算机的下棋算法，不同难度通过Rank判断进入不同的程序分支，实现不同智能等级的计算机下棋水平。
(3)、文本框
在不同的单选按钮前添加相应的文本框，提示用户可以实现的功能。同时我用颜色模拟出显示当前棋局耗用时间的文本框。
不论按钮还是单选按钮都要关联相应的消息，把相应功能的实现放在消息响应处理函数理。这些主要是实现Java库提供的消息响应接口里的方法。
5chessPiece类
主要完成当前棋面的存储，存储棋面的数据结构为二维数组int[][] PositionFlag；然后定义获取、设置某点以及整个棋面的状态的方法。
(1)、SetPositionFlag(int x, int y, int flag)//设置（x,y）处的状态为flag
(2)、GetPositionFlag(int x, int y)//获取（x,y）处的状态
(3)、SetAllFlag(int [][]NewFlag)//设置当前整个棋面的状态为NewFlag
(4)、GetAllFlag()//获取当前整个棋面的状态
(5)、DrawChessPiece(Graphics g)//绘制当前局面的棋子
由于本类比较重要，所以附上了代码，见源代码1。
6chessBoard类
功能为绘制棋盘线。由于围棋的棋盘比较复杂，横线、竖线较多，且为了使棋盘美观，还要自定义窗口边框、棋盘边框、对弈双方边框等，对线宽、线型也有一定要求。有时要单像素线条，有时要多像素线条。对于多像素线条，我主要用了2种方法。
方法一：
在需要绘制多像素线条处首先绘制一条单像素线，然后根据线宽要求上下平移适当像素达到绘制多像素的目的。这样的方法适合绘制水平线或竖直线，绘制其他斜率的线条容易造成走样。在没有想到比较好的反走样编程思想后我选择了调用Java库中已经封装好的函数。
方法二：
为了克服方法一绘制非水平或竖直线时造成的走样，同时也为了更进一步学习Java语言，我猜想肯定会有类似OpenGL中设置线宽的画刷，于是上网百度找到了相应的画刷Stroke类。通过Java库实现绘制不同线宽的直线，达到了反走样效果。
7chessOneStep类
这个类是为了配合chessList类实现悔棋以及在计算机下棋算法实现返回有效状态点而设计的。主要数据成员为
private int x,y,weight；//其中x,y表示点坐标，weight表示将棋下到该点获得的估价值。
主要方法如下：
(1)、GetX()//获得当前对象的x坐标
(2)、GetY()//获得当前对象的y坐标
(3)、GetWeight()//获得当前对象的(x,y)处的估价值
8chessList类
程序支持悔棋功能，为了实现悔棋，自定义了chessList类。这个类主要通过引入javautilArrayList和javautilList实现集合的数据类型。然后自定义一些方法，如下：
（1）、AddStep(chessOneStep OneStep)//添加一步棋到List中
（2）、GetSize()//获得当前List的大小
（3）、ClearList()//清空List
（4）、RemoveLast()//删去List中的最后元素
由于每次删除当前List中的最后一个元素，实现后进先出，所以可以模拟栈的功能实现悔棋。
9myCompare类
由于在计算机下棋的极大极小博弈树算法中需要对自定义对象chessOneStep按weight进行排序，所以引入了myCompare类，通过实现Comparator接口中的compare方法完成自定义对象排序。
10chessPanel类
程序的自定义面板类，主要负责完成当前框架内容的显示。这是一个重要的与框架和图形显示密切相关的类。主要数据成员为
private chessboard MyChessBoard;//当前显示棋盘
private chesspiece MyChessPiece;//当前显示整个棋面的状态
主要方法如下：
（1）、chesspanel(chessboard MyChessBoard1, chesspiece MyChessPiece1)//构造函数，分别用MyChessBoard1和MyChessPiece1初始化MyChessBoard和MyChessPiece
（2）display(chessboard MyChessBoard1, chesspiece MyChessPiece1)//自定义显示回调函数，调用repaint()完成重新绘制游戏界面
（3）、paintComponent(Graphics g)//核心方法，调用各种函数完成具体的绘制工作
11chessPositon类
程序算法核心类，总的功能是控制人和计算机轮流下棋，以及调用chessPanel类中的display(chessboard , chesspiece )方法完成界面的实时刷新。关于chessPositon类，我在此将重点介绍。chessPosition类的主要数据成员如下：
private static chessboard MyChessBoard;//当前显示棋盘
public static chesspiece MyChessPiece;//当前显示整个棋面的状态
private static chesspanel Mychesspanel;////当前显示面板
public static chesslist MyChessList=new chesslist();//当前下棋集合，用于悔棋
final private static int INF = (1 << 30); // 表示正无穷大的常量，用于极大极小博弈数搜索算法
public static boolean CanGo;//控制当前下棋一方
类的设计集中体现在成员方法的设计上。实现人机对战，只有语言是远远不够的，还要加入算法，用算法引导计算机下棋。下面介绍该类的方法成员：
（1）、chessposition(chesspanel , chessboard ,chesspiece ) //带有参数的构造函数
（2）、chessposition()
不带参数的构造函数
（3）、mouseClicked(MouseEvent event)
鼠标响应函数，负责人的下棋，根据鼠标点击的位置转换得到所在棋盘的相对位置。如果该位置不合法，即超出棋盘有效范围，点击无响应；如果该位置上已有棋，d出消息框给出提示。这二者都要求重新给出下棋位置，即当前鼠标响应无效…直到点击到棋盘有效区域。
（4）、IsOver(int[][] Array,int x,int y)
判断当前int[][]Array对应的棋局是否结束，即一方五子连成一条直线。此处有两种思路，一种对当前棋面上的所有棋子都进行一次判断，具体为水平方向、竖直方向、与水平线成45度方向、与水平线成135度方向，只要有一个方向五子连成一条直线就说明有一方获胜，游戏结束；另一种思路为只在当前下棋的4个方向进行判断，我的程序采用的是第二种，所以IsOver方法除了int[][]Array参数外，还有x,y参数，（x,y）表示当前下棋的坐标点。
（5）display()
通过调用自定义面板类的显示回调函数用于重新显示游戏界面，达到每下一步棋及时更新游戏界面的目的。
（6）、GetValue(int flag, int num)
估值函数，根据经验把棋局分成只有1颗棋相连，2颗棋相连且两端被封死，2颗棋相连且一端封死另一端活的，2颗棋相连且两端都是活的，同理3颗棋、4颗棋也各自可分3种情况。不同的情况对应不同的估价值。估价值的设定是决定计算机一方是否智能的一个关键因素。
（7）、GetPredictValue(int flag, int num)
对未连成一片但通过再下一颗子就能连成一片的局面进行估值，这在双方下棋的有限步骤内是能产生重要影响的。如果每局棋仅考虑当前一步，是不可取的。
（8）、Evaluate(int[][] Array, int x, int y)
根据棋面具体情况以及预先设定的估值函数，对某个点对应的局面进行评估。由于每次双方只能下一颗棋，所以可以每次取当前局面的所有点中对应估值最大值点的估值作为整个局面的估值。
（9）、GetGreedNext()
计算机下棋方法1，对应难度等级为简单，采用贪心思想。每次下棋前在求得最有利点下棋，而是否最有利只是通过一步评估。算法伪码描述为：
Max取负无穷大
for(行i从0到15)
{
For(列j从0到15)
{
If((i，j)对应的位置无棋)
{
a假设放上一颗由人控制的棋，求估价值；
b假设放上一颗由计算机控制的棋，求估价值；
c取二者中较大值作为(i,j）处的估价值tmp；
d取tmp与Max较大值赋值给Max
}
}
}
最终Max对应的点就是当前整个局面中最大的估值点。至于上述为什么要考虑双方都在该点下棋的情况呢？主要原因为下五子棋是个攻防兼备的过程，不仅要考虑自己对自己最有利，还要考虑对对手最不利，通俗来讲就是在自己赢的时候不能让对手先赢。
（10）、GetSearchNext(int LookLength)
derectSearch(int [][]Array,boolean who,int deepth)
计算机下棋方法2：直接搜索法,对应难度等级为中等。
每步棋最多有225个不同下法，若采用直接搜索法则对应的孩子节点有225个（在下棋过程中会逐渐减少），即每层有最多225个节点待扩展，这就决定了直接搜索进行不超过2次—主要原因有两点：
a采用深度优先搜索需要递归，递归中状态过多可能会爆栈，我们知道递归是用栈机制来实现的；采用宽度优先搜索又需要存储为扩展的节点，这对内存容量要求很高。
b不管深搜还是广搜，在时间复杂度为O(N^m)的情况下都是不能接受的。其中N为当前棋局的待扩展节点，最大225;m为搜索的深度。
综上所述，在采用直接搜索法时搜索深度不能太深，严格来说是应该控制在2层以内，在计算机运算速度在10^7次每秒的情况下，理论和实验都表明超过2层就会变得很慢且这种趋势成指数级增长。
直接搜索算法伪代码为
GetSearch(boolean flag，int deep)
{
如果deep等于0，返回当前棋局估值；
for(行i从0到15)
{
For(列j从0到15)
{
If((i，j)对应的位置无棋)
{
如果轮到计算机下棋，置标志位为2
GetSearch(！flag，deep-1)；
如果轮到人下棋，置标志位为1；
GetSearch(！flag，deep-1)；
}
}
}
}
（11）、GetMinMaxsearchNext(int LookLength)
MinMaxsearch(int [][]Array,boolean who, int deepth)
计算机下棋算法3：极大极小博弈树法,对应难度等级为困难。五子棋是个博弈游戏，当前在寻找对自己最有利的下棋点时要尽可能保证对对手最不利，这种思想可以用极大极小博弈树
人工智能原理 2004年一、回答下列问题（30分）
1、什么叫宽度优先搜索？宽度优先搜索的优点在何处？缺点在何处？
2、试说明逻辑符号“ ”、“→”的含义和差别。
3、请举出输入归结演绎不完备的例子。
4、设S={P(x),Q(f(a))}是子句集，请举出I是S的普通解释，而不是其Herbrand解释的例子。
5、请举出公式与其Skolem范式不等价的例子。
6、什么叫A算法？什么叫A算法？什么叫A算法是可采纳的？两个A算法如何比较好坏？
二、求解下列问题（30分）
1、设八数码问题有估价函数：f(n)=d(n)+W(n)；其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数；试给出以下面为初始节点和目标节点的图搜索过程，指明各节点估价函数值和整体解路径，并计算该搜索过程的渗透度是多少？有效分枝系数是多少？
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
2、将公式G化为Skolem范式，并给出G的子句集S。
3、使用基于规则的正向演绎系统证明下面问题：
已知事实 ；规则两条 ， ；目标 。画出演绎过程与/或图。
三、证明第一种形式的Herbrand定理：设S是子句集，则S是不可满足的，当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树。（15分）
四、总结α-β过程，并以下述博弈树为例，以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（15分）
五、什么叫支架集归结演绎，试证明基子句集支架集归结演绎的完备性。（10分）
人工智能原理 2003年
一、叙述图搜索算法GRAPHSEARCH过程；设八数码问题有两个估价函数：f1(n)=d(n)+W(n)；f2(n)=d(n)+P(n)+3S(n)。其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数，P(n)是每个数码离开目标位置的距离的和。S(n)是由如下方式得到的序列分：对于非中心的外圈上的数码沿顺时针方向走一圈，如果一个数码后面的数码不是它在目标状态下的后继者，则给这个数码记2分，否则记0分；对于中心位置，有数码的记1分，没有的话记0分。然后把所有上述得分加起来，就得到序列分S(n)。现有初始状态和目标状态描述如下：请画出各自的启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。计算出各自的渗透度和有效分枝系数。（40分）
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
二、总结博弈搜索的极小极大过程和α-β过程，并以下述博弈树为例，给出两个过程的各节点返回值和搜索到的路径（请画出两个过程图）。对于其中的α-β过程以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（20分）
三、（27分）
1、设子句集 ，求S的H域，S的原子集，子句 的基例集合。
2、使用合一算法判断表达式集合W={Q(f(a), g(x)), Q(y, y)}是否可合一，若可合一，则求出最一般合一。
3、试用表推演方法证明 共同蕴含 。
四、设S是命题逻辑子句集，P是S中出现的一个原子符号，于是可将S中子句分为三部分：含有文字P的部分 ，含有文字～P的部分 ，和不含文字P或~P的部分S3。令 ， ，请证明S是不可满足的当且仅当S1’ , S2’ 都是不可满足的。（8分）
五、请举出基于规则的正向演绎系统不完备的例子。（5分）
人工智能原理 2002年
一、简要回答下列问题（24分）
1、以八数码问题为例，说明产生式系统的基本组成。
2、什么叫A算法？A算法的主要性质是什么？
3、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
4、在基于规则的正向演绎系统中，规则和目标各要求怎样的形式？
5、基于规则的正向演绎系统是否完备？反向演绎是否完备？双向演绎是否完备？
6、在启发式搜索中，估价函数一般定义为f(n)＝g(n)＋h(n)，指明定义中各部分的含义，并说明为什么使用这种定义方式。
7、在合一算法中，设W是非空表达式集合，D是W的差异集合，则当D具有怎样的形式时，W是不可合一的？
8、常用的知识表示方法有哪几种，简要回答各自的特点。
二、判断对错（14分）
1、OPEN表上任一具有f(n)≤f(s)的点，最终都将被A算法选作扩展的节点。
2、若满足单调限制，则A算法所扩展的节点序列的f值是单调递增的。
3、设θ，λ是两个替换，则θ•λ=λ•θ。
4、表达式集合W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))}是可合一的。
5、渗透度和有效分枝系数都是关于图搜索方法启发能力的空间复杂性度量标准。
6、子句集S恒假，当且仅当对每一个解释I，使S中的每个子句C的基例C’被I弄假。
7、一阶逻辑中任一公式是否是恒假的，可用归结方法判定。
三、（12分）
1、若E=Q(y, f(y, g(x))), θ={a/x, b/y, y/z},λ={a/x, z/y, f(x)/z}, 求Eθ, Eλ, Eθ•λ
2、使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)＜diag(m, n)，则在排序中把规则Rij放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。若diag函数值相同则规则随机排序。
四、使用归结方法证明下述子句集是不可满足的（写出整个归结过程和每一步归结使用的合一替换）。
（10分）
五、设产生式系统PS，其状态集合DB={a, b, c, d, e, f, g, h, i, m}，产生式规则为：
a→b，c→m，g→h，a→c，d→e，h→i，a→d，e→f，m→i，b→g，f→m
设a为初始状态，规则应用费用为1，各状态的启发函数值为：
状态 a b c d e f g h i m
h值 1 1 8 2 2 2 4 4 10 4
用A算法画出节点c扩展前与扩展后的搜索图与搜索树，要求标出图中节点的扩展次序、估价函数值，写出节点c扩展前CLOSED表与OPEN表中的元素。（15分）
六、已知子句集S={P(g(x), z), ~P(f(y), h(a))}，求S的原子集、S的语义树。若给定S的一个解释I如下：
D={1, 2} a g(1) g(2) f(1) f(2) h(1) h(2) P(1, 1) P(2, 2) P(2, 1) P(1, 2)
2 2 1 1 2 2 1 F F T T
请构造S对应与I的H解释I。（15分）
人工智能原理 2002年
七、对下面的博弈树以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化，以及搜索到的路径。图中□表示极大点，○表示极小点。说明一般的α-β剪枝过程中，什么情况下效率最高。（10分）
人工智能原理 2000年
一、简要回答下列问题（24分）
1、请叙述产生式系统的过程。
2、回答产生式系统的分类，并说明各自的优缺点。
3、叙述什么样的产生式系统是可交换的产生式系统。
4、说明无信息的图搜索过程与启发式图搜索过程的差异，并举出两种典型的无信息图搜索方法。
5、叙述一阶逻辑解释的定义。
6、在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是否够用？为什么？
7、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
8、机器学习一般分为哪几种类型？
二、设八数码问题有估价函数：f(n)=d(n)+W(n)；其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。现有初始状态描述和目标状态描述如下：
3 4 5
2 6
1 8 7
3 4 5
8 6 7
2 1
请画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。（20分）
三、试用表推演方法证明 共同蕴含 。（16分）
四、叙述合一算法，并用合一算法求出W={P(a, x, f(g(y))), P(z, f(z), f(u))}的最一般合一。（写出算法的执行步骤，20分）
五、欲对某一有解的图搜索问题试用A算法，试证明A算法终止前的任何时刻OPEN表中总存在节点n’，n’在最佳解路径上，满足f(n’)≤f(s)，其中s为初始节点。（15分）
六、在归结推理方法中，若不取因子而仅使用二元归结式是不完备的，请举出一个反例。（5分）
人工智能原理 xxxx年
一、回答下列问题（20分）
1、什么是可交换产生式系统？
2、影响A算法启发能力的因素有哪些？
3、叙述α-β过程的剪枝规则。
4、归结原理有哪几种重要的改进？
5、描述基于规则的正向演绎系统的初始状态、规则和目标的一般形式。
二、请用估价函数：f(n)=d(n)+W(n) 求解八数码问题，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。
3 2 1
4 8
5 6 7
3 8 2
4 6 1
5 7
画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。（20分）
三、叙述合一算法，并用该算法寻找表达式集W={R(x, x), R(f(a), g(y))}的最一般合一。（20分）
四、使用AO算法，启发函数应满足什么条件？下图是已给出的与/或图，其中n0是初始节点，{n7, n8}是目标节点集，h是启发函数，并假定k-连接符的费用是k。请用AO算法求解其最优解图。（20分）
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、证明下述归结方法的完备性定理：如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎。（20分）
人工智能原理 xxxx年A
一、简要回答下列问题
1、人工智能的主要研究领域有哪些？
2、产生式系统由哪几部分组成？各部分的作用是什么？
3、产生式系统的控制策略有哪几种方式？
4、什么是深度优先搜索？什么是宽度优先搜索？
5、什么叫启发信息？它是如何使用的？
6、影响A算法启发能力的要素有哪些？
7、搜索方法的启发能力有哪几种基本的度量方法？
8、什么是从子句集S推出子句C的归结演绎？
9、什么是可交换产生式系统？
10、在归结演绎中，什么叫最一般的合一替换？
二、试述可分解产生式系统的基本过程。
三、已知八数码难题的初始状态和目标状态为：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
设估价函数：f(n)=d(n)+W(n) ，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树上标明各节点的估价函数值及选择扩展节点的次序。
四、已知与/或图，其中n0是初始节点，{n7, n8}是目标节点集，h是启发函数，并假定k-连接符的费用是k。请用AO算法求解其最优解图。
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、试用归结演绎证明公式 是公式集
的逻辑结果。
人工智能原理 xxxx年B
一、简要回答下列问题
1、无信息的图搜索方法主要有哪两种？
2、简述各种搜索策略各自的优缺点。
3、影响A算法启发能力的要素有哪些？
4、一阶逻辑中，公式是怎样定义的？
5、一阶逻辑中，公式的解释是怎样定义的？
6、命题逻辑中，常用哪两种公式范式？
7、一阶逻辑中，常用哪两种公式范式？
8、什么叫子句集的Herbrand域？
二、试述图搜索算法GRAPHSEARCH。
三、已知八数码难题的初始状态和目标状态为：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
设估价函数：f(n)=d(n)+W(n) ，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树上标明各节点的估价函数值及选择扩展节点的次序。
四、写出下述公式的Skolem范式：
五、请用归结方法证明子句集 是不可满足的。
六、请使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)＜diag(m, n)，则在排序中把规则Rij放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。博弈树
探讨一下难度较大的棋类游戏程序，比如国际象棋和西洋跳棋
等等。用这些程序来同人或其他程序对弈。然而，有些程序是把计算机精心设计成一个棋
盘，人们可以在其上对弈（或者是一种单人玩的棋盘游戏）。这种程序更接近于系统模拟
的领域，而不属于人工
智能的范畴。我们此处所要介绍的却是让计算机能够“思考”如何下棋。
假定有两个人或者两台机器在下棋。我们把其中一名称为棋手，另一名称为对手。而我们
始终从棋手的角度来观看这场竞赛。这样一来，如果棋手赢了、对手输了，我们就说这盘
棋赢了；如果棋手输了、对手赢了，我们就说这盘棋输了。
假设现在该轮到棋手走了。在大多数情况下，棋手对这步棋可以有若干种选择。对于棋手
的每一种选择，对手也有若干可供选择的相应棋步。对于棋手的每一步棋以及对手的每一
步回棋，棋手又有自己进一步的选择。显然，这里所遇到的分支情况同我们在状态搜索中
遇到的情形相同的。
实际上，我们可以把一盘棋想象成具有一个入口（起始位置）和一组出口的迷宫。有些出
口标上了赢的记号；有些出口标上了输的记号；而有些出口标上了和局的记号。在入口处
，棋手选择某条路径起步，在路径的一个岔口，对手挑选了自己的路径回步，棋手和对手
就这样轮流选择自己的
路径走下去。棋手总是力争通向胜利的出口，而对手却总是把棋路引向输的出口。有时双
方各自的努力不相上下，最后在和局出口结束棋局。或者他们一直在这个迷宫中徘徊，直
到形势变得非常明朗：双方循环兜圈子，这时只好双方握手言和。
因此，下棋游戏同状态图搜索是相似的，就是要在状态图中找出一条从初始状态到目的状
态的路径。但是，它们之间却有一个很大的差别。在状态图搜索中，总是由一名选手来选
择下一步往哪走。而在棋类的对弈中，棋手只有一半选择的权利，另一半由对手作出决定
。棋手是一直朝着目标
努力，而对手却是通过它每一步棋对此设置障碍。寻找机会把棋手从通往目标的路径上引
开。
对于任何一种博弈竞赛，我们可以构成一个博弈树。它类似于状态图和问题求解搜索中使
用的搜索树。博弈树的结点对应于某一个棋局，其分支表示走一步棋；根部对应于开始位
置，其叶表示对弈到此结束。在叶节点对应的棋局中，竞赛的结果可以是赢、输或者和局
。
所谓棋局，就是所有那些必须记录下来的信息。根据这些信息，比赛在按计划暂停以后能
够得以继续进行下去。显然，这些信息包括了此时棋子在棋盘上的位置以及指出下一步是
轮到棋手走，还是对手走。
博弈树是一棵与／或树，不同于在状态搜索中使用的纯粹的或树。
其原因是：当轮到棋手走时，他可以决定选择哪一步棋走。如果起码有一步可以担保棋手
能够到达赢的棋局，那么棋手就会选择这一步并保证能够取胜。因此对应于棋手走的节点
是一个或节点。
当轮到对手走时，选择是由对手决定的。棋手没有任何选择的权利。只有对手的所有可以
走的棋布都会导致棋手赢时，这时棋手才能保证会赢。因此，对于对手走的结点是一个与
节点。
对于一场经过深思熟虑地棋局来说，其博弈树是非常庞大的（国际象棋来说有10^120个节
点）。以至于不可能把这样大的博弈树装入计算机，也不可能在任何合理的、有限的时间
内进行详细的搜索。尽管如此，首先深入的考察一下完整的博弈树，然后再看看如何来修
正我们的原来的想法，
以便把搜索树修整到一个合理的范围。这样做还是很有意义的。
博弈策略
假设我们对所讨论的博弈问题构造了一棵完整的博弈树，我们希望能从中找出棋手应采用
的策略。这种策略应当确保棋手会赢，或者起码能够得到和局的结果。
首先我们把该博弈树的每一个节点标上w（对应于赢）、d（对应于和局）或者l（对应于
输）。如果当前的棋局对应于标有w的节点，那么就存在一种策略可以担保棋手会赢；如
果结点标的是d，那么除非对手失误，否则棋手最好的前景就是争取和局；如果节标的是l
，那么棋手只好认输了，
除非对手下错了棋。
对一个节点标以w、d和l的过程，可以如下进行。
我们的讨论从叶节点开始，每一个叶结点对应于一场棋赛的结束的终局。根据博弈的规则
，叶节点确定了棋手的赢，输和和局。这样，我们就把每一个叶节点标上相应的值。
现在我们按照从叶往根本方向进行研究。按照每一节点的子节点的标号来标记该节点本身
。节点标注的规则如下： 轮到棋手走步时，如果该节点的子节点至少有一个标有w，那么
，该节点就标为w；如果所有子节点都标为l，那么该节点标为l。其他情况标上d。
轮到对手走步时，如果该节点的子节点都标上了w，那么该节点标为w；如果有一个以上的
子节点标上了l，那么该节点标为l。其他情况标上d。
根节点的标注表明，在对手不失误的情况下，棋手能够得到的最好结果。如果根节点为w
，那么棋手稳 *** 胜券；如果为l，那么对手一定能击败棋手；如果为d，那么在对手不失误
的条件下，棋手能够得到的最好结果就是平局。
一场比赛，如其根节点能够标上w或l，并且是很简单易于分析的话，就可以成为骗人的棋
局。该节点标作w的话，无论是谁先走，先走者都能赢；根节点为l的话，无论谁后走，则
后者也一定能赢。当然需要采取正确的策略。骗子知道哪一方面能够赢，以及要赢所需要
采用的策略。而这些，
受骗者肯定是不知道的。
棋手的策略应该遵循这样的原则：如果有一步棋能走到节点为W的棋局，那么就应当走这
步棋；如果所有的棋步都通向节点为l的棋局，那么就只好放弃这盘棋认输。其他情况下
，就要走到标为d的节点。
对手采取的策略正好相反：如果有一步棋能走到节点标为l的棋局，那么就下这步棋，如
果所有的棋步都通向节点为w的棋局，那就只有放弃认输。其他情况下，就要走到标为d的
节点。
当有两条以上的路径都能通往l节点，或者有两条以上的路径通往d节点时，棋手所采取的
策略就不再是决定性的了。在实际对弈中，棋手总是想选择w节点，达到了w节点，就使得
往后的对弈过程变得简单了。这样做就能减少棋手失误以致失去优势的机会。基于同样的
理由，棋手在达不到节
点时，应该选择d节点。这样就可以导致最复杂的情况产生。希望对手在这种情况下失误
以便使自己重新得到优势。到现在为止，我们的讨论还是很不充分的。因为在所有的w节
点或者所有的l节点之间，我们并没有给出任何差别。学生与修表师父间的博弈。一个学生的瑞士手表坏了，他到博实商店找到修表师父。修表师父告诉他其中一个配件坏了，需要花30元修理费。但是学生私下得知：如果师父给他换的是进口配件，那么师父要花20元成本费（包括购买配件和劳动成本）；而如果换的是国产件，他只需花15元成本。如果换的是进口配件，学生的手表便可以正常使用，他得到的净收益（扣除30元成本）换算为10元货币；如果换的配件是国产的，则不匹配手表性能，尽管表面上无法识别，但是会损坏其他手表配件，此时学生得到的净支付（扣除30元成本）为－10元。这个博弈可以看作是两个阶段进行的。在第一阶段，学生决定是否信任该修表师父。如果学生选择不信任，那么他不会在博实修表双方净支付都为0；如果选择信任，他将付给该师父30元。此后，修表师父有两种选择，即选择提供高质量的进口配件或者低质量国产配件。
A、通过简单计算，请写出该博弈的扩展形式即博弈树。
B、给出该博弈的精炼纳什均衡。
福州大学计算机科学与技术考研经验分享
就今年就业行情来看，不是很建议跨考计算机了，或者考研至少要进行一个学历跨越。怎么说呢，今年找工作比去年差很多很多，难很多很多，后面会不会回暖不知道，我现在说的也不一定以后也对，反正我今年找工作是自闭了，多重原因吧。希望后面的学弟学妹考研前多想一想三年后211硕士毕业又能找个如何的工作呢，切勿心比天高，命比纸薄。
以下是正文
01
自我介绍
本科来自福州大学的食品工程，跨考福州大学数计学院计算机专硕，复习时间从七月份开始，中间做了两周课程设计，充分复习的时间为5个月。初试总分为438分。最终以初试第一总成绩第一拟录取。
其中：数二137，专业课137，英二84，政治80
02
公共课初试心得分享
21数学
用书：《1800题》，《闭关修炼》，《李永乐全书》，《张宇四套八套卷》，《李永乐六套卷》《李林四套六套和108题》。另外自己还找了汤家凤八套写了三四套，张文斌的四套，PDF用ipad做的，还有共创和超越的也写了十多套。
视频：汤家凤基础+强化、张宇强化部分章节、武忠祥高数十七讲部分章节。
复习安排：
1、7月份：先看汤家凤高数基础部分，做1800基础篇；大概需要一个月
2、8月份上旬：然后花了一周学了一遍线代，选了部分1800基础篇的线代做做
3、8月份：汤家凤强化视频（包括线代），认真完成1800强化篇；大概需要一个月
4、9月份：《闭关修炼》和张宇强化视频，张宇强化视频挑选自己薄弱的方面看看，推荐看看数列极限。
5、10月份：大概国庆开始写真题。我只写近15年，基本一天一卷（这个根据实际效果调整，我是写的都挺顺的，就直接写完了，真题测试成绩基本能反应你前阶段复习的基本知识是否到位）。做完真题花了大概一周整理，期间看了武忠祥高数17讲的部分章节，推荐中值定理、积分几何应用、二重积分。十月剩下的时间我又按章节刷了一遍真题。
6、11月份：剩下的时间基本就是模拟卷了，基本每天一套，反复夯实知识点，复习错题。
7、12月份：接近考试的时候又过了一遍10年后的真题。
高分秘诀：
（1）主要看汤家凤老师的视频，张宇的数列和极限讲的比较好，这个部分跟张宇的视频学习；
（2）李永乐老师的视频看的不适应，因此线代部分就用了李永乐老师的资料做一做。每个人对于考试老师的选择都不同，关键在于找到适合自己的老师，跟着老师学做题的思路，但是对于题目的敏感度和熟练度要通过自己的大量的练习巩固。
（3）注意总结知识框架与题型，也总结错题，不断地复习错题。
（4）重视真题，刷了十五年真题，并把李永乐真题册分章节刷了一遍巩固。考前又过了遍近十年真题。
22 英语
用书：真题 + 单词书，真题是《黄皮书》
视频：唐迟阅读，刘晓燕作文强化课
安排：
1、全程背单词！！！单词一定要过关。
2、8月下旬一直到初试前：真题首先只做阅读理解，一天一篇，整理生词，能全篇翻译。
3、10月底开始准备作文：听了下刘晓燕的作文课。后面自己要准备个大概模板，也要能自己熟练运用几个句型，问题不大的。
高分秘诀：
（1）主要从单词入手，利用背单词软件（扇贝），前期每天背六七十个单词，后期每天背两三百个单词，刚开始会比较陌生，但是熟练了就还好。
（2）不要担心自己地英语的功底，考前我只过了四级，六级没过。通过考研英语复习，在今年也过了六级，大概510+。
（3）英语我讲究效率，语法和长难句不必过分深究，主要是看得懂文章意思。
（4）重视真题，通过阅读整理陌生词汇，要做到能全篇文章正确翻译。
23 政治
用书：《肖秀荣1000题》、《知识点提要》、《肖四肖八》。这里提一句精讲精练和徐涛的那本教材都可以不买，反正我是听课时也没怎么划，听完了课也没怎么翻。听课主要是图个乐放松放松。
视频：徐涛强化课、徐涛刷题班、徐涛时政
安排：
1、9月份到肖八出来之前：就刷刷徐涛视频，做做1000题。重点章节1000题需要重复刷。真题的选择题可以做一下。
2、《知识点提要》是10月左右出的一本书，出了之后就买来，多翻翻，错题相关知识点也可以到上面找。
3、11底到12月初：肖八出来之后，肖四出来之前，就是做各种模拟卷的选择题。要整理错题，只要摘录关键句子。
4、12月初到初试：肖四出来之后就是背肖四了。
高分秘诀：
（1）政治要想高分，关键在于选择题，我选择题得了45分。
（2）政治的发力点在肖八出来之后，大题背诵部分集中在肖四。
03
专业课初试心得分享
用书：两本参考教材、王道数据结构、三研福大白皮书系列（初试白皮书，最后预测六套卷）；
跨考基础：没学过C++，但是会Java，数据结构也知道一些；所以开始准备考研的时候算不上零基础。
视频：准备考研期间是没怎么看相关视频。前期自学C的时候看了慕课上翁恺的视频（效果相对一般，但是0基础的可以看看下），C++快速的过了一下b站上小甲鱼的视频（意义不大，毕竟和考试的相差还是很大）。
高分秘诀：
（1）跨考的原因是：本科其实是调剂到食品工程，对计算机比较感兴趣，也不算零基础。对于想要跨考的21备考生一定要先学好一门计算机语言，最好是先学学C++。不在于能掌握语言细节，而是能用它实现数据结构，写出算法即可。
白皮书系列真题和答案比较完整，每年的题型变化很大，但是重点内容一般不变，但是与王道的数据结构侧重点不同，要研究真题，一些福大特有章节可以结合白皮书学习一下。
（2）白皮书系列真题和答案比较完整，每年的题型变化很大，但是重点内容一般不变，但是与王道的数据结构侧重点不同，要研究真题，一些福大特有章节可以结合白皮书学习一下。
专业课安排：
1、先学习了自己不太了解的数据结构。零基础的要先学c。
2、7月份：把《王道》的书过一遍。基础差点的可以看《天勤》。
3、7月底到8月初：然后就可以学C++的相关内容，有基础的好学，基础不太好的找点视频看看，福大参考教材我觉得没必要仔细翻，福大C++的题型不是很稳定，说不上很难，但是也要重视，C++跟着福大白皮书差不多了。
4、8月初到9月底：这个时候可以学习白皮书的内容，大概是八月多开始。大概花两个月，这两个月要基本讲数据结构和C++拿下。
5、十月份：十月多可以看看福大数据结构参考教材。王晓东还有一本算法书，有能力的也可以去翻翻。
6、11月份到12月份：再后期就是《白皮书最后冲刺六套卷》+温习。对数据结构有关的重要算法全部掌握，每天一个数据结构轮巡着复习就好。
高分秘诀：
（1）算法部分，开始准备考研之前有翻一些算法书，也听过慕课上北大的那个算法课，然后结合数据结构的算法进行学习。
（2）C++刚开始的时候只做了一些知识点的复习，刷了一些计算机二级的题，但是跟福大的题型不太一样。然后做白皮书的里面的C++试题差不多足够，跟福大的考试题型相似。
（3）最后的《白皮书》系列是福大研究生学长们自己做出来的考研资料，比较贴合福大专业课，有一些考试的新题型出现在上面，比如堆排序的时间复杂度分析以及并查集等。
政治：接近九月份开始的政治。看了一个月的网课（徐涛的强化班），
带着做肖秀荣1000题。
十月份把1000题写完，这时候腿姐的选择题技巧班出了，不想学习的时候看看，罪恶感没那么强。
十一月份，看了徐涛的小黄书，当然，腿姐的冲刺背诵笔记也不错，
然后二刷了肖秀荣的1000题、肖秀荣八套卷。这时候有徐涛、腿姐的代背，我早上起床会看看听听，缓解一下困意。十二月份主要就是背肖秀荣四套卷。因为背书，没怎么看选择题，导致考试前选择题忘了很多。
数学：七月份开始，跟的是武忠祥高数、
李永乐线代、
余丙森概率论，
当然，大家也可以看看汤家凤、张宇。七八月份听完了对应的基础课、强化课，把相应的辅导讲义也给看了一遍，做了高数、线代、概率的配套习题。然后八月二十号我就开始写真题，十月五号的时候，写完了真题35年，用的是汤家凤的真题，这段时间看的是李艳芳的真题课讲解（强烈推荐）。
十月份把书又看完了一遍，辅导讲义很重要，第二遍还有蛮多不会的。十月二十号左右又把2010年后的真题做了一遍。十一月份，当年模拟题还没出的时候，我把去年的李林6+4做了，
然后不久当年的模拟题也出来了，我做了张宇的过关8+4，提高8，余丙森五套卷、
李林6+4，还有方浩、李艳芳的没做完，太难了。有部分模拟卷我是买的答题纸做的，最后大概用了十五张的答题纸，这样可以模拟考场。个人感觉，张宇是蛮符合今年的出题风格。十二月份，我做做模拟题，把真题又看了一遍，个人感觉真题很重要，假如时间够，建议把2010年之前的也都做了，感觉到有蛮多重复出题的点，以及前面题目的改进。
英语：七月份开始，每天早上背400个单词，我没有看延伸的扩展，十二月份每天就没有400个了，记录我背了9800多个单词。晚上写写真题，用的是张剑黄皮书，
主要是阅读，不会的就去瞅瞅唐叔对应的课程讲解。
十月份开始看看翻译、新题型，瞅了瞅唐静的翻译课和刘琦的新题型课。十一月五号，我开始作文，我看的是周思成的作文课，大家也可以看看王江涛、潘赟、石雷鹏，评价都很好。十二月十号后，我每天英语就练练作文（买的作文的答题纸）、看看以前的阅读。个人感觉学习英语是最快乐的，每天两三个小时学习英语。
（1）英语
需要准备的资料很少，如果基础也不错，就可以不用花很多时间。我是大一六级踩线过这样的水平，考研英语前期准备的很少。朱伟的恋词对着视频看过一遍，累的时候看看会很轻松。后面再每天早上背一背，一本书也看了3遍，到11月左右的时候再开始做真题。重点是近几年的真题。我把10年之后的真题阅读部分，每篇翻译，生词整理出来，一篇一篇的分析每道选择的答题技巧和套路。背了王江涛5+5的作文，
最后考试的时候直接默了一篇上去。作文真的很重要，建议就是不要去买什么模板这些，没必要，直接背几篇作文（一个老师的全套），各种话题都涵盖了。考试的时候只要搭点边就可以了。扣不了几分，绝对比你自己临场发挥的强。除非你有把握，自己的作文真的很好。默写一篇作文，然后省点时间给阅读，它不香吗……
（2）数学
数学真的很重要，很拉分！前期至少百分之60-70的时间放在数学上面吧。我的数学是全程跟着张宇的，很喜欢张宇的上课风格很幽默，而且他讲的难度比较大，很适合做题，方法什么的也很好用。跟着他走全程，一定是全程吧，这样就不会有漏洞了，重点知识他会反复讲，自己也有数。
我在8月份之前看完了张宇的高数18讲，
他的课看了前一年的，所以不用等更新，会很快。线代和概率是听张宇的视频，看李永乐团队的线代和概率统计辅导讲义。然后八月份开始刷题，题海战术很重要。两个月的时间，我刷了张宇的1000题，李林的880题、660题的高数部分。先做到的1000题，难度很大，很崩溃，做的时候可以找一下1000题的配套讲解视频，很好用，答案密密麻麻的，看不进去，而且很多方法不太能接受，配套的视频看了就会豁然开朗，浅显易懂。880题同步做的，会发现李林的题风格似乎和张宇很像，有些题可以作为补充。同理，不会写的题去找视频看，他会把一系列的知识点讲一下，比只研究答案好很多。
我网上找了这些课本的pdf，做完每一章节的题，我会把错题截出来，很方便。后面可以再做一遍。建议至少一定要完整的做完一位老师的习题集，这样知识才是成体系的。
后面的时候心态有点崩，就什么习题都想做。闭关修炼，108题等都买了，总觉得都要写一遍才可以。尤其新大纲出来网上在传李永乐的题会更适合新大纲，所以又买了660题+330提+临阵磨q等全套的习题。计划着每天做多少题，很快就能结束。最终做完1000+880之后，只来得及做完660的高数部分。
10月份一定要开始刷题了。我用的张宇的真题，好像是从87开始的，每天一套。一样的，看视频讲解，近些年的真题从头看到尾的视频，看看自己的思路是不是和标准思路一样，自己的方法是不是最简单的，还有哪些知识漏洞，没想到的知识点，按照年份做好笔记。错题、好题用软件截出来。可以二刷。
11月中下旬和12月开始刷错题集、背知识点、刷模拟题。模拟题我觉得挺重要的，恰好时间做，难度比实际考试难一点点，多做几套感觉会上来的。所有老师的预测我应该买的比较全，然后做了张宇的8+4、李林的6+4、李永乐6套卷，汤家凤12套。难度上张宇>李林>李永乐。质量也是张宇>李林>李永乐，张宇的题就每道题涉及到的知识点很多，弄懂一道题，就会学会一系列的知识点。李林的题没有张宇那么难，但是也很有价值。李永乐的题感觉，不太适合我的风格，出题点太细节了吧……不太喜欢。汤家凤的题，做一套一套150，没有任何价值了……做了几套就没做，过于基础。
刷模拟卷的同时，错题集同步做好。每天回顾一些之前的错题知识点。
最后数一131分，觉得其实还能更高些的，21年的不算难，做题的时候发现，很多题都非常的熟悉，仿佛做过。
（3）政治
政治没有太早进行，到11月左右开始的吧。买了徐涛的全套（真题集没），把他的视频很快过一遍，然后习题集对照着视频快速刷一遍，没记下太多，一两周的时间就结束了。然后小黄书知识点多翻一翻，配套小黄书做了肖秀荣1000题，也很快2个礼拜左右，正确率不高，但是对应着1000题讲解视频，还有小黄书知识点，这会能记下些东西了。
肖八出来的时候，把选择题做了，两天做完……最提分19分，高点的37左右。同样电子版的资料准备好。在肖四出来前，肖八还有之前1000题以及优题库习题集快速再过一遍，尤其错题。
肖四出来之后整篇背诵！很重要！不要再去找什么杂七杂八的资料了！我是最后一个礼拜，将肖4的简答题大体背了一下，背诵笔记（小黄书）翻一翻，网上找到的各种简答题也整理了一部分，一块看。因为最后一段时间网上政治预测题太多了，导致眼花缭乱。下载了一大堆，今天背着个，明天换那个，就乱了……看的太多反而什么都没记住，没能抱紧肖爷爷大腿，拿到试卷，题目都见过，答案没背住的感觉，更气的是，考完看参考答案有一段话我背下了，但是没背题目，没对应上题，居然没写！
英语：这一阶段我主要是进行了单词的背诵记忆。买了单词书，但是学习的过程中发现对我自己而言，单词书学起来效率比较低，所以我主要还是用的背单词软件。百词斩、扇贝、墨墨都下载使用过，最后用的最好的是百词斩，页面比较简介，缺点可能是词义设置上偏简单。大家可以结合自己的情况选用。用APP背单词好处是可以随时随地，方便我们利用好碎片时间。专业课：我在2021年注会轻一教材出版后，开始学习税法部分。老师跟的是东奥的王颖老师，讲课风格我很喜欢，节奏适中，15倍速听课正正好。税法这部分内容繁琐，有很多细节需要注意。对我来说只是看书勾画的话记忆不够深刻，所以我用画思维导图的方式帮助自己理解。如图所示：
一、 关于专业科目设置
1、计算机原属“数学与计算机科学（软件）学院（拟招收286人）”；今年分为“数学与统计学院(拟招收61人）”、“计算机与大数据学院(拟招收280人）”，两个学院。计算机专业也就理当属于计算机与大数据学院了。根据往年的经验和今年导师的说法来看，计算机与大数据学院报考人数较多，还会继续进行扩招，至于最终招生多少，成绩还没出来也说不准，估摸着应该上300+人数吧。
2、21年专硕统一属于085400电子信息，且并分为三个方向；但22年专硕再次回到以前的模式分为"085404计算机技术（专业学位）"、"085405软件工程（专业学位）"。所以我猜想今年可能会按照这三个方向单独招生，单独切线，至于每个专业招生多少人，要等到国家线出来以后才知。
二、 关于官方公布的复试参考书
1、计算机系统结构（学硕）
[1]张尧学等计算机 *** 作系统教程（第3版）清华大学出版社，2006；
[2]谢钧等计算机网络教程（第4版）人民邮电出版社，2014
2、计算机软件与理论（学硕）、软件工程（学硕）
[1]张尧学等计算机 *** 作系统教程（第3版）清华大学出版社，2006；
[2]麻志毅面向对象分析与设计（第2版）机械工业出版社，2018;
3、计算机应用技术（学硕）
[1]马少平等人工智能清华大学出版社，2004；
[2]谭浩强C++面向对象程序设计(第2版) 清华大学出版社，2014
4、信息安全（学硕）
[1]杨波现代密码学（第4版）清华大学出版社，2017；
[2]谢希仁计算机网络（第7版）电子工业出版社，2017
5、计算机技术（专硕）、软件工程（专硕）、人工智能（专硕）
[1]张尧学等计算机 *** 作系统教程（第3版）清华大学出版社，2006；
[2]马少平，朱晓燕人工智能清华大学出版社，2004
三、 关于复试录取
计算机类硕士研究生复试阶段所考察的内容主要分为三部分（以线下为例）：通常是笔试、机试（学术型硕士没有机试）、面试。复试总分记为100分，则其中机试一般占10%，专业课笔试（含英语）占比50%。面试占比40%。去年是线上，如果是线上的话，一般是英语综合能力测试20%，专业知识测试40%（这个其实就是把线下笔试的题目拿到线上来提问，是拉分的关键点，严重影响老师对你的印象），综合素质及能力测试 40 %（这个正常发挥的话，差距一般不会很大的）。
录取原则是：
（1）复试的总分不及格不录取
（2）总成绩（百分制）= 初试成绩（折合为百分制）70% + 复试成绩40%。（因为22年复试细则还没公布，我暂时按照复试占比百分四十来算）
（3）分数按照总成绩（初试和复试后的加权分数）从高到底录取
总的来分复试还是非常关键的，我们这届有初试相对高分被刷，也有初试压线，复试逆袭录取的。为什么这么说呢，假设我初试成绩400分的话，复试80分的话，那么总成绩就是400÷5×06+80×04=80分。也就是复试的1分等同于初试的3分！
四、 关于复试经验
1、 首先是英语的自我介绍：这部分的时长建议控制在2分钟以内，主要着重介绍下个人的基本信息、本科的学习经历（如果有比赛、项目、论文更佳）、个人的兴趣按照（最好可以和科研沾边一下）。
2、 笔试内容的提问：这部分大家都是抽题的方式进行（会给你一定的思考时间），一般都是从官网推荐的复试参考书中抽取。我的复试科目是 *** 作系统和人工智能。因为初试考的是408计算机专业基础综合，里面有包含 *** 作系统了，不过福大的 *** 作系统有指定的参考书，一般情况下还是建议看下福大官方指定参考书，额外补充一些《计算机 *** 作系统教程》这本书上关于Linux、Windows相关知识。不过最让我吐槽的还是马少平老师的这本《人工智能》，一个是这本书的实在是晦涩难懂，里面的知识点也相对比较古老、陈旧，网上配套的资源和视频基本没有，就找到了一个清华大学的视频，但是视频十分的模糊。实在没办法了，我前前后后大概看了五遍，才慢慢掌握了一些知识和讨论。但是强调下，这本书非常非常非常重要，我复试面试的时候问了两道人工智能的题目，启发式搜索A、A算法的原理，还有一个是博弈树搜索。对了，关于这本书推荐的额外复试人工智能资料就是研福大整理的复试白皮书，做这本书上的相关练习题。
3、 关于综合面试：这部分就不好归纳了，因为问题实在是很广，会问你本科的项目经历、比赛经历、本科成绩、毕业设计等，偶尔还问一下前沿知识，比如AI、大数据、计算机视觉等。关于前沿知识这个也可以看研福大上面的复试白皮书，基本上去把这几年的复试面试题过一遍就足够了。
PS：我被问了英语口语，就问了一个问题，我临场反应用英语回答了，但是好像老哥都没有英语口语啊，这个和面试组的老师风格也有关系，建议大家也准备下。
04
总结与结论
各科提点：
1、绝大多数时间花在数学上，尤其是专业课基础还不错的。每天一个上午是至少要保证的。
2、英语一定是围绕单词和真题是性价比最好的方法。
3、政治后期刷好的各种预测卷选择题，是选择题取得高分的一个不错方法。
4、专业课有能力的算法部分最好不要放弃。基础一般的也得学一些。
时间规划：
1、要有自己的进度安排，要心里有数，明白自己需要完成的任务，来调整适合自己的计划。
2、暑假开始全身心投入复习后，最好不要打断节奏，其他活动能免则免，除了做课设两周，其他时间在图书馆复习满五个月。
3、不建议晚睡，建议早起（630），六点半到图书馆，晚上十点闭关回去，不熬夜学习。
4、晚上偶尔可以去运动一下，坐久了可能真的会腰疼
在之前的讨论中，一场游戏只有一个智能体。而在博弈论中，智能体评估它们的决策如何与其他人的决策相互作用以产生不同的结果。
看一个具体的博弈游戏：
这是博弈问题最简单的一种： 两个玩家的零和有限确定性完美信息博弈 。
在 MDP 中有个名词叫 POLICIES （策略），它是状态到动作的映射。博弈论中有类似的概念，称为 STRATEGIES （策略），它是所有可能的状态到动作的映射。
对于 A 来说 (1→L, 4→L) 就是一个策略。不难看出，在这个特定的游戏中，A 有4个策略，B 有3个策略，如下：（这种策略被称为 纯策略 ）
我们可以以表格的形式写出这些策略，并在中间填入最后的得分。（由于B得分是A的相反数，所以这里省略B）
最终可以得到一个矩阵（红框部分），这个矩阵包含了此场博弈的一切信息，即：有了它我们不再需要一开始的博弈树了。
试想这样一个游戏过程：
A 总是最大化得到的分数，而 B 总是试图最小化 A 可以得到的分数。所以得出这样一个结论： A 先手时必须要考虑会遭遇 B 最严酷的反制策略 。所以选择 (L,L) 是非常不明智的。事实上若交换 AB 角色，结论是一样的。
在这个结论的指导下，A 要选择的并不是全局最大值，而是在 B 执行反制策略（找到极小值）后得到尽可能大的值。也就是：极大化极小值。相反，B 要找到极小化极大值。（因为值越小 B 得分越高）
所以正确的博弈过程是这样的：
从这个过程可以得出一个结论：极大化极小值和极小化极大值最终的结果是一样的。
极小极大原理也就是 Von neumann 定理 （冯诺依曼定理）。
前面所述简单博弈具有确定性，现在我们取消这一约束。看一个具体的游戏：
同样的，只需要用概率乘以得分再求和，也可以写出一个博弈矩阵：
前面所述博弈是完美信息，现在我们取消这一约束成为 两个玩家的零和有限隐藏信息博弈 。
看一个具体的游戏：
因为 B 不知道 A 抽到的是什么颜色，故不知道自己处在哪一状态，也就是隐藏信息。
同样的可以得到一个矩阵：
不难看出，在这场博弈中，Von neumann 定理不再有效了，它无法在不同情况下得出一个确定的结果。
混合策略与纯策略的区别就是， 需要指定选择不同策略的概率 。如此看，纯策略是特殊的混合策略，其选择某一策略的概率是100%
令 A 选择留牌的概率是 p，那么当 B 选择弃权时，A 的预计收益是
当 B 选择亮牌时，A 的预计收益是
不难看出这是2个关于p的函数，可以把它画出来：
由于 B 始终希望最小化 A 的奖励，所以 A 实际的奖励函数应该是取最小的部分（下图红色部分），也就是极大化极小值。
同样的，**部分是极小化极大值。他们最终应该选取的点相同。
前面所述博弈是零和的，现在我们再取消这一约束成为 两个玩家的非零和有限隐藏信息博弈 。
同样，先看一个具体的博弈：
类似地，可以表述为一个矩阵。但由于这里不是零和了，因此 AB 双方的得分都需要列出。
显然，相互合作不揭发对于这个犯罪团伙是最好的方案。但实际上并非那么顺利。设想下面的情况：
因此最终他们会互相检举从而均被判刑6个月，这不是想要的最佳方案。这被称为 囚徒困境 。
NASH 均衡，英文 nash equilibrium ，也被音译为 纳什均衡 。
当且仅当对于所有的 n 个玩家，各自选择的每一项策略都使此玩家效用最大 ，即为 Nash 均衡。
更好理解的解释是：当所有玩家都知道其他玩家的策略，任意选择一名玩家允许他改变策略，他都没有理由改变，因为当前策略可以最大化效用。
Nash 均衡的定义适用于纯策略和混合策略。
对于这个具体博弈，A 选择检举（第二行）总是要比合作（第一行）更有利（0>-1, -6>-9）。可以称为第二行 严格控制 第一行。
这也就意味着如果选择了第一行的任何数据，那么总是应该倾向于选择下一行，因为它更有利。
在囚徒困境中，整个团体无法达成最佳策略。那么对于一个连续的囚徒困境博弈问题，是否可以通过先驱的博弈建立信任从而达到最佳呢？可惜答案也是否定的。
假设连续进行20场博弈，对于最后一场博弈来说，可以认为由于建立了信任，对方一定选择合作，基于最大化自己利益，这正是检举对方的好时机。因为双方都有这种想法，于是再次落入了囚徒困境。
因为第20次博弈结局已知，所以第19次博弈可看做是最后一次，根据归纳法不难看出，每一次博弈都将陷入囚徒困境。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）