univasity
- 浏览: 808807 次
- 性别:
- 来自: 广州
-
最新评论
-
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算法
- 大小: 9.3 KB
- 大小: 35.1 KB
- 大小: 671 KB
- 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 6902原文链接：Minimax Explaine ... -
理解极小极大算法 (Understanding The Minimax Algorithm) [译]
2011-09-11 20:45 27096原文链接：Understanding Th ... -
归并排序（MergeSort）
2011-09-02 23:31 2593归并（Merge）排序法是将两个（或两个以上）有序表合并成一个 ... -
常见排序算法 [整理]
2011-09-02 23:21 2291名称 复杂度 说明 ... -
算法时间复杂度的计算 [整理]
2011-09-02 22:58 155862基本的计算步骤 时间复杂度的定义 一般情况 ... -
[概念]算法的复杂度 [整理]
2011-08-29 15:25 2083同一个问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃 ...
相关推荐
综上所述，"AI-tictactoe:使用博弈论中的minimax算法创建Ai"项目涉及到多个IT领域的知识，包括游戏设计、算法实现、编程技术以及用户体验设计。通过学习和实践这个项目，开发者可以深入了解人工智能在游戏中的应用，...
本文将深入探讨如何使用SwiftUI和minimax算法来创建一个具有人工智能的Tic-Tac-Toe游戏。 首先，SwiftUI是Apple为iOS、macOS、watchOS和tvOS等平台提供的声明式用户界面框架，它允许开发者以简洁的代码构建美观的...
在这个项目中，我们可能会看到Minimax算法的运用，它通过模拟所有可能的未来走法，预测对手的最佳反应，以求找到最优解。 3. **Minimax算法** Minimax算法是一种决策制定方法，用于两方对弈游戏。它通过递归地假设...
3. **人工智能算法**：这里可能使用的是简单的最小-最大搜索法（Minimax）或者Alpha-Beta剪枝，这两种方法在有限搜索深度内寻找最优解，以模拟对手的决策。 - **最小-最大搜索**：AI会假设对手总是选择对其最不利...
《TicTacToe2D-AIOpponent：基于...通过研究这个项目，不仅可以提升JavaScript编程技能，还能深入理解Minimax算法在游戏开发中的应用。对于想要涉足游戏编程或者AI领域的开发者来说，这是一个不可多得的学习资源。
本文将详细探讨一个开源项目“TicTacToe Solver”，它是如何利用Minimax算法和启发式策略来解决这个游戏的，以及其作为计算机AI学习和教学的优秀资源。 一、Minimax算法详解 Minimax算法是AI在决策过程中广泛使用...
总之，“TicTacToe:带有友好AI的简单tictactoe游戏”不仅是一个娱乐项目，也是一个学习和研究AI策略的好例子。通过理解游戏的实现，我们可以深入了解决策树搜索、剪枝技术以及面向对象编程等编程概念。同时，它也为...
一个常见的实现方式是使用Minimax算法或Alpha-Beta剪枝，以确保电脑玩家能做出合理的选择。这些算法会模拟所有可能的走法，预测每一步的最终结果，从而选择最优策略。 学习和使用TicTacToe4fun库，不仅可以让我们更...
AI使用minimax算法选择移动。 如果您碰巧有一个朋友，您也可以在同一台PC上玩这个游戏。 要在比赛结束后重置游戏，只需单击棋盘。Javascript实践我只是在学习javascript，实际上这是我的第一个javascript项目。 ...
在提供的压缩包文件"TicTacToe-master"中，应该包含了完整的源代码和相关的文档，你可以下载后自行研究和学习。通过阅读和理解代码，你将能够更深入地了解如何在实际项目中应用Python编程技巧。
3. α-β剪枝：为了优化Minimax算法，我们引入α-β剪枝技术，提前终止那些明显不会影响最优解的分支，减少计算量。 四、实现步骤 1. 创建HTML界面和JavaScript对象。 2. 实现用户交互，处理点击事件并更新游戏...
【标题】"TicTacToe:一个自学如何玩井字游戏的 Python 程序" 涉及的知识点主要集中在编程语言 Python 和人工智能的基本概念上。在这个项目中，开发者创建了一个能自我学习并提高玩井字游戏能力的程序。下面我们将...
在实现自动化的过程中，我们可能需要编写脚本来模拟玩家的决策，这可以涉及随机数生成器或者更复杂的AI算法，如Minimax或Alpha-Beta剪枝，以创建一个能够自动玩Tictactoe的智能对手。此外，自动化还可能涉及到游戏的...
TicTacToeAI项目是一个基于C语言实现的井字游戏，它引入了人工智能的元素，通过最小最大（Minimax）算法来模拟智能对手，为玩家提供了一种既有趣又具有挑战性的游戏体验。 首先，我们来了解一下井字游戏（Tic Tac ...
1. 最大最小搜索（Minimax）：这是一种常见的游戏树搜索算法，通过模拟所有可能的走法，预测对手的最佳策略，从而找到己方的最佳策略。在五子棋中，可以使用深度优先搜索（DFS）配合剪枝策略来减少计算量。 2. α-...
此外，还可以通过引入人工智能，让计算机与玩家对战，利用搜索算法如Minimax或Alpha-Beta剪枝来实现AI的智能决策。 五、教育价值 Tic Tac Toe在编程教学中占有重要地位，因为它可以轻松地用各种编程语言实现，适合...
3. **Minimax算法**：实现Minimax算法的核心部分。这是一个递归函数，它会遍历所有可能的游戏分支，并返回每个分支的评分。对于Max节点（代表AI），算法会寻找最大评分；对于Min节点（代表对手），则寻找最小评分。 ...
6. `minimax.js` - 最小极大算法的实现，包括Alpha-Beta剪枝优化以减少搜索空间。 在项目中，JavaScript的事件监听器可能会监听用户的点击事件，当用户点击棋盘上的某个位置时，调用相应的函数进行标记并检查游戏...
关于AI的部分，基本的Tic Tac Toe AI通常使用的是最小-最大搜索算法（Minimax），这是一个用于决策树的递归算法。在这个游戏中，AI会预测未来的几步并尝试最大化自己的获胜机会或者最小化对手的获胜机会。由于Tic ...