- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我自己的国际象棋引擎使用 minimax 算法搜索国际象棋走法有问题我使用 5 层深度搜索并且只有 Material /奖励/移动性评估,但即使我给出它也会做出愚蠢的移动并牺牲有值(value)的棋子对他们无穷大(这肯定是一个搜索问题),我没有使用任何类型的修剪,并在几秒钟内给出了 5 深度搜索结果。
我在这个问题上被困了一个星期,我确信问题出在回溯而不是国际象棋逻辑(所以没有国际象棋背景的人都会解决这个问题:))我搜索了很多这是我的第一个问题在 Stack Overflow 中,我希望你们不会让我失望 :)
这是简单的搜索代码
int GameControl::Evaluate(ChessBoard _B)
{
int material=0,bonus=0,mobility=0;
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
{
if(_B.Board[i][j]!=EMPTY)
{
if(_B.Board[i][j]->pieceColor==WHITE){
material+=-_B.Board[i][j]->Weight;
bonus+=-_B.Board[i][j]->bonusPosition[i][j];
mobility+=-_B.Board[i][j]->getPossibleMovesList(i,j,B).size();
}
else {
material+=_B.Board[i][j]->Weight;
bonus+=_B.Board[i][j]->bonusPosition[i][j];
mobility+=_B.Board[i][j]->getPossibleMovesList(i,j,B).size();
}
}
}
return material+bonus/10+mobility/20;
}
pair<pair<int,int>,pair<int,int>> GameControl::minimax( int depth , ChessBoard _B )
{
short int i,j;
int bestValue = -INFINITY;
pair<pair<int,int>,pair<int,int>> bestMove;
vector< pair<int,int> > ::iterator it;
vector< pair<int,int> > Z;
for( i = 0; i < 8; i++ )
for( j = 0; j < 8; j++ )
{
if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==BLACK )
{
Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B);
for(it=Z.begin();it!=Z.end();it++)
{
pair<int,int> temp;
temp.first=i,temp.second=j;
ChessPieces* DestinationPiece;
DestinationPiece=_B.Board[(*it).first][(*it).second];
//Moving
_B.Board[(*it).first][(*it).second]=_B.Board[i][j];
_B.Board[i][j]=EMPTY;
//
int value = minSearch( depth-1 , _B );
if( value > bestValue )
{
bestValue = value;
bestMove.first.first = i;
bestMove.first.second = j;
bestMove.second.first = (*it).first;
bestMove.second.second = (*it).second;
}
//Undo Move
_B.Board[i][j]=_B.Board[((*it).first)][(*it).second];
_B.Board[(*it).first][(*it).second]=DestinationPiece;
}
}
}
return bestMove;
}
int GameControl::minSearch( int depth , ChessBoard _B )
{
short int i;
short int j;
if(depth==0)
return Evaluate(_B);
int bestValue = INFINITY;
for( i = 0; i < 8; i++ )
for( j = 0; j < 8; j++ )
{
vector< pair<int,int> > ::iterator it;
vector< pair<int,int> > Z;
if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==WHITE && !_B.Board[i][j]->V.empty())
{
Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B);
for(it=Z.begin();it!=Z.end();it++)
{
pair<int,int> temp;
temp.first=i;
temp.second=j;
ChessPieces* DestinationPiece;
DestinationPiece=_B.Board[(*it).first][(*it).second];
// Moving
_B.Board[(*it).first][(*it).second]=_B.Board[i][j];
_B.Board[i][j]=EMPTY;
//
int value = maxSearch( depth-1 , _B );
if( value < bestValue )
bestValue = value;
//Undo Move
_B.Board[i][j]=_B.Board[(*it).first][(*it).second];
_B.Board[(*it).first][(*it).second]=DestinationPiece;
//
}
}
}
return bestValue;
}
int GameControl::maxSearch( int depth , ChessBoard _B )
{
short int i;
short int j;
if(depth==0)
return Evaluate(_B);
vector< pair<int,int> > ::iterator it;
vector< pair<int,int> > Z;
int bestValue = -INFINITY;
for( i = 0; i < 8; i++ )
for( j = 0; j < 8; j++ )
{
if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==BLACK )
{
Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B);
for(it=Z.begin();it!=Z.end();it++)
{
pair<int,int> temp;
temp.first=i,temp.second=j;
ChessPieces* DestinationPiece;
DestinationPiece=_B.Board[(*it).first][(*it).second];
//Moving
_B.Board[(*it).first][(*it).second]=_B.Board[i][j];
_B.Board[i][j]=EMPTY;
//
int value = minSearch( depth-1 , _B );
if( value > bestValue )
bestValue = value;
//Undo Move
_B.Board[i][j]=_B.Board[((*it).first)][(*it).second];
_B.Board[(*it).first][(*it).second]=DestinationPiece;
}
}
}
return bestValue;
}
最佳答案
你没有做 quiescence search , 所以愚蠢的举动可能是由于众所周知的 horizon effect固定深度极小极大搜索容易受到影响。至少,您应该扩展搜索任何强制移动、检查或捕获,其中一 block 捕获了相等或更大值(value)的一个。
关于c++ - 一个简单的国际象棋 Minimax,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10372585/
我正在为一个小游戏实现 minimax,我注意到一些我称之为“拖延”的事情。归结为一个非常简单的例子: 在夺旗游戏中,旗帜在玩家 A 上方一格,玩家 B 距离玩家 50 格。轮到 A,他可以向前搜索
我正在努力使用 miniMax 算法构建一个基本的 tictactoe 游戏,并且我在 JavaScript 中有一个可以运行的实现。然而,我正在向它提供一些测试板状态,但它似乎没有按我预期的方式工作
我正在为 Connect 4 编写 MiniMax 代码。基本上,我有一个 SimpleMiniMax 类,它有一个方法 minimax (接受 grid 的输入),该方法应该返回类 Move 的实例
我正在尝试用 Java 编写一个小型 AI 算法来实现 miniMax 算法。 此游戏所基于的游戏是双人游戏,两名玩家每回合各走一步,每个棋盘位置都会导致每位玩家得分。玩家 X 位置的“质量”是通过从
我正在为一个简单的国际象棋引擎制作一个极小极大算法,但是遇到了一些困难。我已经运行了我的代码几个小时但无济于事,它似乎仍然输出错误的结果;当我威胁它的一个棋子并且它有一个有效的移动可以挽救该棋子时,它
我正在构建一个 Tic Tac Toe 解决机器人。为了练习,我使用 minimax 算法写了一个 Tic Tac Toe 游戏,效果很好。当我想将我的代码移植到 Controller 时,我发现这个
我目前正在使用 C# 开发针对 AI 的西洋跳棋游戏。我尝试使用 minimax 算法来实现 AI。尽管我的功能有效,但它选择的 Action 根本不符合逻辑。我用很多游戏和算法测试了它,当有很多更好
我正在设计一款 3D 井字棋游戏,发现时间限制了我的 Minimax 算法的深度。虽然深度达到 6 在很大程度上是无关紧要的时间 (Depth 7 = 6 seconds >Depth 8 = 49
我正在使用 Realm of Racket 中给出的 stub 为滴答游戏构建 AI。书作为依据。到目前为止,一切进展顺利。但是,当我尝试运行我的 minimax 时树根上的函数,它返回一个列表,其中
我正在尝试用 C 语言创建完美的井字游戏。我正在使用 2D 数组来跟踪棋盘。 我已将问题缩小到我的 minimax 函数对每个潜在移动进行评分的方式,但我在调试它时遇到了麻烦,因为错误通常发生在第二步
我在 Python 中为基本的井字棋 AI 实现了一个极小极大算法,如下所示: def minimax(currentBoard, player): if isGameOver(current
我正在研究 Minimax 算法来构建五子棋游戏。我对 Minimax 的问题是,在子节点中具有相同的评估值,这是真正添加到父节点或随机添加的。 Example tree from Wiki 所以从上
考虑到我正在从头开始构建井字游戏,我目前正在尝试使用 minimax 算法,这样我就可以让计算机作为玩家 1,而我自己作为玩家 2。我想我理解 minimax 算法(作为某种形式的深度第一次搜索)。
据我所知,最简单形式的 Minimax 算法的工作方式如下:自下而上遍历游戏树,如果轮到玩家,则将所有子节点的最大分数分配给当前节点,否则最低分数。叶子根据游戏输出进行评分,比方说赢+1,平0,输-1
我正在尝试打印出 Mini Max 的访问状态和效用。当值从终端状态返回到其根时,我遇到了问题,从而导致我访问的状态实用程序值中的 4 个不正确。我只是不知道是什么原因导致了这个错误。我很确定我的 M
我正在使用带 alpha-beta 剪枝的极小极大算法编写黑白棋引擎。它工作正常,但我发现了以下问题: 当算法发现位置丢失时,它会按预期返回 -INFINITY,但在在这种情况下,我无法追踪“最佳”走
我自己的国际象棋引擎使用 minimax 算法搜索国际象棋走法有问题我使用 5 层深度搜索并且只有 Material /奖励/移动性评估,但即使我给出它也会做出愚蠢的移动并牺牲有值(value)的棋子
我正在尝试实现一个使用 Minimax 进行点和框游戏的 AI (http://en.wikipedia.org/wiki/Dots_and_Boxes) 这是我目前所拥有的: public
我正在尝试让 minmax 算法(计算机 AI)在我的井字游戏中发挥作用。我已经坚持了好几天了。从本质上讲,我不明白为什么计算机 AI 只是简单地将它的标记 ("O") 从棋盘 block 0-8 中
我的目标摘要:弄清楚在使用我认为不能进行尾递归的算法时,如何使用连续传递样式来避免堆栈溢出。或者,找到一种方法使函数尾递归。 详情: 我是 F# 的新手(以及一般的函数式编程),我正在尝试使用 alp
我是一名优秀的程序员,十分优秀!