Tic Tac Toe — Реализация минимаксного алгоритма для Tic-Tac-Toe в переполнении стека
Я работал над реализацией C ++ минимально-сложного ИИ Tic-Tac-Toe, и я изо всех сил стараюсь заставить ИИ играть ходы, чтобы заблокировать игрока от победы. Я надеялся, что некоторые люди могут помочь мне, узнав, как обеспечить это.
Код узла
void Node::addToNodeList(int turn) {
childNodes.push_back(Node(G));
for (auto& child : childNodes) {
child.addToNodeList(-turn);
if (child.childNodes.empty()) {
float tempScore = child.determineMinimaxValue();
if (tempScore < score) {
score = tempScore;
}
} else {
for (int i = 0; i < child.childNodes.size(); i++) {
if (child.childNodes[i].score < score) {
score = child.childNodes[i].score;
}
}
}
}
}
float Node::determineMinimaxValue()
{
if (childNodes.empty()) {
if (G.getWinner() == 0) {
return 0.f;
} else if (G.getWinner() == -1) {
return -1.f;
} else if (G.getWinner() == 1) {
return 1.f;
}
} else {
for (auto& child : childNodes) {
child.determineMinimaxValue();
}
}
return 0;
}
Код AI Player
Node AIPlayer::minimaxMove(int player, GameBoard GB)
{
G = GB;
N = Node(G);
N.addToNodeList(player);
return N;
}
int AIPlayer::makeTheMove(GameBoard *GB, Node ND)
{
float smallest = 100;
for (unsigned int i = 0; i < ND.childNodes.size(); i++) {
smallest = std::min(smallest, ND.childNodes[i].score);
if (i == ND.childNodes.size() - 1) {
for (unsigned int j = 0; j < ND.childNodes.size(); j++) {
if (smallest == ND.childNodes[j].score) {
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
for (int z = 0; z < 3; z++) {
GB->playerBox[x][y][z] = ND.childNodes[j].G.playerBox[x][y][z];
GB->winCondition[x][y][z] = ND.childNodes[j].G.winCondition[x][y][z];
}
}
}
}
}
}
}
return 1;
}
Решение
Мне удалось получить ответ на этот вопрос, используя небольшую помощь от моего наставника и некоторое свободное использование for (auto &child : childNodes)
Код узла
void Node::addToNodeList(int turn) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
//for (int k = 0; k < 3; k++) {
if (G.playerBox[i][j][1] == 0) {
G.playerBox[i][j][1] = turn;
G.winCondition[i][j][1] = true;
childNodes.push_back(Node(G));
G.playerBox[i][j][1] = 0;
G.winCondition[i][j][1] = false;
}
//}
}
}
for (auto &child : childNodes) {
child.addToNodeList(-turn);
if (child.childNodes.empty()) {
int tempScore = child.determineMinimaxValue();
if (tempScore < score) {
score = tempScore;
}
}
else {
if (turn == -1) {
int smallest = 100000;
for (unsigned int i = 0; i < this->childNodes.size(); i++) {
smallest = std::min(smallest, this->childNodes[i].score);
}
score = smallest;
}
else {
int biggest = -100000;
for (unsigned int i = 0; i < this->childNodes.size(); i++) {
biggest = std::max(biggest, this->childNodes[i].score);
}
score = biggest;
}
}
}
int Node::determineMinimaxValue() {
if (G.getWinner() == 0) {
return 0;
}
else if (G.getWinner() == -1) {
return -1;
}
else if (G.getWinner() == 1) {
return 1;
}
else {
return 0;
}
}
Код AI Player
Node AIPlayer::minimaxMove(int player, GameBoard GB) {
G = GB;
N = Node(G);
N.addToNodeList(player);
return N;
}
int AIPlayer::makeTheMove(GameBoard *GB, Node ND) {
if (GB->getWinner() == 1 || GB->getWinner() == -1) {
return 1;
}
int smallest = 100000;
for (unsigned int i = 0; i < ND.childNodes.size(); i++) {
smallest = std::min(smallest, ND.childNodes[i].score);
}
for (unsigned int j = 0; j < ND.childNodes.size(); j++) {
if (smallest == ND.childNodes[j].score) {
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
for (int z = 0; z < 3; z++) {
GB->playerBox[x][y][z] = ND.childNodes[j].G.playerBox[x][y][z];
GB->winCondition[x][y][z] = ND.childNodes[j].G.winCondition[x][y][z];
}
}
}
}
}
return 1;
}
Другие решения