首页 > 博弈 > 井字过三关·变种游戏

井字过三关·变种游戏

2014年3月11日 发表评论 阅读评论

最近我好像对这个游戏的执念很深啊。。

这篇博文的起因是这个样子的,上次我在到处跟别人“调研”井字过三关(如若不清楚这个游戏,请查看上一篇博文)名字问题的时候,有个朋友提到了一种井字过三关的变种玩法,觉得很有趣,最近出差回来有点闲情,就做来玩了一下。。

传统的井字过三关(是不是叫井字游戏更加大众化。。)作为一个游戏本身,有一个致命的缺陷,单局游戏时长太短,走完不到9格就结束了,完成一局几乎花不了10秒,而且,对于稍有常识的玩家来说,平局率太高,95%都有了吧。。再其次,局面变化太少,就算不玩,你枚举也可以枚举完所有的可能的局面;

规则

鉴于此,出现了本文中的这个游戏,最基本的规则和传统的一样,A,B两人轮流在3×3的棋局上打圈圈(○)和叉叉(×),先让自己的符号连成一条线的玩家胜利,包括纵,横,斜对角都可以。

下面是变种游戏的附加规则:场面上最多只能容纳6个棋子,也就是说下了第七个棋子的时候,第一个棋子会消失;下第八个的时候第二个会消失,如此类推

另外还需补充说明的一点是:判断胜负要在下子后,处理完棋子的消失问题后才可以进行。

考虑到游戏的趣味性,下面游戏对于先后手分别设立的不同的AI等级,让电脑先手的话,还是比较难获胜的。。。大概。。。吧。。友情提示一下,如让电脑先手,一开始那一步会有点卡。。你懂的。。。

左下角的红色数字是消失时间倒计时。

游戏本体:


先点击“开始游戏”

据我测试经验,一开始你总会对于规则还没彻底了解,或者“眼睛一花”,就输给了AI了,随着玩多几盘,你会开始慢慢上手。。如果你玩多几盘电脑先手,你大概就会发现。。。其实这个游戏里面所谓的平局,就是在某四步里面不断打转,被迫不断重复,谁走错了谁就输的那种;再然后,你可能会突然走了某一步。。就把电脑给干掉了。。。

另外,根据别人透露,这个游戏先手其实有必胜法,而且你肯定想不到的是,必胜法是走边的中间那个位置。。。走中央和角的话,只要对方应对正确,那么确实可以逼平【就是上面一段所提到的四步死循环】;

但是我的AI的思考迭代深度没有设计得太深,我尝试了一下,如果加大迭代搜索深度,那么电脑第一步走的确实是边的中央(现在你所玩到的电脑先手第一步是走角),不过好像后面复杂过头了,我弄了半天也没弄清楚为什么走边的中间可以必胜。。而且为了娱乐性质,加之电脑思考导致的停顿不要太长时间(影响体验),所以才变成了上面你们所看到的那个样子。。。也就是说,原理上讲。。你们是可以打败它的!

代码

下面是AI的核心代码:

function AIMove() {
 	var MaxScore = -999999;
 	var bestmove = {
 		x: -1,
 		y: -1
 	};
 	for (var i = 0; i < 3; i++) {
 		for (var j = 0; j < 3; j++) {
 			if (boardState[i][j] != EMPTY)
 				continue;
 			var boardState_t = Array2DClone(boardState);
 			var TimeLeft_t = Array2DClone(TimeLeft);

 			var result = SetGame(i, j, boardState_t, 
                               TimeLeft_t, AIColor);
 			if (result == AIColor) {
 				MaxScore = 999999;
 				bestmove = {
 					x: i,
 					y: j
 				};
 			} else {
 				var score = MinMax(boardState_t, TimeLeft_t, 0,
                                IsPlayerFirst() ? 3 : 10);
 				if (score >= MaxScore) {
 					bestmove = {
 						x: i,
 						y: j
 					};
 					MaxScore = score;
 				};
 			}
 		}
 	}
 	DrawGame();
 	ClickLock = 0;
 }

 function MinMax(mboardState, mTimeLeft, AITurn, Depth) {
 	var curscore = 99999 * (AITurn == 1 ? -1 : 1);
 	Depth--;
 	if (!Depth) return 0;
 	for (var i = 0; i < 3; i++) {
 		for (var j = 0; j < 3; j++) {
 			if (mboardState[i][j] != EMPTY)
 				continue;
 			var boardState_t = Array2DClone(mboardState);
 			var TimeLeft_t = Array2DClone(mTimeLeft);

 			var judge = SetGame(i, j, boardState_t, 
                                 TimeLeft_t, 
                                 AITurn ? AIColor : PlayerColor);
 			if (judge == AIColor) return 1;
 			if (judge == PlayerColor) return -1;

 			var temp_score = MinMax(boardState_t,
                                   TimeLeft_t, 
                                   AITurn ? 0 : 1, Depth);
 			if (AITurn && temp_score > curscore) {
 				curscore = temp_score;
 			} else if (!AITurn && temp_score < curscore) {
 				curscore = temp_score;
 			}
 			if(AITurn && curscore == 1)	return 1;
 			else if(!AITurn && curscore == -1) return -1;
 		}
 	}
 	return curscore;
 }

