Hello! It became interesting to learn how AI works in games, it was decided to start with the tic tac toe, for obvious reasons.
This algorithm was immediately invented -
- We find all possible moves (at this step, you can remove those moves that can be obtained from the already existing fields, but you can not do this)
- For every possible move we perform
- If the next move leads to a victory, execute it.
- If not, we calculate in depth all possible outcomes of the game after this turn, remember the ratio of the number of games won to the number of possible (let's call this parameter
prob)
- Select a move with the largest
probvalueprob
The first two points are easy to implement, but further complications arise, most likely due to a lack of understanding of the structure of trees. Could you explain and, preferably, show how to present the game in the form of a tree? How then to get around it, it seems, is understandable, although a comment on this item is also desirable. Language is not so important, but better with ++.
This is the result of this code:
class GameTree { private: vector<GameTree> children; vector<int> probs; Board current; public: GameTree(Board board, int totalP, int currentP, int depth = 0) { for(int i=1; i<totalP+1; i++) // если кто-то уже выиграл, нудно перестать считать if(board.isWonBy(i)) { cout<<"\t\t\t\twon by "<<i<<endl; return; } if(currentP == totalP+1) currentP = 1; cout<<"Depth = "<<depth<<endl; cout<<"Player = "<<currentP<<endl; cout<<"Board: "<< endl; board.print(); getchar(); current = board; vector<Move> avalMoves = current.avalMoves(); for(int i=0; i<avalMoves.size(); i++) { children.push_back( GameTree(current.withMove(avalMoves[i].withPlayer(currentP)), totalP, currentP+1, depth+1)); } } }; class Board { private: int N; int size; int *board; int toN(int x, int y) { return y*N+x; } public: Board(int *prev = NULL, int n = 2) { N = n; size = (int)pow(3, N); board = new int[size]; if(prev == NULL) for(int i = 0; i < size; ++i) board[i] = 0; else for(int i = 0; i < size; ++i) { board[i] = prev[i]; } } bool isWonBy(int p) { for(int i=0; i<3; i++) { if(board[Move(i, 0).toN()] == p && board[Move(i, 1).toN()] == p && board[Move(i, 2).toN()] == p) { return true; } if(board[Move(0, i).toN()] == p && board[Move(1, i).toN()] == p && board[Move(2, i).toN()] == p) { return true; } } if(board[Move(0, 0).toN()] == p && board[Move(1, 1).toN()] == p && board[Move(2, 2).toN()] == p) { return true; } if(board[Move(0, 2).toN()] == p && board[Move(1, 1).toN()] == p && board[Move(2, 0).toN()] == p) { return true; } return false; } vector<Move> avalMoves() { vector<Move> ret; for(int i=0; i<pow(3, N); i++) if(board[i] == 0) { ret.push_back(Move(i)); } return ret; } void applyMove(Move move) { if(board[move.toN()] == 0) board[move.toN()] = move.getPlayer(); } Board withMove(Move move) { Board ret(board, N); ret.applyMove(move); return ret; } void print() { for(int x=0; x<3; x++) { for(int y=0; y<3; y++) { cout<<board[Move(x, y).toN()]<<' '; } cout<<endl; } } }; class Move { private: int player; int x; int y; public: Move(int x_, int y_) { player = -1; x = x_; y = y_; null = false; } Move(int i) { player = -1; x = i%(int)pow(3, 2-1); // TODO 2 сменить на N y = i/(int)pow(3, 2-1); } int setPlayer(int p) { player = p; } int getPlayer() { return player; } Move withPlayer(int i) { Move ret(x, y); ret.setPlayer(i); return ret; } int toN() { return y*2+x; } }; All this is called like this:
int main() { Board b; GameTree(b, 2, 1); return 0; } Conclusion:
Depth = 0 Player = 1 Board: 0 0 0 0 0 0 0 0 0 Depth = 1 Player = 2 Board: 1 0 0 0 0 0 0 0 0 Depth = 2 Player = 1 Board: 1 0 0 2 0 0 0 0 0 Depth = 3 Player = 2 Board: 1 1 0 2 0 0 1 0 0 Depth = 4 Player = 1 Board: 1 1 0 2 0 0 1 0 0 After that, the last state is repeated. Help me please.
