Я пытаюсь сделать обратную игру в крестики-нолики 4×3 на языке c ++, используя поиск в глубину и минимакс. Я продолжаю получать ошибку сегментации всякий раз, когда дерево пытается получить минимаксное значение, и я не уверен почему. Я смотрел на мою логику несколько раз, и я просто не вижу проблемы. Я не думаю, что это как-то правильно создает дерево.
Сначала я задумался о глубине, что он будет смотреть на родительский узел, если у него не будет всех его потомков, он создаст следующий дочерний узел, скопирует родительскую плату в дочернюю, а затем для каждого дочернего элемента в массиве childNum будет пропустите столько пробелов, сколько это число потомков, затем поместите X или O соответственно на доске. Затем, если это не конечное состояние, он отправит этот дочерний узел в getMove (). Как только он попадет в конечное состояние, он сохранит это значение в родительском узле и отправит родительский узел в 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.