# Data structure and algorithm C++ tic-tac-toe Jingzi

Rarely today, campus activity day, school holidays, can do a good job in the near future plans but has no time to do things ~such as blogging [oblique smile]
I'm very busy recently. There are many ddl s. There will be three exams next week, and there will be English pre... next week. But I really want to record my recent learning achievements, otherwise I may forget it later.

P.S. This term's data structure course is really heartfelt, and Fei Chang likes the feeling that he successfully solved practical problems with the knowledge he learned in the course

# C++ Minimax Algorithms to Realize Man-Machine Fighting in Tingzi Chess

## Summary:

Because the core of this topic is the realization of the game, so here on how to play chess, how to judge whether the game is over and so on, do not elaborate.

The idea of realizing the game in this topic is as follows:

1. Setting up an evaluation mechanism to assign value to the current situation
Setting up two opposite comparative mechanisms, comparing the evaluation value of the two situations and deciding which side is most advantageous at present
2. Traverse - trial release, evaluation

Explain:

1. Because objectively speaking, both sides of the game are facing the same chess game, so an evaluation mechanism is set up to assign value to the current situation.
But for either side, the most advantageous situation for the opponent is the most disadvantageous situation for oneself. So set up two opposite comparison mechanisms.
2. Using recursion, at each level, traverse all positions that can be played, and assess the situation after the position is played for the current player.

## Specific Code & Explanation:

```#include<iostream>
#include<stdio.h>
#include"windows.h"
#define Stack_entry Move
#define maxstack 100
#define success true
#define underflow false
#define overflow false

using namespace std;
```
1. Definition of Move class (each step is a Move)
```class Move{
public:
Move();
Move(int r,int c);
int row;
int col;
};
Move::Move()
{
row=3;
col=3;
}
Move::Move(int r,int c)
{
row=r;
col=c;
}

```
1. Definition of stack (used to store all feasible steps (Move))
```class Stack{
public:
Stack();
bool empty()const;
bool pop();
bool top(Stack_entry &item);
bool push(const Stack_entry &item);
private:
int count;
Stack_entry entry[maxstack];
};
Stack::Stack()
{
count=0;
}
bool Stack::push(const Stack_entry &item)
{
bool outcome=success;
if(count>=maxstack)
return overflow;
else
entry[count++]=item;
return outcome;
}
bool Stack::pop()
{
bool outcome=success;
if(count==0)
outcome=underflow;
else --count;
return outcome;
}
bool Stack::top(Stack_entry &item)
{
bool outcome=success;
if(count==0)
return underflow;
else
item=entry[count-1];
return outcome;
}
bool Stack::empty()const
{
bool outcome=true;
if(count>0)
outcome=false;
return outcome;
}

```
1. Definition of Board Class (Defining Chessboard and Operation on Chessboard)
The emphasis is on better function, worst_case function and evaluate function.
```class Board{
public:
Board();
bool done()const;
bool is_ok(Move try_it);
void print()const;
bool better(int value,int old_value)const;
void play(Move try_it);
int worst_case()const;
int evaluate()const;
int legal_moves(Stack &moves)const;
void show_the_board();
private:
int square;
int moves_done;
int the_winner()const;
};

Board::Board()
/**Initialize the chessboard. The number of places without chessboard is 0.**/
{
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
square[i][j]=0;
moves_done=0;
}

void Board::print()const
/**Print chessboard**/
{
cout<<endl<<"    0   1   2"<<endl;
for(int i=0; i<3; i++)
{
cout<<endl<<i;
for(int j=0; j<3; j++)
{
if(square[i][j]==1)
cout<<"   O";
else if(square[i][j]==2)
cout<<"   X";
else cout<<"   -";
if(j==2) cout<<endl;
}
}
cout<<endl;
}

void Board::play(Move try_it)
/**Put "step" on the chessboard**/
{
square[try_it.row][try_it.col]=moves_done%2+1;
moves_done++;
}

int Board::the_winner()const
/**Returns the number (1 or 2) representing the winner and returns 0 if the winner or loser is uncertain.**/
{
int i;
for(i=0 ; i<3 ; i++)
if(square[i]&&square[i]==square[i]
&&square[i]==square[i])
return square[i];

for(i=0 ; i<3 ; i++)
if(square[i]&&square[i]==square[i]
&&square[i]==square[i])
return square[i];

if(square&&square==square
&&square==square)
return square;

if(square&&square==square
&&square==square)
return square;
return 0;
}

bool Board::done()const
/**Judging whether the game is over**/
{
return (moves_done==9||the_winner()>0);
}

int Board::legal_moves(Stack &moves)const
/**Store all feasible steps in the incoming stack**/
{
int count=0;
while(!moves.empty())
moves.pop();
for(int i=0; i<3; i++)
for(int j=0; j<3; j++)
if(square[i][j]==0)
{
Move can_play(i,j);
moves.push(can_play);
count++;
}
return count;
}

bool Board::is_ok(Move try_it)
/**Judging whether this step is feasible**/
{
if(try_it.row>=0&&try_it.row<3&&try_it.col>=0&&try_it.col<3
&&square[try_it.row][try_it.col]==0)
return true;
else return false;
}

int Board::evaluate()const
/**Return to a number, which reflects the winning or losing and how many steps have been taken.
For calculating the final result of each feasible step in the following recursive function**/
{
int winner=the_winner();
if(winner==1)
return 10-moves_done;//If the winner is 1, the return value is positive. The larger the number, the better for player 1.

else if(winner==2)
return moves_done-10;//Winner is 2, then the return value is negative. The smaller the number, the better for player 2.
else
return 0;//It ends in a draw
}

int Board::worst_case()const
{
if(moves_done%2)	//For Player 2
return 10;
else return -10;	//For Player 1
}

bool Board::better(int value,int old_value)const
/**Compare the two values which is the best**/
{
if(moves_done%2)	//For Player 2
return value<old_value;
else				//For Player 1
return value>old_value;
}
```

