Hello, my name is 💎 three diamonds from Tech Galaxy.

Here’s a fun programming exercise that many students think of as algorithmic. But often in the process of programming, when we want to achieve some logic or function, it is really necessary to use algorithms. But I think what Teacher Winter said is quite right.

Part of the programming exercise is closely related to algorithms and data structures, but part is more language-specific. We both need to know how to write the algorithm, and we need to integrate it with the language, how to express it better in our language. But the core of programming practice is improving our programming skills.

TicTacToe is a very famous little game, which is called TicTacToe abroad, but in China, we call it “three sons” or “one dragon”.

If we are going to implement this little game, we first need to understand the rules of the game. If we don’t know the rules of the game, we can’t express it in code language.

The one rule

Board: 3 x 3 squares
Both sides hold ⭕️ and ❌ pieces respectively
The two sides alternate with each other
The first to tie three straight lines wins
This line can be “horizontal”, “vertical” and “oblique” respectively

“Two” code implementation

“1” creates the board

The game is based on having a board on which you can put pieces, or in our program, a place to store data, keeping track of where each piece is placed.

Here we can store it with a two-dimensional number:

let parttern = [
  [2.0.0],
  [0.1.0],
  [0.0.0]]console.log(pattern)
Copy the code

0Represents the position where no pieces are stored on the board
1Represents a piece with ⭕️ on its face
2Represents a piece with ❌ on its face

After we have the data of the board, because this is a game that can be played by users, we of course need to show it in the browser. So here we need to add HTML and CSS.

<style>
      * {
        box-sizing: border-box;
        background: #0f0e18;
      }
      .container {
        margin: 3rem;
        display: flex;
        justify-content: center;
        align-items: center;
        flex-direction: column;
      }
      h1 {
        color: #ea4dc5;
      }
      #board {
        width: 300px;
        height: 300px;
        display: flex;
        flex-wrap: wrap;
      }
      .cell {
        width: 100px;
        height: 100px;
        background: #2d2f42;
        border: 1px solid #0f0e18;
        cursor: pointer;
        display: flex;
        justify-content: center;
        align-items: center;
        transition: background 500ms ease;
      }
      .cell:hover {
        background: # 454966;
      }
      .cell .iconfont {
        background: transparent;
        width: 100%;
        height: 100%;
        font-size: 50px;
        line-height: 100px;
        text-align: center;
        vertical-align: middle;
      }
      .blue {
        color: #7ceefc;
      }
      .purple {
        color: #ea4dc5;
      }
      #tips p {
        color: #dddddd;
      }
</style>

<div class="container">
  <h1>Tic-tac-toe Simulator</h1>  <! - the title -- -- >
  <div id="board"></div>  <! -- -- -- > board
  <div id="tips"></div> <! --> < span style = "max-width: 100%; clear: both; min-height: 1em;
</div>
Copy the code

Once we’ve done the HTML and CSS above, we’ll see that the board is an empty DIV, and the grid hasn’t been added yet.

Here we need to create the checkerboard according to the data in our pattern. So we need to add JavaScript to create the squares and pieces on our board based on our checkerboard data.

/ / board
let pattern = [
  [2.0.0],
  [0.1.0],
  [0.0.0]].let chess = 1;

/** Render board */
function build() {
  // Get the checkerboard element
  let board = document.getElementById('board');

  board.innerHTML = ' ';

  // Fill the checkerboard
  for (let y = 0; y < 3; y++) {
    for (let x = 0; x < 3; x++) {
      let cell = document.createElement('div');
      cell.classList.add('cell');

      // Create a circle piece
      let circle = document.createElement('i');
      circle.classList.add('iconfont'.'icon-circle'.'blue');
      // Create a fork chess piece
      let cross = document.createElement('i');
      cross.classList.add('iconfont'.'icon-cross'.'purple');
      // Create an empty chess piece
      let empty = document.createElement('i');

      let chessIcon = pattern[y][x] == 2 ? cross : pattern[y][x] == 1? circle : empty; cell.appendChild(chessIcon); board.appendChild(cell); }}}Copy the code

To create this board we used the following ideas:

Let’s start by looping through our two-dimensional arraypattern
A double loop is the same thing as going from top to bottom, left to right through the board
We need to put pieces into the board at the same time as we loop the board
First we create a checkerboard griddivElement and give it a class namecell
If we meet1At ⭕️cellinside
If we meet2When put ❌ tocellinside
If we meet0Put an “empty” intocellinside
So I’ve given you a chess piece hereiElement, and its class uses iconfont
Of course if we can use itemojiInstead of this part, just give itcellElement adds text (for example:Cell. The innerText = '⭕ ️')
Finally, thecellAdd to the boardboardIt can be

