- 浏览: 801486 次
- 性别:
- 来自: 广州
最新评论
-
mixture:
语句int num1, num2;的频度为1;语句i=0;的频 ...
算法时间复杂度的计算 [整理] -
zxjlwt:
学习了。http://surenpi.com
[问题解决]Error: ShouldNotReachHere() [整理] -
Animal:
谢谢 楼主 好东西
算法时间复杂度的计算 [整理] -
univasity:
gaidandan 写道缓存失败,,模拟器上可以缓存,同样代码 ...
[开发总结]WebView使用中遇到的一些问题&解决 -
blucelee2:
那么麻烦干吗,而且这种方法会导致,当拉太小的时候样式会丢掉,整 ...
[SWT]SashForm中固定单侧大小(&实现面板隐藏)
极小极大的定义
Minimax算法
又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大得益)。通常以递归形式来实现。
Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,另一方则选择令对手
优势最小化的一个,其输赢的总和为0(有点像能量守恒,就像本身两个玩家都有1点,最后输家要将他的1点给赢家,但整体上还是总共有2点)。很多棋类游戏
可以采取此算法,例如tic-tac-toe。
关于极小极大,更多的信息可参考以下文章:
以TIC-TAC-TOE为例
tic-tac-toe就是我们小时候玩的井字棋(我这边习惯叫“井字过三关”),不熟悉的可以参考wiki
。
一般X的玩家先下。设定X玩家的最大利益为正无穷(+∞),O玩家的最大利益为负无穷(-∞),这样我们称X玩家为MAX(因为他总是追求更大的值),成O玩家为MIN(她总是追求更小的值),各自都为争取自己的最大获益而努力。
现在,让我们站在MAX的立场来分析局势(这是必须的,应为你总不能两边倒吧,你喜欢的话也可以选择MIN)。由于MAX是先下的(习惯上X的玩家先下),于是构建出来的博弈树如下(前面两层):
MAX总是会选择MIN最大获利中的最小值(对MAX最有利),同样MIN也会一样,选择对自己最有利的(即MAX有可能获得的最大值)。有点难理解,其实就是自己得不到也不给你得到这样的意思啦,抢先把对对手有利的位置抢占了。你会看出,这是不断往下深钻的,直到最底层(即叶节点)你才能网上回溯,确定那个是对你最有利的。
具体过程会像是这么一个样子的:
具体过程会像是这么一个样子的:
但实际情况下,完全遍历一颗博弈树是不现实的,因为层级的节点数是指数级递增的:
层数 节点数
0 1
1 9
2 72
3 504
4 3024
5 15120
6 60480
7 181440
8 362880
完全遍历会很耗时...一般情况下需要限制深钻的层数,在达到限定的层数时就返回一个估算值(通过一个启发式的函数对当前博弈位置进行估值),这样获得的值就不是精确的了(遍历的层数越深越精确,当然和估算函数也有一定关系),但该值依然是足够帮助我们做出决策的。于是,对耗时和精确度需要做一个权衡。一般我们限定其遍历的深度为6(目前多数的象棋游戏也是这么设定的)。
于是,我们站在MAX的角度,评估函数会是这样子的:
static final int INFINITY = 100 ; // 表示无穷的值 static final int WIN = +INFINITY ; // MAX的最大利益为正无穷 static final int LOSE = -INFINITY ; // MAX的最小得益(即MIN的最大得益)为负无穷 static final int DOUBLE_LINK = INFINITY / 2 ; // 如果同一行、列或对角上连续有两个,赛点 static final int INPROGRESS = 1 ; // 仍可继续下(没有胜出或和局) static final int DRAW = 0 ; // 和局 static final int [][] WIN_STATUS = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } }; /** * 估值函数,提供一个启发式的值,决定了游戏AI的高低 */ public int gameState( char [] board ) { int result = INPROGRESS; boolean isFull = true ; // is game over? for ( int pos = 0; pos < 9; pos++) { char chess = board[pos]; if ( empty == chess) { isFull = false ; break ; } } // is Max win/lose? for ( int [] status : WIN_STATUS) { char chess = board[status[0]]; if (chess == empty ) { break ; } int i = 1; for (; i < status.length; i++) { if (board[status[i]] != chess) { break ; } } if (i == status.length) { result = chess == x ? WIN : LOSE; break ; } } if (result != WIN & result != LOSE) { if (isFull) { // is draw result = DRAW; } else { // check double link // finds[0]->'x', finds[1]->'o' int [] finds = new int [2]; for ( int [] status : WIN_STATUS) { char chess = empty ; boolean hasEmpty = false ; int count = 0; for ( int i = 0; i < status.length; i++) { if (board[status[i]] == empty ) { hasEmpty = true ; } else { if (chess == empty ) { chess = board[status[i]]; } if (board[status[i]] == chess) { count++; } } } if (hasEmpty && count > 1) { if (chess == x ) { finds[0]++; } else { finds[1]++; } } } // check if two in one line if (finds[1] > 0) { result = -DOUBLE_LINK; } else if (finds[0] > 0) { result = DOUBLE_LINK; } } } return result; }
基于这些,一个限定层数的实现是这样的:
/** * 以'x'的角度来考虑的极小极大算法 */ public int minimax( char [] board, int depth){ int [] bestMoves = new int [9]; int index = 0; int bestValue = - INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ board[pos] = x ; int value = min(board, depth); if (value>bestValue){ bestValue = value; index = 0; bestMoves[index] = pos; } else if (value==bestValue){ index++; bestMoves[index] = pos; } board[pos] = empty ; } } if (index>1){ index = ( new Random (System. currentTimeMillis ()).nextInt()>>>1)%index; } return bestMoves[index]; } /** * 对于'x',估值越大对其越有利 */ public int max( char [] board, int depth){ int evalValue = gameState (board); boolean isGameOver = (evalValue== WIN || evalValue== LOSE || evalValue== DRAW ); if (depth==0 || isGameOver){ return evalValue; } int bestValue = - INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ // try board[pos] = x ; // maximixing bestValue = Math. max (bestValue, min(board, depth-1)); // reset board[pos] = empty ; } } return evalValue; } /** * 对于'o',估值越小对其越有利 */ public int min( char [] board, int depth){ int evalValue = gameState (board); boolean isGameOver = (evalValue== WIN || evalValue== LOSE || evalValue== DRAW ); if (depth==0 || isGameOver){ return evalValue; } int bestValue = + INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ // try board[pos] = o ; // minimixing bestValue = Math.min(bestValue, max(board, depth-1)); // reset board[pos] = empty ; } } return evalValue; }
Alpha-beta剪枝
另外,通过结合Alpha-beta剪枝能进一步优化效率。Alpha-beta剪枝顾名思义就是裁剪掉一些不必要的分支,以减少遍历的节点数。实际上是通过传递两个参数alpha和beta到递归的极小极大函数中,alpha表示了MAX的最坏情况,beta表示了MIN的最坏情况,因此他们的初始值为负无穷和正无穷。在递归的过程中,在轮到MAX的回合,如果极小极大的值比alpha大,则更新alpha;在MIN的回合中,如果极小极大值比beta小,则更新beta。当alpha和beta相交时(即alpha>=beta),这时该节点的所有子节点对于MAX和MIN双方都不会带来好的获益,所以可以忽略掉(裁剪掉)以该节点为父节点的整棵子树。
根据这一定义,可以很轻易地在上面程序的基础上进行改进:
/** * 以'x'的角度来考虑的极小极大算法 */ public int minimax( char [] board, int depth){ int [] bestMoves = new int [9]; int index = 0; int bestValue = - INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ board[pos] = x ; int value = min(board, depth, - INFINITY , + INFINITY ); if (value>bestValue){ bestValue = value; index = 0; bestMoves[index] = pos; } else if (value==bestValue){ index++; bestMoves[index] = pos; } board[pos] = empty ; } } if (index>1){ index = ( new Random (System. currentTimeMillis ()).nextInt()>>>1)%index; } return bestMoves[index]; } /** * 对于'x',估值越大对其越有利 */ public int max( char [] board, int depth, int alpha, int beta){ int evalValue = gameState (board); boolean isGameOver = (evalValue== WIN || evalValue== LOSE || evalValue== DRAW ); if (beta<=alpha){ return evalValue; } if (depth==0 || isGameOver){ return evalValue; } int bestValue = - INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ // try board[pos] = x ; // maximixing bestValue = Math. max (bestValue, min(board, depth-1, Math. max (bestValue, alpha), beta)); // reset board[pos] = empty ; } } return evalValue; } /** * 对于'o',估值越小对其越有利 */ public int min( char [] board, int depth, int alpha, int beta){ int evalValue = gameState (board); boolean isGameOver = (evalValue== WIN || evalValue== LOSE || evalValue== DRAW ); if (alpha>=beta){ return evalValue; } // try if (depth==0 || isGameOver || alpha>=beta){ return evalValue; } int bestValue = + INFINITY ; for ( int pos=0; pos<9; pos++){ if (board[pos]== empty ){ // try board[pos] = o ; // minimixing bestValue = Math.min(bestValue, max(board, depth-1, alpha, Math.min(bestValue, beta))); // reset board[pos] = empty ; } } return evalValue; }
*这里对极小极大算法的实现只是其中一种可行性,实际上可能会看到很多种不同的实现方式,但道理是一样的。
使用开局库
同时,你会发现,这样做视乎还不够,特别在一开局。我们都知道,中心的位置是最好的,但是按照我们上面的算法,第一步确实随机的...这在深度受限制的情况下就更显得重要了。于是就引申出了开局库的概念,这是我在某个讲象棋AI的网上看到的,就是给初始的棋盘设定一些格局。
针对上面的例子,我们只要判断是否第一步棋,如果是则想办法让他选择中心的位置(4)。
在WIKI百科中找到一幅图也能作为TIC-TAC-TOE开局库的参考:
于是,估算函数会变成这样的(当然也可以在别的地方修改,只要合理):
//开局时,每个位置的估值 static final int [] INITIAL_POS_VALUE = { 3, 2, 3, 2, 4, 2, 3, 2, 3 }; /** * 估值函数,提供一个启发式的值,决定了游戏AI的高低 */ public int gameState ( char [] board ) { int result = INPROGRESS ; boolean isFull = true ; int sum = 0; int index = 0; // is game over? for ( int pos=0; pos<9; pos++){ char chess = board[pos]; if ( empty ==chess){ isFull = false ; } else { sum += chess; index = pos; } } // 如果是初始状态,则使用开局库 boolean isInitial = (sum== x ||sum== o ); if (isInitial){ return (sum== x ?1:-1)*INITIAL_POS_VALUE[index]; } // is Max win/lose? for ( int [] status : WIN_STATUS ){ char chess = board[status[0]]; if (chess== empty ){ break ; } int i = 1; for (; i<status.length; i++){ if (board[status[i]]!=chess){ break ; } } if (i==status.length){ result = chess== x ? WIN : LOSE ; break ; } } if (result!= WIN & result!= LOSE ){ if (isFull){ // is draw result = DRAW ; } else { // check double link // finds[0]->'x', finds[1]->'o' int [] finds = new int [2]; for ( int [] status : WIN_STATUS ){ char chess = empty ; boolean hasEmpty = false ; int count = 0; for ( int i=0; i<status.length; i++){ if (board[status[i]]== empty ){ hasEmpty = true ; } else { if (chess== empty ){ chess = board[status[i]]; } if (board[status[i]]==chess){ count++; } } } if (hasEmpty && count>1){ if (chess== x ){ finds[0]++; } else { finds[1]++; } } } // check if two in one line if (finds[1]>0){ result = - DOUBLE_LINK ; } else if (finds[0]>0){ result = DOUBLE_LINK ; } } } return result; }
----------------------------------------------------------------------------------------------------
参考资料
极大极小博弈树的简洁(附Tic-Tac-Toe源码)
Tic-Tac-Toe算法笔记(一):Minimax算法
- MinimaxDemos_TicTacToe-Java_.rar (4.3 KB)
- 描述: 分别是使用了深度限制和使用了Alpha-beta剪枝的例子(能直接编译运行)
- 下载次数: 97
评论
4 楼
XmKevinChen
2014-10-11
1. max跟min的函数中bestValue的计算实际都上都没有用到
2. 计算输赢的代码, 明显应该continue而不是break
for ( int [] status : WIN_STATUS ){ char chess = board[status[0]]; if (chess== empty ){ break ; }
3 楼
liufengyuan07
2012-12-05
谢谢,!~
2 楼
univasity
2012-12-03
liufengyuan07 写道
你好,我想请教一下,INFINITY = 100 这个选取的依据是什么,谢谢!~
你好,不一定要设定为100的,就是这么一个值,你设定成200,999也可以。重要的是以下值得相对关系:
int WIN = +INFINITY ; // MAX的最大利益为正无穷
int LOSE = -INFINITY ; // MAX的最小得益(即MIN的最大得益)为负无穷
int DOUBLE_LINK = INFINITY / 2 ; // 如果同一行、列或对角上连续有两个,赛点
1 楼
liufengyuan07
2012-11-27
你好,我想请教一下,INFINITY = 100 这个选取的依据是什么,谢谢!~
发表评论
-
讲解极小极大 (Minimax Explained) [译]
2011-09-11 21:00 6786原文链接:Minimax Explaine ... -
理解极小极大算法 (Understanding The Minimax Algorithm) [译]
2011-09-11 20:45 26976原文链接:Understanding Th ... -
归并排序(MergeSort)
2011-09-02 23:31 2531归并(Merge)排序法是将两个(或两个以上)有序表合并成一个 ... -
常见排序算法 [整理]
2011-09-02 23:21 2246名称 复杂度 说明 ... -
算法时间复杂度的计算 [整理]
2011-09-02 22:58 155690基本的计算步骤 时间复杂度的定义 一般情况 ... -
[概念]算法的复杂度 [整理]
2011-08-29 15:25 2034同一个问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃 ...
相关推荐
带有最小最大算法的井字游戏 来自JetBrainsAcademy的TicTacToe游戏项目,可与AI一起玩 没有菜单要播放,只需键入“开始播放器播放器”播放器=用户,简单,中,硬 坐标是从(1,1)左下角到(3,3)右上角第一列
极小井字游戏 Minimax算法实施项目。 使用纯JS构建,没有任何其他库。
井字游戏 使用Winmaxs和minimax算法开发的TicTacToe游戏
这里只给出了源代码,没有解决方案文件,大家可以自行组装。VS2022编译通过。博弈树最大搜索深度目前是4层(代码中因为序号从0开始,所以是3,其实还是4层这,已经是上限了)。
Minimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdfMinimax算法及实例分析.pdf
Javascript-MiniMax-TicTacToe TicTacToe的Javascript中的MiniMax算法。
Minimax算法和机器学习技术已经研究了数十年,以在象棋和五子棋等游戏领域中达到理想的优化。 在这些领域中,几代人试图为修剪和评估功能的有效性优化代码。 因此,存在装备精良的算法来处理游戏场合中的各种复杂...
minimax算法介绍_JavaScript_下载.zip
使用了minimax算法。 除了百度各个棋型的打分方式,所有代码皆为本人所撸。本程序结构与之前的井字棋、黑白棋一模一样。 有一点小问题,没时间弄了,就这样吧。 一、效果图 (略) 二、完整代码 from functools ...
Minimax算法的简单实现,可在井字游戏中获得最佳移动。 观看演示 描述 来自 Minimax(有时是MinMax或MM [1])是一种决策规则,用于决策理论,博弈论,统计数据和哲学,用于将最坏情况(最大损失)情况下的可能损失...
minimax_player安装要安装minimax国际象棋算法,只需运行make 如果要使用自动播放器,则有两个python依赖项。 跑: pip install undetected-chromedriver pip install chess Minimax算法运行make ,您将看到一个名为...
MiniMax_AlphaBeta:minimax算法的实现,可以选择使用alpha-beta修剪
CheckersMiniMax:有关minimax算法的更多知识
井字游戏带有Minimax算法的井字游戏
JavaMinimax 适用于井字游戏的minimax算法的Java实现
井字游戏自动化使用minimax算法实现井字游戏的自动化。
Minimax 搜索算法 实现一个跳棋游戏 游戏由专门的借口定义,非常好的教学例子,代码也很值得学习
使用Minimax算法的TicTacToe简易游戏##### *请前往尝试赢,您不应该能够赢,但是试试吧!您需要连接到互联网才能像使用Bootstrap / al CDN一样使用:)QUnit测试单元测试位于TicTacToe / tests / tests_v1.js中要运行...