I'm trying to implement my own Tic-Tac-Toe game and make a tree (data structure) which contains all possible moves (for Min-Max Algorithm).
At one point in function Add_Match(), i'm getting this runtime error:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc`
Interesting part of main() (int Tic-Tac-Toe.cpp):
if(victory(board)){
//the movement gave the victory to player 1, we save it
final.set_score(1);
match.push_back(final);
//reset for rematch
board.Reset();
final.Reset();
memory.Add_Match(match);
match.clear();
match.push_back(Choice());
matchs++;
}
My Board class:
class Board{
private:
int n_=3;
std::vector<std::vector<int>> board_;
public:
Board(){
board_= std::vector<std::vector<int>>(n_,std::vector<int>(n_));
Reset();
}
void Reset(){
for (size_t i = 0; i < n_; i++)
for (size_t j = 0; j < n_; j++)
board_[i][j]=0;
}
void PrintBoard(){
for (size_t i = 0; i < n_; i++){
std::cout<<std::endl;
for (size_t j = 0; j < n_; j++)
std::cout<<board_[i][j]<<" ";
}
std::cout<<std::endl;
}
int win(){
int winner=-1;
for (size_t i = 0; i < n_; i++)
for (size_t j = 0; j < n_; j++){
int player=board_[i][j];
//Right
if(player!=0 && j+2 == 2 && board_[i][j+1] == player && board_[i][j+2] == player)
winner=player;
//Left
else if(player!=0 && j-2 == 0 && board_[i][j-1] == player && board_[i][j-2] == player)
winner=player;
//Up
else if(player!=0 && i-2 == 0 && board_[i-1][j] == player && board_[i-2][j] == player)
winner=player;
//Down
else if(player!=0 && i+2 == 2 && board_[i+1][j] == player && board_[i+2][j] == player)
winner=player;
//Up-Right
else if(player!=0 && i-2 == 0 && j+2 == 2 && board_[i-1][j+1] == player && board_[i-2][j+2] == player)
winner=player;
//Up-Left
else if(player!=0 && i-2 == 0 && j-2 == 0 && board_[i-1][j-1] == player && board_[i-2][j-2] == player)
winner=player;
//Down-Left
else if(player!=0 && i+2 == 2 && j-2 == 0 && board_[i+1][j-1] == player && board_[i+2][j-2] == player)
winner=player;
//Down-Right
else if(player!=0 && i+2 == 2 && j+2 == 2 && board_[i+1][j+1] == player && board_[i+2][j+2] == player)
winner=player;
}
if(winner==-1 && Size()==9)
winner=0;
return winner;
}
bool CheckPosition(int row,int col){
if(board_[row][col]==0)
return true;
else
return false;
}
void Put(int player,int row,int col){
board_[row][col]=player;
}
int Size(){
int count=0;
for (size_t i = 0; i < n_; i++)
for (size_t j = 0; j < n_; j++)
if(board_[i][j]!=0)
count++;
return count;
}
int Get(int row,int col){
return board_[row][col];
}
bool Equals(Board board){
for (size_t i = 0; i < n_; i++)
for (size_t j = 0; j < n_; j++)
{
if(board_[i][j]!=board.Get(i,j))
return false;
}
return true;
}
};
My Choice class:
class Choice{
private:
Board board_;
int row_,col_,score_;
std::vector<Choice> childs_;
public:
Choice(Board board,int row,int col,int score){
board_=board;
row_=row;
col_=col;
score_=score;
}
Choice(){
Reset();
}
void Reset(){
board_.Reset();
row_=-1;
col_=-1;
score_=-1;
}
void Add_Child(Choice new_child){
childs_.push_back(new_child);
}
Choice* get_LastChild(){
return &childs_.back();
}
void Delete_Childs(){
childs_.clear();
}
Board get_Board(){return board_;}
Board *get_Board_Adress(){return &board_;}
int get_Row(){return row_;}
int get_Col(){return col_;}
std::vector<Choice> get_Childs(){return childs_;}
int get_Score(){return score_;}
void set_score(int score){score_=score;}
};
And my Tree_Min_Max class:
class Tree{
private:
Choice root_;
Choice *ptr;
public:
Tree(){
root_.Reset();
}
void Go_Root(){
ptr=&root_;
}
bool find(Choice node){
if(ptr->get_Board().Equals(node.get_Board()) && ptr->get_Row()==node.get_Row() && ptr->get_Col()==node.get_Col())
return true;
else
{
std::vector<Choice> childs = ptr->get_Childs();
for (size_t i = 0; i < childs.size(); i++)
{
ptr=&childs[i];
if(find(node))
return true;
}
return false;
}
}
bool Has(Choice node_to_find){
Go_Root();
bool found=find(node_to_find);
return found;
}
void Add_Match(std::vector<Choice> match){
Choice *parent;
for (size_t i = 0; i < match.size(); i++)
{
if(i==0)
parent=&root_;
else
{
if(!Has(match[i])){
parent->Add_Child(match[i]);
parent=parent->get_LastChild();
}
else
parent=ptr;
}
}
}
void clear(){
Go_Root();
root_.Delete_Childs();
}
};
I have debugged my code, but I can't properly find the error.
I think the bad_alloc is caused by a bad memory location in the stack, but how I can solve this?
Here is one clear error:
else
{
std::vector<Choice> childs = ptr->get_Childs();
for (size_t i = 0; i < childs.size(); i++)
{
ptr=&childs[i]; // <-- Bug
//...
You are storing the address of a local variable. When the childs vector goes out of scope, that pointer is no longer valid.
The error actually comes from this:
std::vector<Choice> get_Childs(){return childs_;}
You are returning a copy of the vector, and not the actual childs vector. The fix is to return a reference, not a copy:
std::vector<Choice>& get_Childs(){return childs_;}
and then:
std::vector<Choice>& childs = ptr->get_Childs();
Note the reference return value.