看到第二个函数名,估计有人应该知道这个AI用的是什么算法了。。。但是需要说明一下的是,为了简单起见,一个局面的评价函数我只设置了三个值,1为必胜,0为未知胜负,-1为必败,所以顺手在上面代码最后的第64,65行做了一个简单的剪枝;

其实我想吐槽的是,写个JS的AI让我深刻的体会到什么叫做“数据结构越复杂,算法越简单”了。。妈蛋以前用C++写的几乎一遍就通了,用个JS写个同样的算法却花了不知道多少时间来调试。。【口胡!明明就是自己JS太垃圾,还找C++来当借口。。

难得糊涂

在写这个简单的游戏的AI的时候,发现了一个很好玩的“现象”;

一开始呢,我定义的游戏规则是,下子后判断玩胜负再处理消失的棋子的问题,AI的迭代搜索深度是10步,然后就发生了一个非常好玩的现象,电脑先手,棋风汹涌无比;让他后手的话,就弱得一把渣;已经弱到了你随便找一排下三个子它都完全不防守的地步了;

这显然不科学!!所以我就调试啊,调了半天,真的是“半天”,一步一步的看AI的变量的变化,最后才明白过来了,这个规则下先手有10步以内就可以找到的必胜策略,所以呢,AI先手玩家根本赢不了,而对于AI后手,它的思考就是:“啊,原来我不管怎么走,10步以内输定了啊。。。不管下那一步,评价函数都是-1。。。”没错!!!它居然。。。自!暴!自!弃!!!这尼玛的。。。

再之后我只好把规则改成当前玩的这个后,不过问题还是存在,只要AI发现自己必败,妈蛋它又开始乱来了。。。最后无奈之下,只好改成。。。让他“目光短浅”一点。。也就是上面代码23-24行迭代函数MinMax的最后一个参数,根据先后手设定不同的思考深度;

这就感觉,如果人类对未来知晓得太多,或者过度聪明以至于对未来可以完全掌握,那么他可能会觉得人生的意义并不是那么的丰富。。。当然这只是我在口胡。。。

不过技术上讲,这个问题也可以算法层面上解决的;也就是设定初始深度10,如果AI发现不管走么走都输,那么这个时候再让他弱一点,改成9让AI去摸索,如果还是,那么继续降它的智商,直到1为止,如果还是。。。节哀。。不过算了,懒得改了。。

PS.如发现bug,还望指出。

PS.PS.告诉你个好事吧,如果你玩不赢AI,请用Console。。。。233333333。。。当然,这也是有前提的,是吧。。

3月
12

AI已修改,上面分析全是屁话。。

3月
17

对AI的犯傻感到彻底绝望,于是深度根治。。。所以思考可能会进一步变慢。。但愿不要再犯傻。。

Github:githubfavicon


【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