Here I use the “Alibaba” iconfont code, of course, we can also directly use emoji. For those of you practicing with my essay, you can also use the iconfont I’m using. Here I have attached the iconfont address I’m using:

<link rel="stylesheet" href="//at.alicdn.com/t/font_2079768_2oql7pr49rm.css" />
Copy the code

This is what it looks like:

“2” drops the piece

We already have a 3 x 3 board, and that’s the way to do it. What we want to achieve is that when the user clicks on a grid, the pieces fall into the corresponding position. It does not take effect if there are already pieces in the position.

/** ** To place a piece on the board ** - first give the current piece number to the element in the current x, Y position **@param {Number} X x *@param {Number} Y y * /
function move(x, y) {
  if (pattern[y][x]) return;

  pattern[y][x] = chess;

  chess = 3 - chess;

  build();
}
Copy the code

The logic of this code is simple:

If the currentx.yIf the position has a chess piece, it must not be 0. If it is 0, it can directly return, deduce this method
If a piece can be dropped, the current position is assigned to the piece’s code1Is ⭕ ️,2Is ❌
Here we use the equivalence of 1 and 2, 3−1=23-1=23−1=2, and 3−2=13-2=13−2=1
So the last player’s piece is1. $3- Current piece = next player’s piece$ , that is,2
Finally, we call our checkerboard construction methodbuildRebuild the board

This method is written, but we find that we didn’t call it at all, so clicking on the board has no effect.

So here we’re going to add a “click” event to each grid as we build the checkerboard.

/** Render board */
function build() {
  / /... This part of the code is omitted

  let chessIcon = pattern[y][x] == 2 ? cross : pattern[y][x] == 1 ? circle : empty;
  cell.appendChild(chessIcon);
  cell.addEventListener('click'.() = > move(x, y)); // add a listening event here
  board.appendChild(cell);
  
 / /... This part of the code is omitted
}
Copy the code

So our board can click on the grid to put down the pieces!

“3” judges the winner

Our game is ready to play at this point, but a game can’t have an ending, so we need to make it winnable.

When we understand the game of TicTacToe, we know that there are several conditions to win the game, that is, one side of the chess pieces in the “horizontal”, “vertical”, “oblique” line can win the game. So here we need to test these three cases separately.

Through analysis, we have four cases:

There are three pieces in the vertical row that are all the same
There are three pieces that are the same
Is oblique line”/“Three pieces are the same
The oblique line”\“Three pieces are the same

So let’s write a check() method to check:

/** * Checks all the pieces in the board ** - finds out if any pieces have already won * - three pieces in a row are considered winning **@param {Array} Pattern Indicates the board data *@param {Number} Chess chess number *@return {Boolean}* /
function check(pattern, chess) {
  // Check all rows first
  for (let i = 0; i < 3; i++) {
    let win = true;
    for (let j = 0; j < 3; j++) {
      if(pattern[i][j] ! == chess) win =false;
    }
    if (win) return true;
  }

  // Check vertical rows
  for (let i = 0; i < 3; i++) {
    let win = true;
    for (let j = 0; j < 3; j++) {
      if(pattern[j][i] ! == chess) win =false;
    }
    if (win) return true;
  }

  // Check crossed rows
  // Use curly braces "{}" to make the win variable
  // becomes a scoped variable independent of outside variables
  // win variable influence

  // "backline \ check"
  {
    let win = true;
    for (let j = 0; j < 3; j++) {
      if(pattern[j][j] ! == chess) win =false;
    }
    if (win) return true;
  }

  // "check"
  {
    let win = true;
    for (let j = 0; j < 3; j++) {
      if (pattern[j][2- j] ! == chess) win =false;
    }
    if (win) return true;
  }

  return false;
}
Copy the code

With this method of winning and losing, we can put it in one place and let it detect the winner of the game.

We can put this detection in when the user drops a piece, before the piece type is reversed and reconstructed, to detect whether the current player has won.

/** global variables -- if there is a winner */
let hasWinner = false

