preface

Earlier this year, I attended the geek time advanced training camp, and came into contact with the tic-tac-toe game of man-machine battle. I said THAT I would write a blog to record it. Today, I fill in the hole.

Tic-tac-toe, or three pieces of chess I believe that everyone is not strange, students in the book to draw a “well” word and classmates play chess, or directly in the Chinese with a grid of homework up and down.

Without further ado, let’s take a look at the effect achieved:

How to achieve this is mainly divided into the following parts:

  • Drawing board
  • The user move later
  • Check the outcome
  • Analog trap (one layer)
  • Best choice (recursive)
  • Computer move later

Drawing board

  • useCSS inline-blockimplementation3 * 3layout
  • Defining a one-dimensional arraypatternTo simulate3 * 3Checkerboard, record the situation
    • Array element value definition:0It means that there is no child,1saidOMove later.2saidXMove later
  • render: Traverses a one-dimensional array, dynamically draws the checkerboard according to the values of the array elements
<! DOCTYPEhtml>

<style>
  #board {
    width: 306px;
    margin: 0 auto;
  }

  .cell {
    width: 100px;
    height: 100px;
    color: red;
    display: inline-block;
    border: 1px solid black;
    vertical-align: middle;
    line-height: 100px;
    font-size: 50px;
    text-align: center;
  }
</style>

<! -- You can omit the body tag -->
<div id="board"></div>

<! -- -- -- > static
<script>
  let pattern = [2.0.0.0.1.0.0.0.0];

  function render() {
    const board = document.getElementById("board");
    // Empty the board before drawing
    board.innerHTML = "";

    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        const cellValue = pattern[i * 3 + j];
        const cell = document.createElement("div");

        cell.classList.add("cell");
        cell.innerText = cellValue === 2 ? "X" : cellValue === 1 ? "O" : "";

        board.appendChild(cell);
      }
      board.appendChild(document.createElement("br"));
    }
  }

  render();
</script>
Copy the code

The user move later

  • Defining identification variablescolor, records the value of the element on which the last child was dropped
  • render: Traverses a one-dimensional array and adds a click event to a checker, passing the current checker’s “coordinates” as an argument
  • setCellValue: Defines submethods that handle one-dimensional arrays and identity updates, and checkerboard redraws
<! -- Click -->
<script>
  let pattern = [2.0.0.0.1.0.0.0.0];
  let color = 1;

  function render() {
    // ...
    cell.addEventListener("click".() = > setCellValue(i, j));
    // ...
  }

  function setCellValue(i, j) {
    pattern[i * 3 + j] = color;
    color = 3 - color;
    render();
  }

  render();
</script>
Copy the code

Check the outcome

  • setCellValue: After the user hits, check the outcome of the game, one side wins, the game ends
  • checkWinOrLose: go through the chessboard, check the outcome of three vertical, three horizontal and two oblique in turn
<! -- Click + to determine the outcome -->
<script>
  let pattern = [0.0.0.0.0.0.0.0.0];
  let color = 1;

  function render() {
    / /...
  }

  / / move later
  function setCellValue(i, j) {
    pattern[i * 3 + j] = color;
    render();
    if (checkWinOrLose(pattern, color)) {
      alert(`${color === 2 ? "X" : color === 1 ? "O" : ""}is winner! `);
      // Game over
      return;
    }
    color = 3 - color;
  }

  // Check the result
  function checkWinOrLose(pattern, color) {
    let win = false;

    / / three horizontal
    for (let i = 0; i < 3; i++) {
      win = true;
      for (let j = 0; j < 3; j++) {
        if (pattern[i * 3+ j] ! == color) { win =false; }}if (win) {
        returnwin; }}/ / three longitudinal
    for (let i = 0; i < 3; i++) {
      win = true;
      for (let j = 0; j < 3; j++) {
        if (pattern[j * 3+ i] ! == color) { win =false; }}if (win) {
        returnwin; }}/ / two oblique
    // forward slash /
    {
      win = true;
      for (let i = 0; i < 3; i++) {
        if (pattern[i * 3 + 2- i] ! == color) { win =false; }}if (win) {
        returnwin; }}// backslash \
    {
      win = true;
      for (let i = 0; i < 3; i++) {
        if (pattern[i * 3+ i] ! == color) { win =false; }}if (win) {
        returnwin; }}return false;
  }

  render();
</script>
Copy the code

Analog trap (one layer)

  • setCellValue: After either side gets the shot, simulate the shot (one layer) and predict the winner
    • predictWin: traverses the checkerboard, copies the checkerboard array, simulates the squares to be placed, and obtains the winning positions
  • clone: Copies a one-dimensional array
