Topic: AITTT (Monte Carlo, minimax, random selection strategy plus programming ideas

Requirements analysis and modeling interface design

Today, I would like to talk about the topic of architecture design with you through TicTacToe, which is also to throw a brick to attract jade. I also hope to iterate my programming level through sharing.

Think about this question: when you get a requirement, do you start writing code right away or do requirements analysis first?

I used words, almost no demand analysis, come up to write code, directly to the later, the maintenance of the code is becoming more and more big, everywhere is copy and paste, oneself also can’t stand, come over as a whole, the efficiency is extremely low, fortunately, I am a lazy people love, this a few times, I started thinking, how to let oneself write less code, At the very least, you can change less code. If a feature is implemented and tested, it is best to leave that part of the code unchanged.

At the time, I just wanted to maintain less historical code, and I never realized that this was the motivation for requirements analysis and architectural design. The first point of architectural design is requirements analysis, distinguishing between stable and changing points of requirements. Then from the model to the interface, and finally the implementation.

So what is a point of stability and a point of change

So, for example, a stable point is something that doesn’t change, like a computer, it has to have CPU, it has to have memory but the input and output devices are a point of change

In our TicTacToe:

Stable point: the board is square, and the squares are square change points: the size of the board is indeterminate, and the size of the squares drawn is indeterminate. Design all the change points as interfaces, parameters, variablesCopy the code

Analyze requirements

Board (Board)

When I saw last week’s work, I wanted to implement tic-tac-toe and gobang together in the initial requirement analysis. They have many similarities.

  1. They all have a Board. The Board is square, which means the width and height are the same, which can be expressed as dimension, and then there are Cells of dimension * dimension on the Board.
  2. Each Piece has only two pieces (PIECE_O | PIECE_X), so each Piece has only three pieces (PIECE_O | PIECE_X | EMPTY). Each Piece is played by selecting one of the EMPTY pieces.
  3. Move and then switch pieces until checkWin to PIECE_O | PIECE_X | DRAW.

These are all stable points. This is the core requirement of a board. That was my original design.

There are also a lot of opinions on demand analysis Guo Huijuan: I usually do demand analysis to understand the input and output

Game Scene (Game)

  1. It’s not enough just to have checkerboard data. The Board class only takes on the business of the Model layer. We can’t play chess with commands where there is only one command line.
  2. In the browser environment, the View layer is natural, which is HTML and CSS. 3. But there is still a role of Controller, listen to the View layer events, and then modify the Model source data, but also through some business events in the Model layer, modify the View display. I abstracted this character into a Game.

Now let’s do a requirements analysis for Game. A Board game should have a Board, and it should know the current state of the game (isRunning). It should also know which piece is currently in play (currentPiece), and it should also know which element (containerEl) to draw the Board (_draw).

Game. Move has a lot more logic than Borad. Move. In the game, the move can be made only after determining whether the game is in progress and whether the position is empty. However, the business of Game. move remains stable, whether it is game.move, which listens to the output of View events, or Game. move, which is called directly from the command line.

With game.move as a base, you can extract the point of change in requirements. Although Game. move is stable, AI strategy is the point of change.

There can be algorithms with smart barriers, there can be many advanced AI algorithms (Monte Carlo, Minmax, etc.), there can be many advanced algorithms.

Does every additional strategy require a move method in Game? This makes Game’s code more and more unmaintainable. Is there a way to stabilize Game’s code?

So let me tell you a little bit about my code design

As long as each policy class provides a calculatePosition (board, piece) method, constraints can be constrained by an interface in other languages. This design can also be described as a combination of polymorphism and inversion of control (IoC).

Each strategy only needs to calculate a position according to the current board and pieces, and call Game.moveByStratepy (Strategy) to move the position according to the calculated position.

Code library: https://github.com/moling3650/TicTacToe

FU½: It’s a little dizzy, so the GAME decides if the GAME is going on, and whose turn is it? Moring: Yes

FU½: And where do the different algorithms settle? Muring: Game is mainly responsible for user interaction. Muring: You can understand it this way

Guo Huijuan: Feel interface, class division is quite clear, thumbs up. I don’t seem to use it in my current business, so I can consciously cultivate it and learn it

For example, class A depends on class B. The common practice is to instantiate class B within class A. If class B is A database or relies on other infrastructure, testing class A must integrate with class B, which is inefficient. You can mock an instance of class B directly to test class A

AI strategy

I’ll go straight to the code for the strategy part.

RandomStrategy (Artificial Retardation)

  1. Gets all empty squares on the board
  2. Pick a chess move at random

MonteCarloStrategy(statistical simulation method)

0. Create a scoreboard that looks exactly like the board 1. Practice the current game several times until the game is won 2. Update the scoreboard according to the results of each practice, the score of the winner position +1, the score of the negative position -1 3. Count up all the positions with the highest odds and pick one at random

** MinimaxStrategy ** 1. Assume that you are in the worst situation 2. Exhaust your efforts to find a slightly better outcome 3. 4. Recursively seek an unbeatable result

As a matter of fact, teacher Winter’s project was a minimax algorithm. I just made some pruning and optimization, such as pruning the opening board score, pruning the winning game, and replacing the checkerboard clone by backstepping. I also wrote a version with log deployment to the website, you can follow the log trace to experience the genius of this algorithm.

The log version preview link http://47.114.59.114:8012/

This is the Monte Carlo strategy

discuss

1. Guo Huijuan: Pruning means not to go down. Can you be more specific about the pruning of winning games and the pruning of chess score?

Guo Huijuan: How did you get this score? Is it the same as I thought? It’s just going through all the possible subcommands. Then count the score situation: play randomly with the current board as a template, until the winner is determined

Topic: AITTT (Monte Carlo, minimax, random selection strategy plus programming ideas) share by: Mo Ling Location: brush topic group

Thank you all!!

Code link: github.com/moling3650/… Link: http://47.114.59.114:8012/