曙光v1 |
您所在的位置：网站首页 › 五子棋为啥执黑必胜呢 › 曙光v1 |
曙光v1
|
五子棋终结者，这个电脑执黑必胜的程序，为了完成打败熊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=10)||(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; } } } }
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |