Question

五子棋高级算法

1.求一个高级的五子棋算法，必须要能预测未来几步（递归或者回溯都行）。不一定要有具体代码，算法思想或者伪代码都可以。
2.先给100分，如果如果答案令我满意，再给100-500分。
3.听说国外有一种叫 黑石 的五子棋软件，据说用的是回溯算法，能达到专业三段的水平，有具体的算法步骤也可以。
4.附件的截图是我自己写的一个算法(没有用到递归和回溯)，如果朋友提供的算法能PK赢我这个，奖励500分。
5.刚有朋友给我传了五子棋终结者的软件，不知道其他朋友有源代码吗？能提供源代码的，给500分。
6.有知道的朋友，如果懒得写代码，画一个流程图也可以啊。。。。
7.谢谢5楼的朋友 cpych 。我现在才知道JDK自带了这个例子。不过我看完了源代码，这是个井字游戏，跟五子棋的算法相去还是很远，而且我想问的是，如何使程序具有预测功能，不能只看眼前利益。无论如何,thank you all the same.
9.谢谢热心朋友simon5678，但是你发给我的例子没有源代码，更重要的是，你这个例子的算法不怎么样，连活三和死三都分不清。不过还是谢谢你了。
8.欢迎发EMALI:linguiben@21cn.com

Answer 1

我也想看，呵呵，wawacry@qq.com
这个对五子棋比较精通才能写好吧

我觉的可以将走步看成是对一个多叉树的遍历，在树的层次上应该是黑白棋交替，即若第一层是白子，那么第二层则是黑子，这棵树每次生成一层节点，也就是白子或者黑子走一次，一层中包含子的数量就是可能的走步，判断生成每个节点时白棋或者黑棋是否连成线（5个），若连成线，则退出。

回溯可能是这样的，若想白棋赢，这个算法若找到了白棋赢的树路径，则退出算法，若找到了黑棋赢，那么这条路径是不可行的，要回溯到上层节点继续遍历。

这个算法若用穷举法，你的棋盘有15*15=225个位置，那么可能要比较的次数会是225*224*223*......，估计这个算法是不可能实现的吧，要简化就要根据经验，对树做剪枝，减少比较次数。

这些经验像下面这样：
若甲方已经有三个子连成线，那么乙方在没有三个子连成线的情况下只能有
两种走法，也就是堵三，
若乙方有三个子连成线，那么会多出可选位置，也就是冲四的位置。

若甲方有四子连线，当然一头是堵住的，那么乙方只能有一个位置可以选择。

可以看一些五子棋高手的经验，将这些经验写到程序中去。

以上是突然想出来的，呵呵，希望大家共同讨论

Answer 2

基本算法：
采用博弈比较常用的策略。
计算机下子前，分别对玩家和电脑棋型进行评估，然后根据棋型对每一位置打分（玩家和电脑在同一点的分数不同），比如活三100分，冲四1000分等，然后根据每个落子点分数进行选择。采用极大极小值策略，进行多步计算。
-_-.........代码在文件夹chess里啊..........

一些可能有用的链接
http://topic.csdn.net/t/20001021/09/35626.html
http://zhidao.baidu.com/question/46388110.html?si=6

Answer 3

建议你看看这个

Java\jdk1.6.0_02\demo\applets\TicTacToe

JDK中的 demo 这个是三子的示例

Answer 4

最近我也在弄这个，有源码的能给我发个好吗？
398418056@qq.com
谢谢了哈。

Answer 5

我有兴趣写AI...告诉我接口。。能给我交互界面么。