分类: 博弈 标签: , ,
  • 你又出技术了,求个评论回复邮件代码呗?用SMTP邮件服务器的代码也行啊

    • 你又开始折腾这个了么。。。这个的话你去google搜一下“wordpress 代码实现 邮件回复”,就有了。

  • 再来瞧瞧博主

  • 艹,老是输掉_______________

    • 游戏越简单,人类战胜电脑的可能性越小。。

      • 嗯蒽唔,不过策略越容易指定,只是我感觉我越来越笨了 _______________________

        • replace('指定', '制定')___________________

          • 好吧。。。我写完评论才看到你这条。。

        • 不要妄自菲薄。。【我怎么感觉你这句话上下句衔接不上。。23333

          • 玩久了就不想钻算法,看到别人的算法代码就石化;一钻算法又拔不出来,解决了算法问题之后又开始满足感不停泛滥________________________

            • 一遇算法终身误么。。哈哈。。

  • 好恶心,不玩了- -

  • 好高级/w

    • 显然不高级。。垃圾游戏。。

      • 嘛。 还行吧。

        • 规则简单,界面粗糙,AI粗暴。。最重要,毫无娱乐性。。

  • OX

    我都把文章看完了,你竟然来句「AI已修改,上面分析全是屁话。。」带不带这么坑的..?!

    • 其实没改多少,就是两种模式下电脑思考深度都变成10,然后不会再犯傻【大概。。】这两点而已。。

  • 话说我从右边的中间开始,一直没赢过……

    • 边的中间先手必胜我是听别人说的,自己没严格验证过。。。可能是不对的。。也可能是规则没对上。。。

    • 妈蛋。。刚刚自己又玩了一下,发现了个bug。。。下(1,2)(2,2)(3,1)(1,3)电脑又犯傻了。。。

      • 改进后的算法真凶残 QAQ 用之前的侧中间开局完败……你接触过游戏公司么?是算法比较重要还是界面架构比较重要?

        • 嗯,我相信这个版本的AI应该比较完善了。。。没接触过,从来游戏都是自己写着自娱自乐的。。以前只在腾讯实习搞过后台。。。这个不清楚诶(游戏的idea比较重要?),应该是看情况吧,写一个游戏(要稍微像样一点的)或多或少都会涉及到状态空间搜索啊,人机博弈啊之类的,就算没有这些,编程中用的数据结构的算法也基本必不可少的。不过也有一些游戏不涉及这些,像三消游戏,或者最近很火的那个2048的游戏,只要实现游戏规则的逻辑就可以的那种,自然应该把精力放在交互上。【我瞎说的。。

  • Yu

    话说井字游戏本来就是这样的规则么,难道你玩过的是某一方可以超过三个?以前玩的最大障碍就是下第四个的时候要回忆下下下去后哪个要被消除另外,你的服务器貌似被部分墙?我在家用联通网没问题,学校用教育网就会挂。。。好奇怪

    • 传统的不是就是不消失的么?不做标记哪个会消失这么难?被墙,倒应该不会,90%是因为这个主机的机房又TM出问题了。。。然后出问题的时候你碰巧在学校?

      • Yu

        小时候在电子词典上玩的就是会消失的那种,常常玩着玩着就变成两边都在某个loop中出不去了。至于记忆哪个会消失困难--或许我记忆太残了吧我检测了下,是DNS的问题,我ping你的domain无法得到ip,但如果把ip加入hosts就可以访问。我用的就是8.8.8.8完全没问题啊好奇怪

        • 孤陋寡闻了,我是最近第一次听说这个游戏的。。不标记的话这个游戏也太难了吧。。刚刚试了一下,简直被完虐。。【开了标记可以撑多一下下再被完虐。。唉,以前访问没问题的话,就是这个破主机的问题了。。

        • 听说昨天8.8.8.8被劫持了一段时间。。

          • Yu

            前几天就有同样的问题了,当时还以为你的机器down掉了,等了几天发现在家居然好了,才突发其想翻墙看看你的网站

            • 我怎么有一种莫名其妙被扔到墙外的感觉。。

              • Yu

                ping ip一直应该是完全没问题的,只是ping domain在某些位置得不到ip而已也许我在的地方比较崎岖而已,仅仅是

              • Yu

                另外,中国的话,用DNSPod还是挺靠谱的,虽然很不喜欢腾讯22.cn之类域名提供商的DNS感觉不是怎么很靠谱的样子 -- 还有,我还以为大家都是godaddy上去买域名的

                • 几个月前刚开始搞,所以不是很懂,域名买的地方和主机都很垃圾。。一直是准备有空去把域名过户出去。。现在的确实很恼火。。

      • 我就是用代理访问的……

  • 三石

    楼主啊楼主~哦呵呵呵呵,我最近也tm想着做一个五子棋AI啊(闲得蛋疼),傻逼AI自暴自弃的状况我也遇到过,最后修改了一下评价函数(评分×深度),这样AI必胜的时候会找最短路径,必输的时候会尽可能多走几步。。。太机智。。。

    • 哈哈哈,自暴自弃这种事也只有真正动手写代码的人才会发现。。。以前写的一个五子棋AI没有用博弈树的方法所以没发现。写的黑白棋AI用的αβ决策,因为太强了【或者我太弱了】所以发现不了。。

  • 路人甲

    好難過,泰半一直輸,贏都搞不清楚怎贏的,請問井字變種的AI設定..原裡是什麼?

    • 参考;https://zh.wikipedia.org/zh-cn/%E6%9E%81%E5%B0%8F%E5%8C%96%E6%9E%81%E5%A4%A7%E7%AE%97%E6%B3%95