深度优先极小极大分割错误
Depth first Minimax Segmentation Fault
我正在尝试使用深度优先搜索和 minimax 在 C++ 中制作反向 4x3 tic tac toe 游戏。每当树试图获得极小极大值时，我都会收到分段错误，我不确定为什么。我已经看过我的逻辑很多次了，但我似乎看不出问题所在。我不认为它以某种方式正确地创建了树。
我对深度的想法首先是它会查看 parent 节点，如果它没有所有的 children 它将创建下一个 child 节点，将 parent 板复制到 child 板，然后对于 childNum 数组中的每个 child，它将跳过与数字 child 一样多的空格，然后相应地在黑板上放一个 X 或 O。然后，如果它不是结束状态，它会将 child 节点发送到 getMove() 一旦它到达结束状态，它将将该值存储在 parent 节点中并发送 parent 节点到 getMove() 并返回树。
任何人都可以看到是什么导致了这个分段错误或我的代码中存在的任何其他错误吗？这是：
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <ctype.h>
#include <iostream>
using namespace std;
struct node_t{
node_t* parent;
int minimax;
int childrenVals[12];
bool isMax;
char board[4][3];
int level;
bool xmove;
node_t* child;
};
void getMove(node_t *root);
void printBoard(char board[4][3]);
int checkStatus(char board[4][3]);
int getChildNum( int minimax[12]);
int status = -2;
char myBoard[4][3];
int main(){
//create root node
node_t n;
node_t* root;
root = &n;
root->board[0][0] = '1';
root->board[0][1] = '2';
root->board[0][2] = '3';
root->board[1][0] = '4';
root->board[1][1] = '5';
root->board[1][2] = '6';
root->board[2][0] = '7';
root->board[2][1] = '8';
root->board[2][2] = '9';
root->board[3][0] = '/';
root->board[3][1] = '*';
root->board[3][2] = '-';
root->parent = NULL;
root->child = NULL;
root->isMax = true;
root->xmove = true;
root-> level = 0;
for(int i = 0; i < 12; i++){
root->childrenVals[i] = -2;
}
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
myBoard[i][j] = root->board[i][j];
}
}
cout<<"Welcome to Reverse Tic Tac Toe! Here is the board:"<<endl;
printBoard(root->board);
cout<<"To make a move, you will type in the number or symbol "<<endl;
cout<<"of the box you would like to place your piece in. "<<endl;
cout<<endl;
cout<<"Would you like to go first or second? (type 1 or 2):"<<endl;
char order;
char Omove;
bool isValid = false;
bool gameOver = false;
int gameValue;
//Get order
cin >> order;
while(order !='1' && order != '2'){
if(order != '1' && order != '2'){
cout<<"Please type a 1 if you would like to go first and a 2 if you
would like to go second:";
cin >> order;
}
else{
break;
}
}
if(order == '2'){
root->xmove = true;
getMove(root);
//root->board = myBoard;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
root->board[i][j] = myBoard[i][j];
}
}
root->level++;
printBoard(root->board);
}
while(gameOver == false){
cout<< "Your move:";
while(isValid == false){
cin >> Omove;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
if(root->board[i][j] == Omove && Omove != 'X' && Omove != 'O
'){
root->board[i][j] = 'O';
isValid = true;
}
}
}
if(isValid == false){
cout<<"Invalid move, please look at the board and try again:";
}
}
root->level++;
printBoard(root->board);
gameValue = checkStatus(root->board);
if(gameValue != -2){
gameOver = true;
}
else{
getMove(root);
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
root->board[i][j] = myBoard[i][j];
}
}
root->level++;
root->isMax = true;
printBoard(root->board);
if(gameValue != -2){
gameOver = true;
}
}
}
if(gameOver == 1){
cout<<"You lose!"<<endl;
}
else if(gameOver == -1){
cout<<"You win!"<<endl;
}
else if(gameOver == 0){
cout<<"It's a tie!"<<endl;
}
return 0;
}
void getMove(node_t *node){
status = checkStatus(node->board);
//if node is not an end state
if(status == -2){
int childNum = 0;
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] == 0 || node->childrenVals[i] == 1 || node-
>childrenVals[i] == -1){
childNum++;
}
}
//if node does not have all its children
if(childNum != 12 - node->level){
if(childNum > 0){
//delete current child pointer
delete node->child;
}
//create child Node
node_t* child = new node_t;
child->parent = node;
node->child = child;
child->level = node->level + 1;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
child->board[i][j] = node->board[i][j];
}
}
for(int i = 0; i < 12; i++){
child->childrenVals[i]= -2;
}
if(node->isMax == true){
child->isMax = false;
}
else{
child->isMax = true;
}
//xmove means the children of that node move for X
if(node->xmove == true){
child->xmove = false;
}
else{
child->xmove = true;
}
int openSpace = 0;
bool shouldbreak = false;
for(int i=0; i < 4; i++){
for(int j=0; j< 3; j++){
if(child->board[i][j] != 'X' && child->board[i][j] != 'O'){
if(openSpace == childNum){
if(node->xmove){
child->board[i][j] = 'X';
shouldbreak = true;
break;
}
else{
child->board[i][j] = 'O';
shouldbreak = true;
break;
}
}
else{
openSpace++;
}
}
if(shouldbreak == true){
break;
}
}
if(openSpace == childNum){
break;
}
}
// cout<<"Level: "<<node->level<<endl;
// printBoard(child->board);
// cout<<endl;
getMove(child);
}
//if node does have all its children
else{
//cout<<"Level: "<<node->level<<endl;
// printBoard(node->board);
//n is used for the case that it is back to the root node
int n;
if(node->isMax == true){
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] > node->minimax){
node->minimax = node->childrenVals[i];
n = i;
}
}
}
else{
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] < node->minimax){
node->minimax = node->childrenVals[i];
n = i;
}
}
}
//if not at root node
if(node->parent != NULL){
int next = getChildNum(node->parent->childrenVals);
node->parent->childrenVals[next] = node->minimax;
node_t* temp = node->parent;
node->parent = NULL;
getMove(temp);
}
//if at root node
else{
//get move from root by recreating nth child
int openSpace = 0;
for(int i=0; i < 4; i++){
for(int j=0; j< 3; j++){
if(node->board[i][j] == 'X' || node->board[i][j] == 'O'){
//go to next space
}
else{
if(openSpace == n){
node->board[i][j] = 'X';
break;
}
else{
openSpace++;
}
}
//may have to do a conditional break here
}
}
//set myBoard = this board
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
myBoard[i][j] = node->board[i][j];
}
}
return;
}
}
}
//if node is an end state
else{
if(node->parent != NULL){
int next = getChildNum(node->parent->childrenVals);
node->parent->childrenVals[next] = status;
getMove(node->parent);
}
}
}
int checkStatus(char board[4][3]){
//returns -2 for no win loss or draw
//returns 1 for win
//returns -1 for loss
//returns 0 for draw
if( (board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X')||
(board[0][0] == 'X' && board[0][1] == 'X' && board[0][2] == 'X')||
(board[0][0] == 'X' && board[1][0] == 'X' && board[2][0] == 'X')||
(board[0][1] == 'X' && board[1][1] == 'X' && board[2][1] == 'X')||
(board[0][2] == 'X' && board[1][2] == 'X' && board[2][2] == 'X')||
(board[0][2] == 'X' && board[1][1] == 'X' && board[2][0] == 'X')||
(board[1][0] == 'X' && board[2][1] == 'X' && board[3][2] == 'X')||
(board[1][0] == 'X' && board[1][1] == 'X' && board[1][2] == 'X')||
(board[1][0] == 'X' && board[2][0] == 'X' && board[3][0] == 'X')||
(board[1][1] == 'X' && board[2][1] == 'X' && board[3][1] == 'X')||
(board[1][2] == 'X' && board[2][2] == 'X' && board[3][2] == 'X')||
(board[1][2] == 'X' && board[2][1] == 'X' && board[3][0] == 'X')||
(board[2][0] == 'X' && board[2][1] == 'X' && board[2][2] == 'X')||
(board[3][0] == 'X' && board[3][1] == 'X' && board[3][2] == 'X')){
return -1;
}
if( (board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O')||
(board[0][0] == 'O' && board[0][1] == 'O' && board[0][2] == 'O')||
(board[0][0] == 'O' && board[1][0] == 'O' && board[2][0] == 'O')||
(board[0][1] == 'O' && board[1][1] == 'O' && board[2][1] == 'O')||
(board[0][2] == 'O' && board[1][2] == 'O' && board[2][2] == 'O')||
(board[0][2] == 'O' && board[1][1] == 'O' && board[2][0] == 'O')||
(board[1][0] == 'O' && board[2][1] == 'O' && board[3][2] == 'O')||
(board[1][0] == 'O' && board[1][1] == 'O' && board[1][2] == 'O')||
(board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O')||
(board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O')||
(board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O')||
(board[1][2] == 'O' && board[2][1] == 'O' && board[3][0] == 'O')||
(board[2][0] == 'O' && board[2][1] == 'O' && board[2][2] == 'O')||
(board[3][0] == 'O' && board[3][1] == 'O' && board[3][2] == 'O')){
return 1;
}
//if it has not returned a win or a loss and the board is full return draw
bool isFull = true;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
if(board[i][j] != 'X' && board[i][j] != 'O'){
isFull = false;
}
}
}
if(isFull == true){
return 0;
}
else{
return -2;
}
}
int getChildNum( int childrenVals[12]){
//return index to know which child needs to be created next
for(int i = 0; i < 12; i++){
if(childrenVals[i] == -2){
return i;
}
}
return -1;
}
void printBoard(char board[4][3]){
for(int i = 0; i < 4; i++){
cout<<"|"<<board[i][0]<<"|";
cout<<"|"<<board[i][1]<<"|";
cout<<board[i][2]<<"|"<<endl;
}
cout<<endl;
}
启动调试器，例如 gdb，并从那里运行 您的代码。当它出现错误时，如果您将调试器配置为查找您的源文件，它会在您的代码中显示有问题的行。对于简单的情况，当二进制文件和源代码在同一个目录时，调试器通常可以默认找到源代码。
否则，在代码中放入cout或printf()行，分别在关键点打印1、2、3、....。 运行 代码，然后你可以看到它介于哪两个 printfs 之间。然后添加更多 printfs()，例如 1.1、1.2、1.3 ...，直到找到有问题的行，然后删除 printfs。
我正在尝试使用深度优先搜索和 minimax 在 C++ 中制作反向 4x3 tic tac toe 游戏。每当树试图获得极小极大值时，我都会收到分段错误，我不确定为什么。我已经看过我的逻辑很多次了，但我似乎看不出问题所在。我不认为它以某种方式正确地创建了树。
我对深度的想法首先是它会查看 parent 节点，如果它没有所有的 children 它将创建下一个 child 节点，将 parent 板复制到 child 板，然后对于 childNum 数组中的每个 child，它将跳过与数字 child 一样多的空格，然后相应地在黑板上放一个 X 或 O。然后，如果它不是结束状态，它会将 child 节点发送到 getMove() 一旦它到达结束状态，它将将该值存储在 parent 节点中并发送 parent 节点到 getMove() 并返回树。
任何人都可以看到是什么导致了这个分段错误或我的代码中存在的任何其他错误吗？这是：
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <vector>
#include <ctype.h>
#include <iostream>
using namespace std;
struct node_t{
node_t* parent;
int minimax;
int childrenVals[12];
bool isMax;
char board[4][3];
int level;
bool xmove;
node_t* child;
};
void getMove(node_t *root);
void printBoard(char board[4][3]);
int checkStatus(char board[4][3]);
int getChildNum( int minimax[12]);
int status = -2;
char myBoard[4][3];
int main(){
//create root node
node_t n;
node_t* root;
root = &n;
root->board[0][0] = '1';
root->board[0][1] = '2';
root->board[0][2] = '3';
root->board[1][0] = '4';
root->board[1][1] = '5';
root->board[1][2] = '6';
root->board[2][0] = '7';
root->board[2][1] = '8';
root->board[2][2] = '9';
root->board[3][0] = '/';
root->board[3][1] = '*';
root->board[3][2] = '-';
root->parent = NULL;
root->child = NULL;
root->isMax = true;
root->xmove = true;
root-> level = 0;
for(int i = 0; i < 12; i++){
root->childrenVals[i] = -2;
}
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
myBoard[i][j] = root->board[i][j];
}
}
cout<<"Welcome to Reverse Tic Tac Toe! Here is the board:"<<endl;
printBoard(root->board);
cout<<"To make a move, you will type in the number or symbol "<<endl;
cout<<"of the box you would like to place your piece in. "<<endl;
cout<<endl;
cout<<"Would you like to go first or second? (type 1 or 2):"<<endl;
char order;
char Omove;
bool isValid = false;
bool gameOver = false;
int gameValue;
//Get order
cin >> order;
while(order !='1' && order != '2'){
if(order != '1' && order != '2'){
cout<<"Please type a 1 if you would like to go first and a 2 if you
would like to go second:";
cin >> order;
}
else{
break;
}
}
if(order == '2'){
root->xmove = true;
getMove(root);
//root->board = myBoard;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
root->board[i][j] = myBoard[i][j];
}
}
root->level++;
printBoard(root->board);
}
while(gameOver == false){
cout<< "Your move:";
while(isValid == false){
cin >> Omove;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
if(root->board[i][j] == Omove && Omove != 'X' && Omove != 'O
'){
root->board[i][j] = 'O';
isValid = true;
}
}
}
if(isValid == false){
cout<<"Invalid move, please look at the board and try again:";
}
}
root->level++;
printBoard(root->board);
gameValue = checkStatus(root->board);
if(gameValue != -2){
gameOver = true;
}
else{
getMove(root);
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
root->board[i][j] = myBoard[i][j];
}
}
root->level++;
root->isMax = true;
printBoard(root->board);
if(gameValue != -2){
gameOver = true;
}
}
}
if(gameOver == 1){
cout<<"You lose!"<<endl;
}
else if(gameOver == -1){
cout<<"You win!"<<endl;
}
else if(gameOver == 0){
cout<<"It's a tie!"<<endl;
}
return 0;
}
void getMove(node_t *node){
status = checkStatus(node->board);
//if node is not an end state
if(status == -2){
int childNum = 0;
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] == 0 || node->childrenVals[i] == 1 || node-
>childrenVals[i] == -1){
childNum++;
}
}
//if node does not have all its children
if(childNum != 12 - node->level){
if(childNum > 0){
//delete current child pointer
delete node->child;
}
//create child Node
node_t* child = new node_t;
child->parent = node;
node->child = child;
child->level = node->level + 1;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
child->board[i][j] = node->board[i][j];
}
}
for(int i = 0; i < 12; i++){
child->childrenVals[i]= -2;
}
if(node->isMax == true){
child->isMax = false;
}
else{
child->isMax = true;
}
//xmove means the children of that node move for X
if(node->xmove == true){
child->xmove = false;
}
else{
child->xmove = true;
}
int openSpace = 0;
bool shouldbreak = false;
for(int i=0; i < 4; i++){
for(int j=0; j< 3; j++){
if(child->board[i][j] != 'X' && child->board[i][j] != 'O'){
if(openSpace == childNum){
if(node->xmove){
child->board[i][j] = 'X';
shouldbreak = true;
break;
}
else{
child->board[i][j] = 'O';
shouldbreak = true;
break;
}
}
else{
openSpace++;
}
}
if(shouldbreak == true){
break;
}
}
if(openSpace == childNum){
break;
}
}
// cout<<"Level: "<<node->level<<endl;
// printBoard(child->board);
// cout<<endl;
getMove(child);
}
//if node does have all its children
else{
//cout<<"Level: "<<node->level<<endl;
// printBoard(node->board);
//n is used for the case that it is back to the root node
int n;
if(node->isMax == true){
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] > node->minimax){
node->minimax = node->childrenVals[i];
n = i;
}
}
}
else{
for(int i = 0; i < 12 - node->level; i++){
if(node->childrenVals[i] < node->minimax){
node->minimax = node->childrenVals[i];
n = i;
}
}
}
//if not at root node
if(node->parent != NULL){
int next = getChildNum(node->parent->childrenVals);
node->parent->childrenVals[next] = node->minimax;
node_t* temp = node->parent;
node->parent = NULL;
getMove(temp);
}
//if at root node
else{
//get move from root by recreating nth child
int openSpace = 0;
for(int i=0; i < 4; i++){
for(int j=0; j< 3; j++){
if(node->board[i][j] == 'X' || node->board[i][j] == 'O'){
//go to next space
}
else{
if(openSpace == n){
node->board[i][j] = 'X';
break;
}
else{
openSpace++;
}
}
//may have to do a conditional break here
}
}
//set myBoard = this board
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
myBoard[i][j] = node->board[i][j];
}
}
return;
}
}
}
//if node is an end state
else{
if(node->parent != NULL){
int next = getChildNum(node->parent->childrenVals);
node->parent->childrenVals[next] = status;
getMove(node->parent);
}
}
}
int checkStatus(char board[4][3]){
//returns -2 for no win loss or draw
//returns 1 for win
//returns -1 for loss
//returns 0 for draw
if( (board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X')||
(board[0][0] == 'X' && board[0][1] == 'X' && board[0][2] == 'X')||
(board[0][0] == 'X' && board[1][0] == 'X' && board[2][0] == 'X')||
(board[0][1] == 'X' && board[1][1] == 'X' && board[2][1] == 'X')||
(board[0][2] == 'X' && board[1][2] == 'X' && board[2][2] == 'X')||
(board[0][2] == 'X' && board[1][1] == 'X' && board[2][0] == 'X')||
(board[1][0] == 'X' && board[2][1] == 'X' && board[3][2] == 'X')||
(board[1][0] == 'X' && board[1][1] == 'X' && board[1][2] == 'X')||
(board[1][0] == 'X' && board[2][0] == 'X' && board[3][0] == 'X')||
(board[1][1] == 'X' && board[2][1] == 'X' && board[3][1] == 'X')||
(board[1][2] == 'X' && board[2][2] == 'X' && board[3][2] == 'X')||
(board[1][2] == 'X' && board[2][1] == 'X' && board[3][0] == 'X')||
(board[2][0] == 'X' && board[2][1] == 'X' && board[2][2] == 'X')||
(board[3][0] == 'X' && board[3][1] == 'X' && board[3][2] == 'X')){
return -1;
}
if( (board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O')||
(board[0][0] == 'O' && board[0][1] == 'O' && board[0][2] == 'O')||
(board[0][0] == 'O' && board[1][0] == 'O' && board[2][0] == 'O')||
(board[0][1] == 'O' && board[1][1] == 'O' && board[2][1] == 'O')||
(board[0][2] == 'O' && board[1][2] == 'O' && board[2][2] == 'O')||
(board[0][2] == 'O' && board[1][1] == 'O' && board[2][0] == 'O')||
(board[1][0] == 'O' && board[2][1] == 'O' && board[3][2] == 'O')||
(board[1][0] == 'O' && board[1][1] == 'O' && board[1][2] == 'O')||
(board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O')||
(board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O')||
(board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O')||
(board[1][2] == 'O' && board[2][1] == 'O' && board[3][0] == 'O')||
(board[2][0] == 'O' && board[2][1] == 'O' && board[2][2] == 'O')||
(board[3][0] == 'O' && board[3][1] == 'O' && board[3][2] == 'O')){
return 1;
}
//if it has not returned a win or a loss and the board is full return draw
bool isFull = true;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
if(board[i][j] != 'X' && board[i][j] != 'O'){
isFull = false;
}
}
}
if(isFull == true){
return 0;
}
else{
return -2;
}
}
int getChildNum( int childrenVals[12]){
//return index to know which child needs to be created next
for(int i = 0; i < 12; i++){
if(childrenVals[i] == -2){
return i;
}
}
return -1;
}
void printBoard(char board[4][3]){
for(int i = 0; i < 4; i++){
cout<<"|"<<board[i][0]<<"|";
cout<<"|"<<board[i][1]<<"|";
cout<<board[i][2]<<"|"<<endl;
}
cout<<endl;
}
启动调试器，例如 gdb，并从那里运行 您的代码。当它出现错误时，如果您将调试器配置为查找您的源文件，它会在您的代码中显示有问题的行。对于简单的情况，当二进制文件和源代码在同一个目录时，调试器通常可以默认找到源代码。
否则，在代码中放入cout或printf()行，分别在关键点打印1、2、3、....。 运行 代码，然后你可以看到它介于哪两个 printfs 之间。然后添加更多 printfs()，例如 1.1、1.2、1.3 ...，直到找到有问题的行，然后删除 printfs。