/** ** Puts a piece on the board ** - first gives the current piece number to the element in the current X, Y position * - checks if a piece has already won **@param {Number} X x *@param {Number} Y y * /
function move(x, y) {
  if (hasWinner || pattern[y][x]) return;

  pattern[y][x] = chess;

  // There is a win/loss judgment
  if (check(pattern, chess);) {
    tips(chess == 2 ? '❌ is the winner! ' : '⭕ ️ is the winner! ');
  }

  chess = 3 - chess;

  build();
}
Copy the code

Here we need to add a hasWinner global variable, this is used to record whether the game has a winner, if there is a winner, the user can not drop pieces. So, at the beginning of the move method, if there is a winner, just return and exit the method.

We can determine the winner by adding this code, but we still need to tell the user who won on the page to be perfect. So here we add a method to prompt insertion:

/** * Insert prompt *@param {String} Message prompts copywriting */
function tips(message) {
  let tips = document.getElementById('tips');

  tips.innerHTML = ' ';

  let text = document.createElement('p');
  text.innerText = message;
  tips.appendChild(text);
}
Copy the code

The final effect is as follows:

“Three” to achieve AI

Now we have a “TicTacToe” game to play. But in this day and age, how can an application be a good product without any AI support? So let’s add some AI features to our game.

“1” predicts whether the next step will be won

Let’s start by sorting out this requirement so that after a player loses, we can detect whether the next player in the game is about to win.

To determine whether the next player is about to win, we need to simulate where the next player will drop the pieces, which in our case, means placing the pieces in sequence on the empty squares of the board and determining whether the next player will win the game.

Implementation idea:

Our timing is to start simulating all possible positions for the next player after the previous player drops a piece
At this point we can loop the squares on the current board, simulating the result of the next player placing a piece on each of the non-empty squares
If there is a grid into the chess pieces will win, then the next player can win!

What we should note here is that we need to simulate the result of the next player moving every space in the current situation. At this time, if we use the original pattern data to simulate, the position of the chess pieces in the current game will be affected. So we need to constantly clone the chessboard data to simulate. This will not affect the current board data.

Implementation prediction method: willWin()

/** * Check if the current piece is about to win ** - loop through the board * - skip over all the squares that already have pieces * - Clone the board data (because we want the next piece to go through all the empty places) * see if it will win, if it is simulated directly on the original board, Dirty data) * - let the current piece simulate the current loop to the empty seat * - then check if it wins * *@param {Array} Pattern Indicates the board data *@param {Number} Chess chess number *@return {boolean}* /
function willWin(pattern, chess) {
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (pattern[i][j]) continue;
      let tmp = clone(pattern);
      tmp[i][j] = chess;
      if (check(tmp, chess)) {
        return true; }}}return false;
}
Copy the code

Clone method: Clone ()

/** * Clone checkerboard data *@param {Array} Pattern Indicates the board data *@return {Array} Clone checkerboard data */
function clone(pattern) {
  return JSON.parse(JSON.stringify(pattern));
}
Copy the code

Finally, we need to move after the previous player, and then add a win/lose prediction method: “Modify our move() method.”

