我正在写一个游戏,它是Gomoku的变种.基本上是一个巨大的板上的tic tac脚趾.
想知道是否有人知道一个好的人工智能策略.我目前的实现是非常愚蠢的,需要很长时间(O(n ^ 3),大约1-2秒才能移动):
-(void) moveAI {
//check if the enemy is trying to make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkEnemies];
//check if we can make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkIfWeCanMakeALine];
//otherwise just put the piece randomly
[self put randomly];
}
编辑:谢谢大家的反馈!我会尝试你的答案,让你们知道我是否可以做出任何改进.
对于gomoku,已经找到了获胜策略.见本文:L.Victor Allis,HJ van den Herik,MPH Huntjens.Go-Moku和威胁空间搜索.当我写自己的程序时,它对我帮助很大.通过这种方式,你将能够编写出能够很好地攻击对手并找到胜利组合的程序.
为这类游戏编写AI的传统且相当有效的策略是典型的树搜索策略.也就是说,每个板状态在图形中形成节点,并且在每个节点和可以由单个移动产生的状态之间放置有向边缘.以这种方式构建树,其中根板是空节点.然后,以一种巧妙的方式遍历树,找到看起来像"好"的状态."良好"状态通常通过使用一些聪明的启发式的评估函数来度量.显然你不想访问树中的所有节点 - 这将是很多工作!你只想要一些聪明的东西.
您可以添加预先计算的早期游戏和结束游戏以加速这些场景,然后依靠针对游戏中期的优化的树遍历启发式算法.
这种树遍历算法的实际名称是"Minimax"算法.在维基百科上寻找它,你会看到很多相当不错的材料.有一些方法可以提高算法的效率,其中最引人注目的是alpha-beta修剪,所以一定要看一下.您可能需要查看connect-four启发式方法,并决定如何将它们应用到游戏中.例如,用于评估电路板状态的可能良好的启发式方法是计算可连续的2次运行,3次运行和4次运行的数量,并将它们加权到分数中.(例如,每次2次运行值1点,每次3次运行值10点,每次4次运行值1000点)
另一种优化策略是开发一种启发式算法,优先考虑minimax算法应该搜索的位置 - 通常通过估计板评估函数的某种确定性.
有了这个策略,你应该能够在相同的时间内获得不那么愚蠢的AI.然而,真的,非常好的AI需要花费很多精力来构建,即使在这些"简单"的游戏中,它仍然可能需要超过10秒或更长时间才能让聪明的动作不受影响.另一方面,有一些聪明的编程技巧,例如在人类对手忙于思考时通过树预先计算遍历.嘿,人类可以在计算机的同时思考.公平是公平的!
希望我能得到一些帮助.祝好运!这是一个有趣的项目.
我一直试图为同一个程序创建一个算法.
你当然应该做的第一件事就是检查是否有办法形成5并取胜.如果没有,那么下一个应该是检查你的对手是否可以做到这一点,如果是,那么防守.
你有多少玩过自己的gomoku？你对基础知识的掌握程度如何？
好的,下一步是思考:我们如何才能获得能够获胜的位置？显然,要赢,我们必须连续四次.但它我们只是连续形成四个这样的:
__________ ____XOOOO_ __________
然后对手可以关闭它.
但如果我们形成"开放四",就像这样:
__________ ____OOOO__ __________
然后对手不能关闭双方,你可以赢.因此,形成一个开放的四是获胜的一种方式.现在问题是:我们怎样才能形成一个开放的四个？当然,如果我们形成"开放三",就像这样:
__________ ____OOO___ __________
然后对手可以阻止我们:
___________ ____XOOO___ ___________
我们回到了开始.
为了获胜,我们可以同时组成两个空位三分球:
____________ ____OOO_____ _____O______ ____O_______
现在,如果对手阻挡其中一个,我们可以使用另一个来形成一个开放的四个:
____________ _______O____ ___XOOO_____ _____O______ ____O_______ ____________
赢了:
________O___ _______O____ ___XOOO_____ _____O______ ____O_______ ___X________
在gomoku术语中,如果您同时进行两次打开三分球,则称为3x3.
请注意,两个三分必须是开放的:你能理解为什么吗？
还有其他获胜方式:
4x3:你看到胜利的举动以及为什么赢了？
____________ __XOOO______ __XXXO______ ____OX______ ____________
4x4:看到获胜的举动？
____________ __XOOO______ __XXXO______ __OXOX______ ___O________ __X_________
这些只是游戏的基础.了解这些策略有助于您思考如何构建AI,因此您可以对原则进行硬编码.
当然,这只是一个开始.如果你能尝试实现这一点然后给我反馈,我将不胜感激.
我一直在尝试用Java编写程序.你想看看我做过的代码吗？你可以玩游戏吗？它还不是很好,但你可以从中获得新的想法.虽然注释和变量名称是用爱沙尼亚语编写的,但可能很难理解.:(
我创造了一个gomoku播放器一次,它使用alpha-beta修剪非常成功,并给每个位置一个分数取决于每个玩家有多少半打开和完全打开的2s,3s和4s.
计算这不是n ^ 3.您只需检查最新的移动是否会关闭任何对手线,如果它延伸了一些线,则相应地修改得分.
如果你需要它玩得更好,我会研究一些国际象棋电脑的技术.例如,尝试"杀手移动"(记住哪些移动得分高或在其他位置直接获胜)首先搜索时会显着提高树搜索的效率.重要的是在alpha-beta修剪中首先尝试假定的最佳动作.
当你拥有你的玩家时,你应该尝试通过互相玩不同的版本来找出不同元素(2s,3s,4s,开放和半开放等)的得分最好.
五子棋可以解决，但在空缺位置和有限的资源下玩不能解决。
我是Hewer gomoku程序和Gomocup组织者的作者，我可以告诉你，编写好的Gomoku AI需要花费很长时间。人居要复杂得多。您可以使用Gomocup界面简化工作，并编写“仅” AI。
京公网安备 11010802040832号 | 京ICP备19059560号-6 