我在为游戏筷子做一个C程序。
这是一个非常简单的游戏,总共只有625个游戏状态(如果考虑到对称性和不可到达的状态,它甚至更低)。我读过minimax和alpha-beta算法,主要是针对tic-tac-toe的,但我遇到的问题是,在tic-tac-toe中,不可能循环回到以前的状态,而这在筷子中很容易发生。因此,当运行代码时,它将以堆栈溢出结束。
我通过添加以前访问过的州的标志来解决这个问题(我不知道这样做是否正确。)以便可以避免它们,但现在我的问题是输出并不像预期的那样对称。
例如,在游戏的开始状态下,每个玩家都有一个手指,所以它都是对称的。程序告诉我,最好的动作是用左手打我的右手,而不是相反。
我的源代码是-
#include <iostream>
#include <array>
#include <vector>
#include <limits>
std::array<int, 625> t; //Flags for visited states.
std::array<int, 625> f; //Flags for visited states.
int no = 0; //Unused. For debugging.
class gamestate
{
public:
gamestate(int x, bool t) : turn(t) //Constructor.
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
val[i][j] = x % 5;
x /= 5;
}
init();
}
void print() //Unused. For debugging.
{
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++)
std::cout << val[i][j] << "\t";
std::cout << "\n";
}
std::cout << "\n";
}
std::array<int, 6> canmove = {{ 1, 1, 1, 1, 1, 1 }}; //List of available moves.
bool isover() //Is the game over.
{
return ended;
}
bool won() //Who won the game.
{
return winner;
}
bool isturn() //Whose turn it is.
{
return turn;
}
std::vector<int> choosemoves() //Choose the best possible moves in the current state.
{
std::vector<int> bestmoves;
if(ended)
return bestmoves;
std::array<int, 6> scores;
int bestscore;
if(turn)
bestscore = std::numeric_limits<int>::min();
else
bestscore = std::numeric_limits<int>::max();
scores.fill(bestscore);
for (int i = 0; i < 6; i++)
if (canmove[i]) {
t.fill(0);
f.fill(0);
gamestate *play = new gamestate(this->playmove(i),!turn);
scores[i] = minimax(play, 0, std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
std::cout<<i<<": "<<scores[i]<<std::endl;
delete play;
if (turn) if (scores[i] > bestscore) bestscore = scores[i];
if (!turn) if (scores[i] < bestscore) bestscore = scores[i];
}
for (int i = 0; i < 6; i++)
if (scores[i] == bestscore)
bestmoves.push_back(i);
return bestmoves;
}
private:
std::array<std::array<int, 2>, 2 > val; //The values of the fingers.
bool turn; //Whose turn it is.
bool ended = false; //Has the game ended.
bool winner; //Who won the game.
void init() //Check if the game has ended and find the available moves.
{
if (!(val[turn][0]) && !(val[turn][1])) {
ended = true;
winner = !turn;
canmove.fill(0);
return;
}
if (!(val[!turn][0]) && !(val[!turn][1])) {
ended = true;
winner = turn;
canmove.fill(0);
return;
}
if (!val[turn][0]) {
canmove[0] = 0;
canmove[1] = 0;
canmove[2] = 0;
if (val[turn][1] % 2)
canmove[5] = 0;
}
if (!val[turn][1]) {
if (val[turn][0] % 2)
canmove[2] = 0;
canmove[3] = 0;
canmove[4] = 0;
canmove[5] = 0;
}
if (!val[!turn][0]) {
canmove[0] = 0;
canmove[3] = 0;
}
if (!val[!turn][1]) {
canmove[1] = 0;
canmove[4] = 0;
}
}
int playmove(int mov) //Play a move to get the next game state.
{
auto newval = val;
switch (mov) {
case 0:
newval[!turn][0] = (newval[turn][0] + newval[!turn][0]);
newval[!turn][0] = (5 > newval[!turn][0]) ? newval[!turn][0] : 0;
break;
case 1:
newval[!turn][1] = (newval[turn][0] + newval[!turn][1]);
newval[!turn][1] = (5 > newval[!turn][1]) ? newval[!turn][1] : 0;
break;
case 2:
if (newval[turn][1]) {
newval[turn][1] = (newval[turn][0] + newval[turn][1]);
newval[turn][1] = (5 > newval[turn][1]) ? newval[turn][1] : 0;
} else {
newval[turn][0] /= 2;
newval[turn][1] = newval[turn][0];
}
break;
case 3:
newval[!turn][0] = (newval[turn][1] + newval[!turn][0]);
newval[!turn][0] = (5 > newval[!turn][0]) ? newval[!turn][0] : 0;
break;
case 4:
newval[!turn][1] = (newval[turn][1] + newval[!turn][1]);
newval[!turn][1] = (5 > newval[!turn][1]) ? newval[!turn][1] : 0;
break;
case 5:
if (newval[turn][0]) {
newval[turn][0] = (newval[turn][1] + newval[turn][0]);
newval[turn][0] = (5 > newval[turn][0]) ? newval[turn][0] : 0;
} else {
newval[turn][1] /= 2;
newval[turn][0] = newval[turn][1];
}
break;
default:
std::cout << "\nInvalid move!\n";
}
int ret = 0;
for (int i = 1; i > -1; i--)
for (int j = 1; j > -1; j--) {
ret+=newval[i][j];
ret*=5;
}
ret/=5;
return ret;
}
static int minimax(gamestate *game, int depth, int alpha, int beta) //Minimax searching function with alpha beta pruning.
{
if (game->isover()) {
if (game->won())
return 1000 - depth;
else
return depth - 1000;
}
if (game->isturn()) {
for (int i = 0; i < 6; i++)
if (game->canmove[i]&&t[game->playmove(i)]!=-1) {
int score;
if(!t[game->playmove(i)]){
t[game->playmove(i)] = -1;
gamestate *play = new gamestate(game->playmove(i),!game->isturn());
score = minimax(play, depth + 1, alpha, beta);
delete play;
t[game->playmove(i)] = score;
}
else
score = t[game->playmove(i)];
if (score > alpha) alpha = score;
if (alpha >= beta) break;
}
return alpha;
} else {
for (int i = 0; i < 6; i++)
if (game->canmove[i]&&f[game->playmove(i)]!=-1) {
int score;
if(!f[game->playmove(i)]){
f[game->playmove(i)] = -1;
gamestate *play = new gamestate(game->playmove(i),!game->isturn());
score = minimax(play, depth + 1, alpha, beta);
delete play;
f[game->playmove(i)] = score;
}
else
score = f[game->playmove(i)];
if (score < beta) beta = score;
if (alpha >= beta) break;
}
return beta;
}
}
};
int main(void)
{
gamestate test(243, true);
auto movelist = test.choosemoves();
for(auto i: movelist)
std::cout<<i<<std::endl;
return 0;
}
我正在以 5 为基数到十进制的系统传递移动,因为每手牌都可以有 0 到 4 的值。
在代码中,我输入了状态-
3 3
4 1
输出说我应该打我的右手(1)到对方的右边(3),但它没有说我应该打我的对手的左边(也是3)
我认为问题是因为我处理无限循环的方式。
做这件事的正确方法是什么?或者如果这是正确的方法,那么我该如何解决这个问题呢?
另外,请让我知道如何改进我的代码。
非常谢谢。
编辑:
我已经按如下方式更改了我的极小极大函数,以确保无限循环的得分高于损失,但我仍然没有得到对称性。我还做了一个函数来增加分数的深度
static float minimax(gamestate *game, int depth, float alpha, float beta) //Minimax searching function with alpha beta pruning.
{
if (game->isover()) {
if (game->won())
return 1000 - std::atan(depth) * 2000 / std::acos(-1);
else
return std::atan(depth) * 2000 / std::acos(-1) - 1000;
}
if (game->isturn()) {
for (int i = 0; i < 6; i++)
if (game->canmove[i]) {
float score;
if(!t[game->playmove(i)]) {
t[game->playmove(i)] = -1001;
gamestate *play = new gamestate(game->playmove(i), !game->isturn());
score = minimax(play, depth + 1, alpha, beta);
delete play;
t[game->playmove(i)] = score;
} else if(t[game->playmove(i)] == -1001)
score = 0;
else
score = adddepth(t[game->playmove(i)], depth);
if (score > alpha) alpha = score;
if (alpha >= beta) break;
}
return alpha;
} else {
for (int i = 0; i < 6; i++)
if (game->canmove[i]) {
float score;
if(!f[game->playmove(i)]) {
f[game->playmove(i)] = -1001;
gamestate *play = new gamestate(game->playmove(i), !game->isturn());
score = minimax(play, depth + 1, alpha, beta);
delete play;
f[game->playmove(i)] = score;
} else if(f[game->playmove(i)] == -1001)
score = 0;
else
score = adddepth(f[game->playmove(i)], depth);
if (score < beta) beta = score;
if (alpha >= beta) break;
}
return beta;
}
}
这是添加深度的函数-
float adddepth(float score, int depth) //Add depth to pre-calculated score.
{
int olddepth;
float newscore;
if(score > 0) {
olddepth = std::tan((1000 - score) * std::acos(-1) / 2000);
depth += olddepth;
newscore = 1000 - std::atan(depth) * 2000 / std::acos(-1);
} else {
olddepth = std::tan((1000 + score) * std::acos(-1) / 2000);
depth += olddepth;
newscore = std::atan(depth) * 2000 / std::acos(-1) - 1000;
}
return newscore;
}
免责声明:我不懂C,
坦率地说,我没有费心阅读游戏规则
。我现在已经阅读了规则,仍然坚持我所说的......但我仍然不知道C.不过,我可以介绍一些关于算法的一般知识,这些知识应该会让你朝着正确的方向前进。
不对称本身并不是一件坏事。如果两个招式完全等价,它应该选择其中一个,而不是像布里丹的屁股一样无助地站着。事实上,你应该确信你写的任何代理都有某种方法可以在它不能区分的策略中任意选择。
您应该更仔细地考虑拒绝访问以前的状态所暗示的效用方案。追求无限循环是一个有效的策略,即使你当前的表示会使程序崩溃;也许错误是溢出,而不是导致溢出的策略。如果让你在输掉游戏和拒绝让游戏结束之间做出选择,你希望你的经纪人更喜欢哪个?
如果你希望你的代理不惜一切代价避免失败——也就是说,你希望它更喜欢不确定的游戏而不是失败——那么我建议将任何重复的状态视为终端状态,并在输赢之间赋予它一个值。毕竟,从某种意义上说,它是终端——这是游戏将永远永远进入的循环,它的明确结果是没有赢家。然而,记住,如果你使用的是简单的极小值(一个效用函数,而不是两个),那么这意味着你的对手也将永恒的游戏视为中等结果。
这听起来可能很荒谬,但也许玩到无限实际上是一种合理的政策。记住,minimax假设了最坏的情况——一个完全理性的敌人,他的利益与你的完全相反。但是,例如,如果你正在写一个代理人与一个人比赛,那么这个人要么在逻辑上出错,要么最终会决定他们宁愿以输球结束比赛——所以你的代理人会从耐心地保持纳什均衡循环中受益!
如果你希望你的经纪人希望游戏最终结束,那么我建议你实施一个活的惩罚——一个添加到你的效用中的修正,它随着时间的推移而减少(无论是渐进的还是无限制的)。仔细实施,这可以保证,最终,任何一个结局都比另一个结局更好。对于这个解决方案,你需要小心考虑这对你的对手意味着什么偏好。
另一个常见的解决方案是深度限制你的搜索并实现一个评估函数。这将游戏状态作为其输入,并只是吐出一个效用值,这是它对最终结果的最佳猜测。这可以证明是最优的吗?不,除非你的评估函数只是完成极小极大,但这意味着你的算法将在合理的时间内完成。通过将这个粗略的估计埋在树中足够深的地方,你最终会得到一个非常合理的模型。然而,这会产生一个不完整的策略,这意味着它对重新规划代理比标准规划代理更有用。最小极大重新规划是复杂游戏的通常方法(如果我没弄错的话,它是深蓝遵循的基本算法),但是因为这是一个非常简单的游戏,你可能不需要采取这种方法。
请注意,所有这些解决方案都被概念化为对效用函数的数字更改或估计。一般来说,这比任意丢弃可能的策略更可取。毕竟,这就是你的效用函数的用途——任何时候你根据效用的数值以外的任何东西做出策略决策,你都在破坏你的抽象,使你的代码不那么健壮。
我做了一个Tic-Tac-Toe游戏,使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe(10x10)游戏制作一个计算机AI,但它的游戏树大得离谱。 我的代码是这样的,我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子: 和 我希望你明白了。 所以,我把我的计划从10x10改为3x3,效果很好。 然后我改变和,使其成为(4x4)井字游戏。 现在,我认为使用Alph
我到处寻找修复代码的答案,但在花了很长时间调试代码后,我发现自己陷入了绝望。问题是,我的minimax函数不会为可能的最佳移动返回正确的值,我甚至试图通过存储最佳的第一个移动(当深度=0时)来修复它,但如果解决方案不明显,那么该算法将严重失败。我还尝试修改基本案例的返回值,以便优先考虑早期的胜利,但这并没有解决问题。 目前我正在TictoE板上测试这个函数,助手类(如getMoves()或getW
我正在尝试用换位表实现增强的α-β-最小-最大修剪。我使用这个伪代码作为参考: http://people.csail.mit.edu/plaat/mtdf.html#abmem 这个算法有三个问题: > 我相信我应该在每个保存的换位表条目中存储深度(=到叶级的距离),并且仅在 entry.depth 时才使用条目 我想存储每个位置的最佳移动,以便在搜索停止后使用它进行移动排序和提取最佳移动。在纯
我正在尝试用Alpha-beta剪枝来实现Minimax,这是一款3D Tic-Tac-Toe游戏。然而,该算法似乎选择了次优路径。 例如,你可以通过直接跑过立方体的中间或穿过单板来赢得比赛。人工智能似乎选择了下一轮最佳的细胞,而不是当前一轮。 我尝试过重新创建并使用我返回的启发式算法,但没有取得多大进展。不管是哪一层,它似乎都有同样的问题。 代码在这里。 相关部分是和(以及'2'变体,这些只是我
我已经为游戏跳棋编写了一个带有alpha-beta修剪的minimax算法,现在我正尝试使用negamax方法重写它。我希望这两者是等价的,因为negamax只是一种编写minimax的技术。但由于某种原因,我的两种算法表现不同。当我在相同的输入上运行它们时,negamax版本似乎评估了更多的状态,所以我认为alpha-beta修剪一定有问题。 下面的代码显示了这两种算法(
我最近实现了极小极大和阿尔法贝塔修剪算法,我100%确定(自动分级器)我正确地实现了它们。但是当我执行我的程序时,它们的行为不同。我99%确定极小极大和阿尔法贝塔的结束状态应该是相同的。我说得对吗?它们在实现结果的路径上会有所不同吗?因为我们忽略了min将选择的一些值,而max不会选择这些值,反之亦然。