<script>
  / /...
  function render() {
    / /...
  }

  / / move later
  function setCellValue(i, j) {
    // ...
    if (predictWin(pattern, color)) {
      alert(`${color === 2 ? "X" : color === 1 ? "O" : ""}will win! `); }}// Check the result
  function checkWinOrLose(pattern, color) {
    / /...
  }

  // Create a new layer.
  function predictWin(pattern, color) {
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        // Skip the place where the child is already placed
        if (pattern[i * 3 + j]) {
          continue;
        }
        let temp = clone(pattern);
        temp[i * 3 + j] = color;
        if (checkWinOrLose(temp, color)) {
          return[i, j]; }}}return null;
  }

  function clone(value) {
    return Object.create(value);
  }

  render();
</script>
Copy the code

Best choice (recursive)

  • setCellValue: After either side has won, look for the best option (recursively) and predict the situation
    • bestChoice:
      • Execution process:
        • callpredictWinMethod simulates the drop (layer 1), terminates execution if the winning drop position is returned, and returns the result
        • Traversing the chessboard, we (color) after the simulated game, the opponent ((3 - color) Angle, substitute parametersRecursive calls bestChoiceMethod, get the best result of the counterparty
        • The best result of the opposing side is negative (-r), which is our worst result, and the best place for us is updated after comparison (point) and results (result) until victory (result = 1), jump out of traversal
        • The result is returned
      • Return value definition:
        • Color: square
        • -Penny: I’m at the point.
        • The result:2 -Means not started,- 1Said to lose,0Represents a game of peace,1Said win
<script>
  / /...
  function render() {
    / /...
  }
  / / move later
  function setCellValue(i, j) {
    / /...
    let choice = bestChoice(pattern, color);
    console.log(
      `${
        choice.color === 2 ? "X" : choice.color == 1 ? "O" : ""
      } best choice: point=The ${JSON.stringify(choice.point)}, result=${ choice.result }`
    );
  }
  // Check the result
  function checkWinOrLose(pattern, color) {
    / /...
  }
  // Create a new layer.
  function predictWin(pattern, color) {
    / /...
  }

  // Best choice (recursive)
  function bestChoice(pattern, color) {
    let point = predictWin(pattern, color);
    if (point) {
      return {
        color: color,
        point: point,
        result: 1}; }// Start result
    let result = -2;
    outer: for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        // Skip the place where the child is already placed
        if (pattern[i * 3 + j]) {
          continue;
        }
        let temp = clone(pattern);
        temp[i * 3 + j] = color;
        // Transpose to get our "worst result" (-r) based on the "best result" of the "counterparty" in its current situation.
        let r = bestChoice(temp, 3 - color).result;
        // Update the location and result after the comparison
        if (-r >= result) {
          result = -r;
          point = [i, j];
        }
        / / the pruning
        if (result === 1) {
          breakouter; }}}return {
      color: color,
      point: point,
      result: point ? result : 0}; }/ /...

  render();
</script>
Copy the code

Computer move later

  • userSetCellValue: After the user clicks, the computer clicks
    • computerSetCellValue: callbestChoiceGet the best choice (including the drop location and the result), and drop
<script>
  let pattern = [0.0.0.0.1.0.0.0.0];
  let color = 2;

  function render() {
    // ...
    cell.addEventListener("click".() = > userSetCellValue(i, j));
    // ...
  }

  // The user drops the child
  function userSetCellValue(i, j) {
    // ...
    computerSetCellValue();
  }

  // The computer drops
  function computerSetCellValue() {
    let choice = bestChoice(pattern, color);
    if (choice.point) {
      pattern[choice.point[0] * 3 + choice.point[1]] = color;
      render();
      if (checkWinOrLose(pattern, color)) {
        alert(`${color === 2 ? "X" : color === 1 ? "O" : ""}is winner! `);
        // Game over
        return;
      }
      color = 3- color; }}// Check the result
  function checkWinOrLose(pattern, color) {
    / /...
  }
  // Create a new layer.
  function predictWin(pattern, color) {
    / /...
  }
  // Best choice (recursive)
  function bestChoice(pattern, color) {
    / /...
  }
  / /...

  render();
</script>
Copy the code

conclusion

To review, in this man-machine tic-tac-toe game, the main logic of machine operation is in bestChoice – bestChoice method. Based on traversal and recursion, the machine simulates the machine making a move, and then simulates the human making a move, and the cycle repeats until the bestChoice – bestChoice is obtained.

To put it bluntly, it is to use the computing power of the computer to enumerate all the possibilities and find the optimal solution within the rules.

Tic-tac-toe is not enough computer power to plug the teeth, backgammon with the exhaustive method seems to have a little card, to go seems to be unable to use exhaustive method to deal with all situations.

Welcome to like and comment, the main part of the game is available, but there are still many imperfect places, online link:

Codepen. IO/LSNSH – the – b…