This article is neither original nor reproduced, so I chose a compromise solution: translation.
The main code in this article comes from C++ Backgammon AI_[PE]Classic Eight Cannons
Using the minimax algorithm, α-β pruning. After the recent optimization, the running speed has been improved a lot. When maxDepth is 3 (the root node is 4 layers), the O2 optimization is enabled and the Release version is compiled, and the search can be completed in about two seconds. This version changes maxDepth to 4, and the search time is about 30 seconds.
And I optimized the game experience based on the original code, and made the original code compile in the Dev editor (mainly under the guidance of the original blogger).
This article can modify the intelligence level (the penultimate line of the program, the 3 in brackets indicates the intelligence level, which can be adjusted up or down, 4~2), but 4 will be very slow, several minutes Only the next step
code show as below:
#include<iostream>
#include <vector>
#include <array>
#include <fstream>
#include <algorithm>
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
void color(int x) {<!-- -->
switch(x) {<!-- -->
case 1:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED );
break;
case 2:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_BLUE );
break;
case 3:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN);
break;
case 4:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_BLUE );
break;
case 5:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN);
break;
case 6:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_BLUE | FOREGROUND_GREEN);
break;
case 7:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY|FOREGROUND_GREEN|FOREGROUND_BLUE|FOREGROUND_RED);
break;
default:
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY|FOREGROUND_GREEN|FOREGROUND_BLUE|FOREGROUND_RED);
break;
}
}
class GameTree {<!-- -->
public:
class Node {<!-- -->
public:
enum State :uint8_t/*save memory*/ {<!-- --> SPACE, BLACK, WHITE };
private:
friend class GameTree;
static const uint8_t BOARDSIZE = 15;
int value;//The leaf node represents the result of the evaluation function, the MAX node represents the α value, and the MIN node represents the β value
int evaluateValue;//The result of evaluation function calculation, used for optimization
unsigned short depth;//depth
uint8_t lastX, lastY;//The xy coordinates of the last move
Node* father;//father node
std::vector<Node*> children;//child nodes
State **board;//chessboard
int Evaluate()const {<!-- --> //Evaluation function
static const auto EvaluateSome = [](State **board, uint8_t beginX, uint8_t endX, uint8_t beginY, uint8_t endY) {<!-- -->
static const auto EvaluateList = [](const std::array<State, 5> & amp; v) {<!-- --> //Assume you are white
//Judge the color and record the number of chess pieces
State lastColor = SPACE;
uint8_t bitList = 0;//Shogi chain is expressed in binary form, such as 01101
for (State i : v) {<!-- -->
if (i != lastColor) {<!-- -->
if (lastColor == SPACE)//the first chess piece encountered
lastColor = i;
else//There are pieces of different colors
return 0;
}
if (i != SPACE)
bitList = bitList * 2 + 1;
}
int result = 0;
switch (bitList) {<!-- -->
case 0://00000
result = 0;
break;
case 1://00001
case 2://00010
case 4://00100
case 8://01000
case 16://10000
result = 5;
break;
case 3://00011
case 24://11000
result = 80;
break;
case 6://00110
case 12://01100
result = 100;
break;
case 10://01010
result = 80;
break;
case 5://00101
case 20://10100
result = 60;
break;
case 9://01001
case 18://10010
result = 20;
break;
case 17://10001
result = 10;
break;
case 7://00111
case 28://11100
result = 800;
break;
case 14://01110
result = 1000;
break;
case 13://01101
case 26://11010
case 11://01011
case 22://10110
result = 800;
break;
case 19://10011
case 21://10101
case 25://11001
result = 600;
break;
case 15://01111
case 30://11110
result = 10000;
break;
case 29://11101
case 23://10111
result = 8000;
break;
case 27://11011
result = 6000;
break;
case 31://11111
return lastColor == WHITE ? INT_MAX : INT_MIN;
}
return lastColor == WHITE ? result : -result;//The opponent returns a negative value, and our side returns a positive value
};
int result = 0;
for (uint8_t i = beginX; i < endX; i ++ ) {<!-- --> //judging from four directions
for (uint8_t j = beginY; j < endY; j ++ ) {<!-- -->
if (j + 4 < endY) {<!-- -->
std::array<State, 5>v;
for (uint8_t k = 0; k < 5; k ++ )
v[k] = board[i][j + k];
const int t = EvaluateList(v);
if (t == INT_MAX || t == INT_MIN)// decide the winner and return directly
return t;
result += t;
}
if (i + 4 < endX) {<!-- -->
std::array<State, 5>v;
for (uint8_t k = 0; k < 5; k ++ )
v[k] = board[i + k][j];
const int t = EvaluateList(v);
if (t == INT_MAX || t == INT_MIN)// decide the winner and return directly
return t;
result += t;
}
if (i + 4 < endX & amp; & amp; j + 4 < endY) {<!-- -->
std::array<State, 5>v;
for (uint8_t k = 0; k < 5; k ++ )
v[k] = board[i + k][j + k];
const int t = EvaluateList(v);
if (t == INT_MAX || t == INT_MIN)// decide the winner and return directly
return t;
result += t;
}
if (i + 4 < endX & amp; & amp; j >= 4) {<!-- -->
std::array<State, 5>v;
for (uint8_t k = 0; k < 5; k ++ )
v[k] = board[i + k][j - k];
const int t = EvaluateList(v);
if (t == INT_MAX || t == INT_MIN)// decide the winner and return directly
return t;
result += t;
}
}
}
return result;
};
uint8_t beginX, endX, beginY, endY;
if (lastX <= 5)
beginX = 0;
else
beginX = lastX - 5;
endX = lastX + 5;
if (endX > BOARDSIZE)
endX = BOARDSIZE;
if (lastY <= 5)
beginY = 0;
else
beginY = lastY - 5;
endY = lastY + 5;
if (endY > BOARDSIZE)
endY = BOARDSIZE;
const int t = EvaluateSome(board, beginX, endX, beginY, endY);
if (t == INT_MAX || t == INT_MIN)// decide the winner and return directly
return t;
return t - EvaluateSome(father->board, beginX, endX, beginY, endY) + father->evaluateValue;
}
public:
//Constructor for non-root nodes
Node(Node* nf, uint8_t x, uint8_t y) :father(nf), lastX(x), lastY(y), depth(nf->depth + 1), value(0), board(new State* [BOARDSIZE ]) {<!-- -->
father->children.push_back(this);
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
board[i] = new State[BOARDSIZE];
memcpy(board[i], father->board[i], BOARDSIZE * sizeof(State));
}
board[lastX][lastY] = IsMaxNode() ? BLACK : WHITE;
evaluateValue = Evaluate();
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
delete[] board[i];
}
delete[] board;
board = nullptr;
}
//constructor for the root node
Node(int _depth, uint8_t x, uint8_t y) : father(nullptr), depth(_depth), lastX(x), lastY(y), value(0), evaluateValue(0), board(new State*[BOARDSIZE] ) {<!-- -->
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
board[i] = new State[BOARDSIZE];
memset(board[i], 0, BOARDSIZE * sizeof(State));
}
board[x][y] = IsMaxNode() ? BLACK : WHITE;
}
inline int GetEvaluateValue() const {<!-- -->
return evaluateValue;
}
inline bool IsMaxNode()const {<!-- --> //default computer backup
return depth & amp; 1u;//equivalent to depth%2
}
void Search(unsigned short _depth) {<!-- -->
if (_depth == 0 || this->evaluateValue == INT_MAX || this->evaluateValue == INT_MIN) {<!-- -->
this->value = this->evaluateValue;
return;
}
bool created = false;//Record whether a new Node is newly created, if not, there is no need to sort.
if (!board) {<!-- --> //not the root node
board = new State * [BOARDSIZE];
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
board[i] = new State[BOARDSIZE];
memcpy(board[i], father->board[i], BOARDSIZE * sizeof(State));
}
board[lastX][lastY] = IsMaxNode() ? BLACK : WHITE;
}
for (uint8_t i = 0; i < BOARDSIZE; i ++ ) {<!-- -->
for (uint8_t j = 0; j < BOARDSIZE; j ++ ) {<!-- -->
if (!board[i][j]) {<!-- -->
bool flag = false;
if (_depth >= 2) {<!-- --> //If the remaining depth is less than 2, the next layer must not have been searched
for (Node* child : this->children) {<!-- -->
if (child->lastX == i & amp; & amp; child->lastY == j) {<!-- --> // already searched
flag = true;
break;
}
}
}
if (!flag) {<!-- -->
new Node(this, i, j);
created = true;
}
}
}
}
if (IsMaxNode()) {<!-- -->
this->value = INT_MIN;
if (created) {<!-- -->
std::sort(this->children.begin(), this->children.end(), [](Node* a, Node* b) {<!-- -->
return a->GetEvaluateValue() > b->GetEvaluateValue();
});//Sort according to the valuation from large to small to increase the probability of pruning
}
} else {<!-- -->
this->value = INT_MAX;
if (created) {<!-- -->
std::sort(this->children.begin(), this->children.end(), [](Node* a, Node* b) {<!-- -->
return a->GetEvaluateValue() < b->GetEvaluateValue();
});//Sort from small to large according to valuation, increase the probability of pruning
}
}
auto ReleaseMemory = [this] {<!-- -->
if (father) {<!-- --> //not the root node
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
delete[] board[i];
}
delete[] board;
board = nullptr;
}
};
for (Node* child : this->children) {<!-- -->
child->Search(_depth - 1);
//α - β pruning
if (IsMaxNode()) {<!-- -->
if (child->value > this->value) {<!-- -->
this->value = child->value;
if (this->father & amp; & amp; this->value >= this->father->value & amp; & amp; this != this->father->children. front()) {<!- - -->
ReleaseMemory();
return;//pruning
}
}
} else {<!-- --> //MIN node
if (child->value <this->value) {<!-- -->
this->value = child->value;
if (this->father & amp; & amp; this->value <= this->father->value & amp; & amp; this != this->father->children. front()) {<!- - -->
ReleaseMemory();
return;//pruning
}
}
}
}
ReleaseMemory();
}
void DeleteAllButThis() {<!-- -->
if (!father->board)//parent node is not the root node
throw std::invalid_argument("this->father must be the root node!");
for (Node* n : father->children) {<!-- -->
if (n != this)
delete n;
}
board = new State * [BOARDSIZE];
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
board[i] = new State[BOARDSIZE];
memcpy(board[i], father->board[i], BOARDSIZE * sizeof(State));
delete[] father->board[i];
}
delete[] father->board;
board[lastX][lastY] = IsMaxNode() ? BLACK : WHITE;
free(father);//Avoid calling the destructor
father = nullptr;
}
inline bool IsFull()const {<!-- -->
return depth == BOARDSIZE * BOARDSIZE;
}
inline State GetWinner()const {<!-- -->
if (this->value == INT_MAX) {<!-- -->
return Node::WHITE;
} else if (this->value == INT_MIN) {<!-- -->
return Node::BLACK;
}
return Node::SPACE;
}
~Node() {<!-- -->
if (board) {<!-- -->
for (int i = 0; i < BOARDSIZE; + + i) {<!-- -->
delete[] board[i];
}
delete[] board;
}
for (Node* n : children) {<!-- -->
delete n;
}
}
};
private:
Node* root;
const unsigned short maxDepth;
public:
GameTree(unsigned short _maxDepth) : root(nullptr), maxDepth(_maxDepth) {<!-- -->
if (_maxDepth < 2)
throw std::invalid_argument("The maximum number of layers must be greater than or equal to 2!");
}
std::pair<uint8_t, uint8_t>AIGetNextPos(uint8_t x, uint8_t y) {<!-- -->
if (root) {<!-- -->
for (Node* node : root->children) {<!-- --> //Enter the branch selected by the user
if (node->lastX == x & amp; & amp; node->lastY == y) {<!-- -->
node->DeleteAllButThis();
root = node;
break;
}
}
} else {<!-- --> //First start
root = new Node(1, x, y);
}
root->Search(maxDepth);
if (root->IsFull())
return std::make_pair(19, 19);
for (Node* node : root->children) {<!-- --> //Select the one with the highest score
if (node->value == root->value) {<!-- -->
node->DeleteAllButThis();
root = node;
break;
}
}
return std::make_pair(root->lastX, root->lastY);
}
Node::State GetWinner()const {<!-- -->
return root->GetWinner();
}
void Run() {<!-- -->
while (1) {<!-- -->
int x, y;
do {<!-- -->
color(7);
std::cout << "Enter x,y coordinates";
color(3);
std::cin >> y >> x;
y-=1;
x-=1;
} while (x < 0 || y < 0 || x >= 15 || y >= 15 || (root & amp; & amp; root->board[x][y] != Node::SPACE) );
if (root) {<!-- -->
for (Node* node : root->children) {<!-- --> //Enter the branch selected by the user
if (node->lastX == x & amp; & amp; node->lastY == y) {<!-- -->
node->DeleteAllButThis();
root = node;
break;
}
}
} else {<!-- --> //First start
root = new Node(1, x, y);
}
system("cls");
for (int i = 0; i <= 15; i ++ ) {<!-- -->
for (int j = 0; j <= 15; j ++ ) {<!-- -->
color(6);
if (i==0 & amp; & amp; j<10)
cout <<" " <<j <<" ";
else if (i==0 & amp; & amp; j>=10)
cout <<j <<" ";
else if (j==0 & amp; & amp; i<10)
cout <<" " <<i <<" ";
else if (j==0 & amp; & amp; i>=10)
cout <<i <<" ";
else if (root->board[i-1][j-1] == Node::SPACE) {<!-- -->
color(5);
std::cout << "ten";
} else if (root->board[i-1][j-1] == Node::BLACK) {<!-- -->
color(2);
std::cout << "○ ";
} else {<!-- -->
color(7);
std::cout << "○ ";
}
}
std::cout << '\\
';
}
root->Search(maxDepth);
if (root->value == INT_MAX) {<!-- -->
std::cout << "Computer wins!";
break;
} else if (root->value == INT_MIN) {<!-- -->
std::cout << "Player wins!";
break;
} else if (root->IsFull()) {<!-- --> // Root->value==0 cannot be used to determine a tie, because a tie must be 0, but 0 is not necessarily a tie
std::cout << "Tie!";
break;
}
for (Node* node : root->children) {<!-- --> //Select the one with the highest score
if (node->value == root->value) {<!-- -->
node->DeleteAllButThis();
root = node;
break;
}
}
system("cls");
for (int i = 0; i <= 15; i ++ ) {<!-- -->
for (int j = 0; j <= 15; j ++ ) {<!-- -->
color(6);
if (i==0 & amp; & amp; j<10)
cout <<" " <<j <<" ";
else if (i==0 & amp; & amp; j>=10)
cout <<j <<" ";
else if (j==0 & amp; & amp; i<10)
cout <<" " <<i <<" ";
else if (j==0 & amp; & amp; i>=10)
cout <<i <<" ";
else if (root->board[i-1][j-1] == Node::SPACE) {<!-- -->
color(5);
std::cout << "ten";
} else if (root->board[i-1][j-1] == Node::BLACK) {<!-- -->
color(2);
std::cout << "○ ";
} else {<!-- -->
color(7);
std::cout << "○ ";
}
}
std::cout << '\\
';
}
if (root->value == INT_MAX) {<!-- -->
std::cout << "Computer wins!";
break;
} else if (root->value == INT_MIN) {<!-- -->
std::cout << "Player wins!";
break;
} else if (root->IsFull()) {<!-- --> // Root->value==0 cannot be used to determine a tie, because a tie must be 0, but 0 is not necessarily a tie
std::cout << "Tie!";
break;
}
}
}
~GameTree() {<!-- -->
delete root;
}
};
int main() {<!-- -->
cout <<"\\
\\
\\
\\
\\
\\
";
color(6);
Sleep(1000);
cout <<"Travel";
Sleep(1000);
cout <<"play";
Sleep(1000);
cout <<"open";
Sleep(1000);
cout <<"Begin";
Sleep(1000);
cout <<"!";
Sleep(2000);
system("cls");
for (int i = 0; i <= 15; i ++ ) {<!-- -->
for (int j = 0; j <= 15; j ++ ) {<!-- -->
color(6);
if (i==0 & amp; & amp; j<10)
cout <<" " <<j <<" ";
else if (i==0 & amp; & amp; j>=10)
cout <<j <<" ";
else if (j==0 & amp; & amp; i<10)
cout <<" " <<i <<" ";
else if (j==0 & amp; & amp; i>=10)
cout <<i <<" ";
else {<!-- -->
color(5);
std::cout << "ten";
}
}
std::cout << '\\
';
}
GameTree(3).Run();
}
Introduction to C++
Dev-C ++ is a set of free integrated development environment (IDE) for developing C/C ++ programs, with GPL as the distribution license, and MinGW and GDB as the compilation system and debugging system. Dev-C++ runs under Microsoft Windows.
The advantage of Dev-C++ is that it has a simple and friendly interface, easy installation, and supports single-file compilation, so it has become the first choice for many entry-level OI players and C++ language beginners. In NOIP, the provinces that offer Windows as a race system generally preset Dev-C++.
Dev-C++ originated from Bloodshed Dev-C++ written by Colin Laplace. This version has been discontinued since February 22, 2005. In 2006, Colin Laplace, the main developer of Dev-C++, once explained this: “Because I am busy with real-life affairs, I don’t have time to continue the development of Dev-C++.”
Orwell Dev-C++ is a derivative of Dev-C++ developed and maintained by independent programmer Orwell (Johan Mes). It has bugfixes for the original Dev-C++ and an updated compiler version. In general, Dev-C++ 5.x is Orwell Dev-C++. It was last updated in 2015 with version 5.11.
Embarcadero Dev-C++1 is the successor of Bloodshed Dev-C++ and Orwell Dev-C++. In 2020, Embarcadero sponsored and took over the original Dev-C++ project to continue development. Embarcadero Dev-C++ adds support for high DPI, updated compiler to include newer version of C++ standard support, and dark mode.
The above Dev-C++ distributions are considered “official”. In addition, after Orwell Dev-C++ stopped updating in 2015, due to teaching needs, a personal developer from China, royqh1979, decided to continue developing his Dev-C++ personal branch, named Red Panda Dev-C++ 2. It integrates smart prompts and a higher version of MinGW64, which is very convenient for domestic personal use and learning.
After the release of Red Panda Dev-C++ 6.7.5, the author used qt5 to develop a brand new Red Panda C++ 3, which can run natively under windows, linux, macos and other systems. The interface of Red Panda C++ is similar to Dev-C++. In addition to providing similar but more complete single-file compilation, debugging, syntax highlighting, search/replace and other functions similar to Dev-C++, it also provides functions such as dark Themes, code intelligence prompts, variable/function renaming, switching/automatic identification of file encoding and other common basic functions of modern IDEs. In addition, Red Panda C++ also has a test set function similar to CP Editor, which can be written by oneself or downloaded from the common OJ competition website to automatically run and test the program.
Tutorial
Common shortcut keys
Document section
- Ctrl + N: Create source code
- Ctrl + O: Open file
- Ctrl + W: close the file
- Ctrl + P: Print file
Formatting section
- Ctrl + /: comment and uncomment
- Tab: Indentation
- Shift + Tab: unindent
Row operation
- Ctrl + E: Copy line
- Ctrl + D: delete line
- Ctrl + Shift + Up: Move up
- Ctrl + Shift + Down: Move down
Jump section
- Ctrl + F: Search
- Ctrl + R: replace
- F3: search next
- Shift + F3: Search previous
- Ctrl + G: Go to the specified line number
- Shift + Ctrl + G: Go to the specified function
- Ctrl + [1 ~ 9]: set bookmark
- Alt + [1 ~ 9]: jump bookmark
Display section
- Ctrl + scroll wheel: Enlarge or reduce font size
- Ctrl + F11: full screen or restore
Run section
- F9: compile only
- F10: run only
- F11: compile and run
- F12: Recompile all
Debugging section
- F2: Go to breakpoint
- F4: set breakpoint or cancel
- F5: Debug and run
- F6: stop
- F7: Step through debugging
Debugging process
- Set compiler configuration to TDM-GCC 4.9.2 64-bit Debug
- Press F4 to set or cancel debug breakpoints
- Place the cursor on a variable and press Alt + A to add a watch variable to the debug window
- Press F5 to start debugging
- Step through debugging by pressing F7 or Alt + N
- Press Alt + S to jump to the next debug breakpoint
- Press F6 to stop debugging
Extension
Add compile options
Click Tools -> Compilation Options, and then select the “Code Generation/Optimization” tab. Here are a few compilation options that I commonly use.
Turn on optimization
Optimize code runtime or footprint.
Select the “Optimization Level (-Ox)” tab in the “Code Generation” sub-tab.
Change language standard
Using new language features or trying to make code compile under old standards.
Select the “Language Standard (-std)” tab in the “Code Generation” subtab.
Show most warnings
Troubleshooting assistant.
Select the “Show most warnings (-Wall)” option tab in the “Code Warnings” sub-tab.
Generate debug information
When the display shows “The project has no debugging information, do you want to open the project debugging option and regenerate?” After clicking, it crashes or you want to use the debugging function, you need to enable this function.
Select the Generate Debug Info tab in the Linker sub-tab.
Compile small trick
Click Tools -> Compile Options, then select the “Compiler” tab, and then introduce several common tricks.
Open Big Stack
Prevent situations such as DFS bursting the system stack.
Add the -Wl,–stack=128000000 command in “Add the following commands to the linker command line”.
This command expands the stack to a size of about 128MB, which can be increased if necessary.
Define macros
It is convenient for local evaluation to use file input and output or for other purposes.
Add the -D[String] command to “Add the following commands to the linker command line”.
Where [String] is changed to the macro name you need.
As shown in the figure, when the compile option is turned on, the following code can be read into data from the test.in file and output in the test.out file.
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
Code formatting
Click Astyle-> Format Current File or press Ctrl + Shift + A for code formatting.
beautification
font
Click Tools -> Editor Options and select the Display tab.
Theme
Click Tools -> Editor Options, then select the “Syntax” tab, you can use the preset theme, or adjust it yourself.
