Минимакс с проблемами обрезки альфа-бета

Я делаю C ++ программу для игры палочки для еды.

Это действительно простая игра, в которой всего 625 игровых состояний (и даже ниже, если учесть симметрию и недоступные состояния). Я прочитал минимаксный и альфа-бета-алгоритмы, в основном для крестики-нолики, но проблема, с которой я столкнулся, заключалась в том, что в крестики-нолики невозможно вернуться к предыдущему состоянию, в то время как это легко может произойти в палочках для еды. Поэтому при запуске кода это может привести к переполнению стека.

Я исправил это, добавив флаги для ранее посещенных состояний (я не знаю, правильно ли это делать), чтобы их можно было избежать, но теперь у меня проблема в том, что выходные данные не симметричны, как ожидалось.

Например, в начальном состоянии игры у каждого игрока есть один палец, поэтому все симметрично. Программа говорит мне, что лучший ход — это удар правой рукой левой, но не наоборот.

Мой исходный код —

#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;
}

Я передаю ходы от своего рода base-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;
}