五子棋终结者，这个电脑执黑必胜的程序，为了完成打败熊BOSS的夙愿，我决定将其中的一部分算法加入到我的五子棋AI中来。可以说其中的核心算法已经实现了（必胜树）。当然，由于时间的仓促，整体并不完善，还有些不足。但是程序是永远都写不完的，这是个普遍真理。不是吗？
首先，我们先看看原作者的想法“
五子棋终结者终结五子棋的计算引擎分为三层， 第一层是目标控制 第二层是策略规划 第三层是急速攻杀判断有无解 为什么要这样做这么多层次？因为五子棋是不可能通过简单的暴力搜索而被解决的 多个层次可以方便矛盾的转化，上层的策略由分散给底层去实现，底层的矛盾可由上层策略化解，而使得系统虽局部有缺陷而整体上合理，， 第三层只能终结部分有VC解的棋局而三个层次结合起来连续运算可以终结整个五子棋， 每一层次都有各自的目的和缺陷，而整体上却能实现当初的目标。 算法中引擎的三个层次要结合起来思考，才能明白这个分为三层的系统是如何终结五子棋的 目标控制层 受限于计算机能力，五子棋终结者是不可能一次搜索就被全面终结的，而是不断地从主要干支到次要枝叶到全面终结的一个目标渐进过程。此层引擎只是一个for循环，逐步放大终结目标的宽度，从5到10到30到50到225，当到225时，五子棋就被完全地终结了。 策略规划层 最佳优先与或求解树引擎。不要看到名字这么复杂，其实就是一个不断扩展发展M叉树。让最可能获胜的棋子获得CPU，棋子的优先度根据下层的结果动态计算调整，也称作反馈，直到分支在当前的目标宽度下被终结。 急速攻杀层 VCF和VCT，简称VC，也就是连续攻击取胜引擎。求解速度和求解严格精确至关重要。 如何在0.01S内进行深度为几十步的攻击？计算攻防时黑与白之间的无关性以及各自的相关性是关键。 无关性的考虑可以化解对方的随意反攻， 相关性的考虑可以使自己的进攻关联，保持节奏和组织性，不至盲目， 二者结合才能避免树产生爆炸，从而秒断棋局是否有连续攻击取胜解。 第三层引擎的这种相关和无关的考虑虽然可以秒断棋局，但却无法断所有的VC棋局解，因为不是全面的VC搜索 不过这没关系，第三层引擎只要能够准确地秒断绝大部分棋局的VC解即可 部分棋局无法求出解的缺陷却可由上层引擎对M叉树的扩展化解 总体上一致即可 三个引擎调试好后，执行终结命令，经过半个月的连续计算后，会生成一个完整的地毯必胜树，树的所有叶子都是可以VC求解的，如果程序设计上没有漏洞，那么是必胜的。 终结者程序很小，删除垃圾测试代码后的真正代码只有几千行，编译结果只有几十K（不包含资源文件），而且运行只需要几M的内存，必胜树只有八十万个节点，内置于程序中。
”
不知道你看完后是否有种一口鲜血喷在屏幕上的感觉，说句话刚看到上面这段我脑袋只闪过一个字，“这家伙在讲什么”。嗯，但是，看着看着就看懂了。
第一个层次，是目标控制层，话句话就是控制，相应的步数对应相应的算法的。
可能作者第一步只有1种算法，到了一定的步数他就会有另外几种算法。通俗点说，就是见什么人说什么话。
第二个层次，整个五子棋算法的核心，策略规划层。说白了就是一颗兄弟孩纸树，地毯式的必胜树。这棵树你们肯定见过，没错他就是二叉树。
电脑执黑子，玩家执白子。电脑下子后，玩家再下子，此时电脑会对根据整个棋盘的情况一一对电脑黑棋节点下的白棋节点进行遍历，当找到与之匹配的白棋节点，再将指针指向白棋的孩纸节点，取出节点中的数据并落子。
数据结构基础：
每一个棋局是一个节点，每个棋局有许多子棋局，节点的树型关系也就是棋局之间的树型关系。
从理论上来说，只要数据量足够大，玩家就会下不赢，后手无禁手的电脑。
第三层是急速攻杀判断有无解：
就是判断整个棋盘上是否有双三，三四，双四等必赢得情形，基本理论应该是权值法，不断的进攻最后玩家失败。
我猜想，作者先用第一层，判断玩家的进攻的相关性，再选择合适的算法来应对，如果玩家的进攻无关，则选用一种能迅速解决棋局的算法。如果是具有相关性的则选用第二层引擎，当达到一定步数时，玩家已经处于必输的局面，此时在调用第三个引擎。再次声明，这只是我的猜想。
还需完善的地方：1.必胜树还未建立好，不知道作者是怎样生成80万种情况。（感觉人工输入是不可能的，累死人了）
2.相关性和无关性的判断这个真的很麻烦。我就做了第一步下在四周的无关性检验。
3.三种情况的相互调用，在何种情况下相互调用，这又是一个值得思考的问题。
4.做完一种情况，因为棋盘是对称的，所以可以将树旋转，获得新的四种情况。
5.如何将机器学习与之结合，又是一个问题。
后记：五子棋做到现在，大体上是差不多了，感觉之后很长时间不会再碰这个东东了，下一次是否能将神经网络或者遗传算法加入到里面去，还是等我的功力再提升一点再说吧！
附代码：
必胜树类
package GobangV1_4_0517;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
public class Tree {
private Node root;// 根节点
public Tree() {
if (!readFile()) {
root = new Node(null, null, 7, 7, 1);// 第一步下在中心位置
System.out.println("读取文件失败");
}
this.initRoot();
}
/**
* 遍历树
*
* @param node
* 根节点
*/
public void printTree(Node node) {
if (node != null) {
System.out.println(node.getX() + " " + node.getY());
printTree(node.getChild());
printTree(node.getBrother());
}
}
private Node tempNode;// 当前位置所在节点
public void deleteNode(){
tempNode.setChild(null);
}
public void addtoTree(int i, int j) {
if (tempNode.getChild() == null) {// 如果孩子节点为空
Node child = new Node(null, null, i, j, data.ARRAY[i][j]);
tempNode.setChild(child);
tempNode = tempNode.getChild();
return;
}
tempNode = tempNode.getChild();
while (tempNode.getX() != i || tempNode.getY() != j) {
if (tempNode.getBrother() == null) {
Node brother = new Node(null, null, i, j, data.ARRAY[i][j]);
tempNode.setBrother(brother);
tempNode = tempNode.getBrother();
break;
}
tempNode = tempNode.getBrother();
}
}
public boolean readFile() {
try {
File file = new File("save.txt");
FileInputStream is = new FileInputStream(file);
ObjectInputStream ois = new ObjectInputStream(is);
root = (Node) ois.readObject();
ois.close();
is.close();
return true;
} catch (Exception e) {
// e.printStackTrace();
}
return false;
}
public void saveFile() throws Exception {
File file = new File("save.txt");
FileOutputStream os = new FileOutputStream(file);
ObjectOutputStream oos = new ObjectOutputStream(os);
oos.writeObject(root);
oos.close();
os.close();
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
public void initRoot() {
tempNode = root;
}
public Node getTempNode() {
return tempNode;
}
public void setTempNode(Node tempNode) {
this.tempNode = tempNode;
}
}
节点类
package GobangV1_4_0517;
public class Node implements java.io.Serializable {
private static final long serialVersionUID = 1L;
private Node brother;
private Node child;
private int x;
private int y;
private int which;
public Node() {
}
public Node(Node brother, Node child) {
this.brother = brother;
this.child = child;
}
public Node(Node brother, Node child, int x, int y, int which) {
this.brother = brother;
this.child = child;
this.x = x;
this.y = y;
this.which = which;
}
public Node getBrother() {
return brother;
}
public void setBrother(Node brother) {
this.brother = brother;
}
public Node getChild() {
return child;
}
public void setChild(Node child) {
this.child = child;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getWhich() {
return which;
}
public void setWhich(int which) {
this.which = which;
}
}
下棋与控制类
package GobangV1_4_0517;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
public class chessListener extends MouseAdapter implements ActionListener {
private Tree tree;
private chessBoard cb;
private fun fun;
private int mode;
private judge panduan;
private boolean flag;
public chessListener(chessBoard cb) {
tree = new Tree();
fun = new fun(cb);
panduan = new judge();
this.cb = cb;
}
@Override
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("保存到文件")) {// 保存到文件
try {
tree.saveFile();
} catch (Exception e1) {
e1.printStackTrace();
}
}
if (e.getActionCommand().equals("录入棋盘")) {
tree.initRoot();
clearBoard();
data.ARRAY[7][7] = 1;
cb.repaint();
mode = 1;
}
if (e.getActionCommand().equals("人机对战")) {
tree.initRoot();
clearBoard();
data.ARRAY[7][7] = 1;
cb.repaint();
cb.appendText("遍历为：");
printTree(tree.getRoot());
mode = 2;
flag = true;
}
if(e.getActionCommand().equals("删除节点")){
tree.deleteNode();
System.out.println("hi");
}
}
public void printTree(Node node) {
if (node != null) {
cb.appendText(node.getX() + " " + node.getY());
printTree(node.getChild());
printTree(node.getBrother());
}
}
public void mousePressed(MouseEvent e) {
int a = e.getX();
int b = e.getY();
for (int i = 0; i < data.COL; i++) {
for (int j = 0; j < data.ROW; j++) {
if (a < (35 + i * data.SIZE) && a > (5 + i * data.SIZE)
&& b > (5 + j * data.SIZE) && b < (35 + j * data.SIZE)) {
if (data.ARRAY[i][j] == 0) {
if (mode == 1) {
data.ARRAY[i][j] = (getchessNO() % 2 == 1) ? 2 : 1;
panduan.judge1();
cb.repaint();
tree.addtoTree(i, j);
cb.appendText("tempNode所在位置为\n"
+ tree.getTempNode().getX() + " "
+ tree.getTempNode().getY() + " "
+ tree.getTempNode().getWhich());
}
if (mode == 2) {
data.ARRAY[i][j] = (getchessNO() % 2 == 1) ? 2 : 1;
panduan.judge1();
//第一次下棋判断无关项
if(getchessNO()==2&&((i<=4||i>=10)||(j<=4||j>=10)))
{
Node node = tree.getTempNode();
node = node.getChild();
// 假设棋谱一定有黑胜利的情况
node = node.getChild();
tree.setTempNode(node);
i = node.getX();
j = node.getY();
data.ARRAY[i][j] = (getchessNO() % 2 == 1) ? 2 : 1;
panduan.judge1();
cb.repaint();
cb.appendText("tempNode所在位置为\n" + tree.getTempNode().getX() + " "
+ tree.getTempNode().getY() + " "
+ tree.getTempNode().getWhich());
}
else{
if (flag) {
putdown(i, j);
} else {
fun.putdown();
}}
}
}
}
}
}
}
public void putdown(int i, int j) {
Node node = tree.getTempNode();
node = node.getChild();
if (node == null) {
flag = false;
fun.putdown();
return;
}
while (node.getX() != i || node.getY() != j) {
if (node.getBrother() == null) {
flag = false;
fun.putdown();
return;
}
node = node.getBrother();
}
// 假设棋谱一定有黑胜利的情况
node = node.getChild();
tree.setTempNode(node);
i = node.getX();
j = node.getY();
if (data.ARRAY[i][j]!=0) {
flag = false;
fun.putdown();
return;
}
data.ARRAY[i][j] = (getchessNO() % 2 == 1) ? 2 : 1;
panduan.judge1();
cb.repaint();
cb.appendText("tempNode所在位置为\n" + tree.getTempNode().getX() + " "
+ tree.getTempNode().getY() + " "
+ tree.getTempNode().getWhich());
}
// 获得棋盘上的步数的个数，返回值为棋盘上棋子子的个数
public int getchessNO() {
int step = 0;
for (int i = 0; i < 15; i++)
for (int j = 0; j < 15; j++) {
if (data.ARRAY[i][j] != 0) {
step = step + 1;
}
}
return step;
}
public void clearBoard() {
for (int i = 0; i < data.COL; i++) {
for (int j = 0; j < data.ROW; j++) {
data.ARRAY[i][j] = 0;
}
}
}
}
相关推荐
内容概要：本文详细介绍了基于MATLAB GUI界面和卷积神经网络(CNN)的模糊车牌识别系统。该系统旨在解决现实中车牌因模糊不清导致识别困难的问题。文中阐述了整个流程的关键步骤，包括图像的模糊还原、灰度化、阈值化、边缘检测、孔洞填充、形态学操作、滤波操作、车牌定位、字符分割以及最终的字符识别。通过使用维纳滤波或最小二乘法约束滤波进行模糊还原，再利用CNN的强大特征提取能力完成字符分类。此外，还特别强调了MATLAB GUI界面的设计，使得用户能直观便捷地操作整个系统。 适合人群：对图像处理和深度学习感兴趣的科研人员、高校学生及从事相关领域的工程师。 使用场景及目标：适用于交通管理、智能停车场等领域，用于提升车牌识别的准确性和效率，特别是在面对模糊车牌时的表现。 其他说明：文中提供了部分关键代码片段作为参考，并对实验结果进行了详细的分析，展示了系统在不同环境下的表现情况及其潜在的应用前景。
嵌入式八股文面试题库资料知识宝典-计算机专业试题.zip
嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_3.zip
内容概要：本文深入探讨了一款额定功率为4kW的开关磁阻电机，详细介绍了其性能参数如额定功率、转速、效率、输出转矩和脉动率等。同时，文章还展示了利用RMxprt、Maxwell 2D和3D模型对该电机进行仿真的方法和技术，通过外电路分析进一步研究其电气性能和动态响应特性。最后，文章提供了基于RMxprt模型的MATLAB仿真代码示例，帮助读者理解电机的工作原理及其性能特点。 适合人群：从事电机设计、工业自动化领域的工程师和技术人员，尤其是对开关磁阻电机感兴趣的科研工作者。 使用场景及目标：适用于希望深入了解开关磁阻电机特性和建模技术的研究人员，在新产品开发或现有产品改进时作为参考资料。 其他说明：文中提供的代码示例仅用于演示目的，实际操作时需根据所用软件的具体情况进行适当修改。
少儿编程scratch项目源代码文件案例素材-剑客冲刺.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 转瞬即逝.zip
内容概要：本文详细介绍了基于PID控制器的四象限直流电机速度驱动控制系统仿真模型及其永磁直流电机（PMDC）转速控制模型。首先阐述了PID控制器的工作原理，即通过对系统误差的比例、积分和微分运算来调整电机的驱动信号，从而实现转速的精确控制。接着讨论了如何利用PID控制器使有刷PMDC电机在四个象限中精确跟踪参考速度，并展示了仿真模型在应对快速负载扰动时的有效性和稳定性。最后，提供了Simulink仿真模型和详细的Word模型说明文档，帮助读者理解和调整PID控制器参数，以达到最佳控制效果。 适合人群：从事电力电子与电机控制领域的研究人员和技术人员，尤其是对四象限直流电机速度驱动控制系统感兴趣的读者。 使用场景及目标：适用于需要深入了解和掌握四象限直流电机速度驱动控制系统设计与实现的研究人员和技术人员。目标是在实际项目中能够运用PID控制器实现电机转速的精确控制，并提高系统的稳定性和抗干扰能力。 其他说明：文中引用了多篇相关领域的权威文献，确保了理论依据的可靠性和实用性。此外，提供的Simulink模型和Word文档有助于读者更好地理解和实践所介绍的内容。
嵌入式八股文面试题库资料知识宝典-2013年海康威视校园招聘嵌入式开发笔试题.zip
少儿编程scratch项目源代码文件案例素材-驾驶通关.zip
小区开放对周边道路通行能力影响的研究.pdf
内容概要：本文探讨了冷链物流车辆路径优化问题，特别是如何通过NSGA-2遗传算法和软硬时间窗策略来实现高效、环保和高客户满意度的路径规划。文中介绍了冷链物流的特点及其重要性，提出了软时间窗概念，允许一定的配送时间弹性，同时考虑碳排放成本，以达到绿色物流的目的。此外，还讨论了如何将客户满意度作为路径优化的重要评价标准之一。最后，通过一段简化的Python代码展示了遗传算法的应用。 适合人群：从事物流管理、冷链物流运营的专业人士，以及对遗传算法和路径优化感兴趣的科研人员和技术开发者。 使用场景及目标：适用于冷链物流企业，旨在优化配送路线，降低运营成本，减少碳排放，提升客户满意度。目标是帮助企业实现绿色、高效的物流配送系统。 其他说明：文中提供的代码仅为示意，实际应用需根据具体情况调整参数设置和模型构建。
少儿编程scratch项目源代码文件案例素材-恐怖矿井.zip
内容概要：本文详细介绍了基于STM32F030的无刷电机控制方案，重点在于高压FOC（磁场定向控制）技术和滑膜无感FOC的应用。该方案实现了过载、过欠压、堵转等多种保护机制，并提供了完整的源码、原理图和PCB设计。文中展示了关键代码片段，如滑膜观测器和电流环处理，以及保护机制的具体实现方法。此外，还提到了方案的移植要点和实际测试效果，确保系统的稳定性和高效性。 适合人群：嵌入式系统开发者、电机控制系统工程师、硬件工程师。 使用场景及目标：适用于需要高性能无刷电机控制的应用场景，如工业自动化设备、无人机、电动工具等。目标是提供一种成熟的、经过验证的无刷电机控制方案，帮助开发者快速实现并优化电机控制性能。 其他说明：提供的资料包括详细的原理图、PCB设计文件、源码及测试视频，方便开发者进行学习和应用。
基于有限体积法Godunov格式的管道泄漏检测模型研究.pdf
嵌入式八股文面试题库资料知识宝典-CC++笔试题-深圳有为（2019.2.28）1.zip
少儿编程scratch项目源代码文件案例素材-几何冲刺 V1.5.zip
Android系统开发_Linux内核配置_USB-HID设备模拟_通过root权限将Android设备转换为全功能USB键盘的项目实现_该项目需要内核支持configFS文件系统
C# WPF - LiveCharts Project
少儿编程scratch项目源代码文件案例素材-恐怖叉子 动画.zip
嵌入式八股文面试题库资料知识宝典-嵌⼊式⼯程师⾯试⾼频问题.zip