Put on a sketch to understand: 5. Very important functions.
Responsible for identifying the most beneficial step for the current player.

```int look_ahead(const Board &game, int depth, Move &recommended)
{
if(game.done()||depth==0)
return game.evaluate();
else
{
Stack moves;
game.legal_moves(moves);
int value;
int best_value=game.worst_case();
while(!moves.empty())
{
moves.top(try_it);
Board new_game=game;
new_game.play(try_it);
if(game.better(value,best_value))
{
best_value=value;
recommended=try_it;
}
moves.pop();
}
return best_value;
}
}
```
1. Print related information
```void instructions()
{
cout<<"Welcome to the Jingzi game! You will begin to play with this computer."<<endl
<<"The rules of the game are simple, just input the coordinates of the pieces."<<endl
<<"Reminder: O For you, X Represent your opponent."<<endl<<endl;
}

void print_the_result(int result)
{
if(result>0)
else if(result<0)
cout<<"\noops!You lost!\n"<<endl;
else cout<<"\n This Bureau and bureau.\n"<<endl;
}

```
1. Play a game of chess
```int play_game(int intel)
{
Board game;
Move player1_choice;
Move player2_choice;

while(intel<1||intel>9)
{
cout<<"IQ should be greater than or equal to 1, less than or equal to 9."<<endl;
cin>>intel;
}
system("cls");
game.print();
while(!game.done())
{
cout<<"Please enter position coordinates:\n";                  //Player playing chess
cin>>player1_choice.row>>player1_choice.col;
while(!game.is_ok(player1_choice))
{
cout<<"You can't play chess in this place."<<endl;
cin>>player1_choice.row>>player1_choice.col;
}
game.play(player1_choice);
if(game.done())
{
system("cls");
game.print();
break;
}

look_ahead(game , intel , player2_choice);  //Computer playing chess
game.play(player2_choice);

system("cls");
game.print();
}
print_the_result(game.evaluate());
return game.evaluate();
}
```
1. Main function. You can play many games of chess and count the wins and losses.
```int main(){
int win0=0,win1=0,win2=0;
int winner;
char command;
int intel=0;

instructions();
cout<<"Do you start the game? Input Arbitrary None N Characters to start the game."<<endl;
cin>>command;
if(command!='N'&&command!='n')
{
while(intel<1||intel>9)
{
cout<<"IQ should be greater than or equal to 1, less than or equal to 9."<<endl;
cin>>intel;
}
system("cls");
}

while(command!='N'&&command!='n')
{
winner=play_game(intel);
if(winner==0) win0++;
else if(winner>0) win1++;
else win2++;
cout<<"Do you want to continue playing? Input Arbitrary None N Characters to continue."<<endl;
cin>>command;
system("cls");
}
if((win0+win1+win2)!=0)
cout<<"With IQ"<<intel<<"In computer games:"<<endl
<<"  You won. "<<win1<<" second"<<endl
<<"The computer won. "<<win2<<" second"<<endl
<<"Bilateral tie "<<win0<<" second"<<endl;
getchar();
return 0;
}
```

## Finally, I want to say:

Do not write do not know, write a startle.
A seemingly simple little program has to write so much.
Therefore, the road is long and far-reaching, I will search up and down.

Okay, that's 8. Time flies so fast that I missed my meal unconsciously and my computer is about to run out of power.
But I have to say it feels good.

—— April 18, 2019 in the Library

Keywords: less Windows

Added by twizler on Thu, 16 May 2019 02:04:26 +0300