/** ** Puts a piece on the board ** - first gives the current piece number to the element in the current X, Y position * - checks if any pieces have won * - reverses the last piece number and re-renders the board **@param {Number} X x *@param {Number} Y y * /
function move(x, y) {
  if (hasWinner || pattern[y][x]) return;

  pattern[y][x] = chess;

  hasWinner = check(pattern, chess);
  if (hasWinner) {
    tips(chess == 2 ? '❌ is the winner! ' : '⭕ ️ is the winner! ');
  }

  chess = 3 - chess;

  build();

  if (hasWinner) return;

  // Add a win/lose prediction
  if (willWin(pattern, chess)) {
    tips(chess == 2 ? '❌ is going to win! ' : '⭕️ is going to win! '); }}Copy the code

If (hasWinner) return; This is so that if a player has already won this move, we don’t need to predict the winner and we can just go back.

In this way, we have achieved an intelligent win-loss prediction function, and the final result is shown in the picture below:

“2” predicts the outcome of the game

The AI we implemented above can only predict whether the next move will be won or not. But it doesn’t give us a sense of who’s going to win in this situation.

Let’s implement a more intelligent AI here, where the program, after each player has placed a piece, decides who will win, based on the current piece situation, or whether the result is a draw.

Implementation idea:

The first step is to define a label for the end result of our game
As a result,- 1Is that you’re going to lose
As a result,0That’s what you end up with
As a result,1It’s going to win
Here the winners and losers are positive and negative, and this is designed to make us better judge the winners and losers
It can also be understood that if the opponent’s chess piece is placed in a position to win, then our result will be lost. This result is just the opposite, so we use positive and negative marks to express it is very convenient for us to judge with the program
Using the logic we described above, we can lock in a way that if we find the position of the opponent’s piece to lose, we will win, and if we find the position of the opponent’s piece to win, we will lose
Using this logic we can use a recursive method to simulate the moves of two players in a loop, and judge the results of the moves, and search in depth until we find a winner
This recursion eventually simulates all the situations in which the two players play the game and find a winning situation, ending the loop. This is also called “winning and losing”. Winning is as good as it gets, we don’t need to simulate every situation, we’ve found the best situation.
Of course, in other board games, there can be many victories, there can be wins and losses, and there can be wins and losses quickly. But in TicTacToe, there is no need to consider these factors.

Having said that, let’s look at how the code is implemented. Let’s first implement a method to find the best result bestChoice:

/** ** find the best result ** - the result is -1 is the end will lose * - the result is 1 is the end will win * - the result is 0 is the end and **@param {Array} Pattern Indicates the board data *@param {Number} Chess chess numbers */
function bestChoice(pattern, chess) {
  // Define a winning position
  let point;

  // As things stand, we are on the verge of winning
  // We can return the result directly
  if ((point = willWin(pattern, chess))) {
    return {
      point: point,
      result: 1}; }// Define a result where -2 is less than -1, 0, 1
  // So it's a worst-case scenario, and we need to start with the worst-case scenario
  // The higher the number gets, the closer we are to winning
  let result = -2;
  point = null;
  outer: for (let y = 0; y < 3; y++) {
    for (let x = 0; x < 3; x++) {
      // Skip all the places where there are already pieces (because we can't put our pieces there anymore)
      if (pattern[y][x]) continue;

      // Clone the current checkerboard data to make a prediction
      let tmp = clone(pattern);

      // Simulate the position of our chess piece
      tmp[y][x]= chess;

      // Find the opponent's best result after we play this piece
      let opp = bestChoice(tmp, 3 - chess);

      // Record the best result
      if (-opp.result >= result) {
        result = -opp.result;
        point = [x, y];
      }

      if (result === 1) breakouter; }}Copy the code

What does this code do? In fact, our program is playing A game of its own, with team A finding A position that they can win, and then team B finding A position that they can win, until there is A result, either neither side can win, that is A draw, or one side wins.

We’ll notice that bestChoice returns an object, and one property is result, which is the predicted outcome of the game. The other is the point, which is where the current player can go and where the best results can be achieved. This will be used when we implement the last AI feature. In this step, we only need to use the result attribute to make a judgment and output the winner hint.

With this more advanced predictive AI, we can replace our willWin().

Here we revamp our move() method:

/** ** Puts a piece on the board ** - first gives the current piece number to the element in the current X, Y position * - checks if any pieces have won * - reverses the last piece number and re-renders the board **@param {Number} X x *@param {Number} Y y * /
function userMove(x, y) {
  if (hasWinner || pattern[y][x]) return;

  pattern[y][x] = chess;

  if ((hasWinner = check(pattern, chess))) {
    tips(chess == 2 ? '❌ is the winner! ' : '⭕ ️ is the winner! ');
  }

  chess = 3 - chess;

  build();

  if (hasWinner) return;

  let result = bestChoice(pattern, chess).result;
  let chessMark = chess == 2 ? '❌ : '⭕ ️';
  tips(
    result == -1
      ? `${chessMark}is going to loss! `
      : result == 0
      ? `This game is going to draw! `
      : `${chessMark}is going to win! `
  );
}
Copy the code

The result is this:

Of course, this prediction is to predict the best outcome, and we assume that both players are excellent and that each move is in the best position. But if the player makes a mistake, it is possible to turn the game around!

“3” joins computer players

The AI we’ve implemented in the past is enough to make us a very smart AI computer player.

In the last step, when we implemented bestChoice() method, the attribute returned by this method has a point attribute, which is actually the best location of the player. We just need to let the program automatically drop to this location, and we have completed the function of computer player.

Implementation idea:

After the last player has scored, we can call our computer player scoring method
usebestChoiceFind the subposition of the best result
Put a computer player’s piece in the best place
Finally, continue to predict the end of the game

It’s really that simple. Let’s see how the code works:

Here we need to change the move() method to userMove() and create a computerMove().

/** ** Puts a piece on the board ** - first gives the current piece number to the element in the current X, Y position * - checks if any pieces have won * - reverses the last piece number and re-renders the board **@param {Number} X x *@param {Number} Y y * /
function userMove(x, y) {
  if (hasWinner || pattern[y][x]) return;

  pattern[y][x] = chess;

  if ((hasWinner = check(pattern, chess))) {
    tips(chess == 2 ? '❌ is the winner! ' : '⭕ ️ is the winner! ');
  }

  chess = 3 - chess;

  build();

  if (hasWinner) return;

  computerMove();
}

/** the computer automatically moves the pieces */
function computerMove() {
  let choice = bestChoice(pattern, chess);

  if (choice.point) pattern[choice.point[1]][ choice.point[0]] = chess;

  if ((hasWinner = check(pattern, chess))) {
    tips(chess == 2 ? '❌ is the winner! ' : '⭕ ️ is the winner! ');
  }

  chess = 3 - chess;
  build();

  if (hasWinner) return;

  let result = bestChoice(pattern, chess).result;
  let chessMark = chess == 2 ? '❌ : '⭕ ️';
  tips(
    result == -1
      ? `${chessMark}is going to loss! `
      : result == 0
      ? `This game is going to draw! `
      : `${chessMark}is going to win! `
  );
}
Copy the code

And that’s how we got computer gamers, so a single guy can play TicTacToe. 😂 😂 😂

Just kidding, maybe you’ll find someone in your life! Refueling oh! 💪

“Four” optimization

At this point, we have completed a “TicTacToe” game. After implementing a feature, we all ask ourselves the question, is there anything about the program that can be improved?

In our code example above, there is actually one area that can be optimized, and that is our checkerboard data.

In the example, our checkerboard data uses a two-dimensional array, so we need to use JSON conversion to clone, which requires a lot of memory space.

If we transform the checkerboard data into a one-dimensional array, we can clone it using JavaScript object.create (Pattern). This method creates a new object and uses the existing object to provide the __proto__ of the newly created object, thus saving a lot of memory. Because we used prototype cloning, not the whole object cloning.

First we transform the checkerboard data:

/ / board
let pattern = [
  0.0.0.0.0.0.0.0.0
];
Copy the code

Now we have a one-digit board, so how do we wrap lines?

The number of rows * 3 + the position of the pointer to the current row. Of course, the number of rows starts at 0 in the array.

So here’s the phenomenon:

[

0 times 3 plus 1, 0 times 3 plus 2, 0 times 3 plus 3,

(1 * 3 + 1), (1 * 3 + 2), (1 * 3 + 3),

(2 times 3 plus 1), (2 times 3 plus 2), (2 times 3 plus 3),

]

The resulting position looks like this:

[

1, 2, 3,

4, 5, 6,

7, 8, 9

]

Does that help us find our nine squares?

Pattern [y][x] = pattern[y * 3 + x]

Finally, we can modify our clone() method:

/** * Clone checkerboard data *@param {Array} Pattern Indicates the board data *@return {Array} Clone checkerboard data */
function clone(pattern) {
  return Object.create(pattern);
}
Copy the code

“Final” summary

The whole point of this TicTacToe exercise is abstract thinking. How do we abstract the complex logic of a game step by step into the code of our program, through if and else judgment, and add iteration loop to realize our requirements and functions. In fact, this process is not a simple exercise of algorithms and mathematics, but more programming ability.

Here I have to sigh again, teacher Qin Chao often said “five poison god palm”. All learning and skills do not depend on how talented we are, but more on whether we have repeated practice. Only the knowledge and skills that have been honed countless times will become our internal forces.

I’m Three diamonds from Tech Galaxy: “Learning is to grow, growing is not to regress. Persistence can succeed, failure is just because there is no persistence. Come on, students! See you next time!”

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Using JavaScript to implement a TicTacToe game – programming training

The one rule

“Two” code implementation

“1” creates the board

“2” drops the piece

“3” judges the winner

“Three” to achieve AI

“1” predicts whether the next step will be won

“2” predicts the outcome of the game

“3” joins computer players

“Four” optimization

“Final” summary

Using JavaScript to implement a TicTacToe game – programming training

The one rule

“Two” code implementation

“1” creates the board

“2” drops the piece

“3” judges the winner

“Three” to achieve AI

“1” predicts whether the next step will be won

“2” predicts the outcome of the game

“3” joins computer players

“Four” optimization

“Final” summary

Related Posts

Wechat H5 webpage development process

2020 Latest React Hooks+TS project best practices

PromiseA+ specifications/principles and implementations