TicTacToe solver in JavaScript

Question

I come more from a frontend background and have been reading up on more backend approaches and algorithms while solving a TicTacToe grid to see if there are any wins normally, I'd probably use something like this

for (let i = 0; i < rows; i++) {
    if (arr[i][0] === arr[i][1] && arr[i][0] === arr[i][2]) {

but with what I've been studying, I thought it'd be better to use a map and iterate through them instead

'use strict';

const board = [
  ['x','x','x'],
  ['x','o','o'],
  ['x','x','x']
]

const matches = [
  [1,4,7],
  [2,5,8],
  [3,6,9],
  [1,2,3],
  [4,5,6],
  [7,8,9],
  [1,5,9],
  [3,5,7]
]

const solver = (board, matches) => {
  // build map
  let counter = 1;
  const map = {};
  
  // convert array to object
  for (let row of board) {
    for (let char of row) {
      map[counter] = char;
      counter++;
    }
  }

  for (let match of matches) {
    // create a new array with the values
    const arr = [...map[match[0]],map[match[1]],map[match[2]]];
    // check for duplicates
    const arr2 = [...new Set(arr)].join("");
    // console log if length is 1
    if (arr2.length === 1) console.log(`match found at set: ${match}`)
  }
}

solver(board, matches)

Is this efficient? Is there a better way of doing this?

It looks a lot cleaner than

if (arr[i][0] === arr[i][1] && arr[i][0] === arr[i][2])

for sure, but then again, that itself could have probably been designed more efficiently.

Is there a better way to generate the coordinates dynamically?

mpasko256 · Accepted Answer · 2018-10-22 13:22:44Z

you can simplify this block a little:

for (let row of board) {
    for (let char of row) {
         map[counter] = char;
         counter++;
    }
}

into:

const map = board.flat();

You can generate matches pseudo-automatically which simultaneously improve readability

function generateMatches() {
     function simpleRange(upTo) {
          return new Array(upTo).fill(true).map((_, index) => index);
     }

     function customRange(start, step, length) {
          return simpleRange(length).map(index => start + index * step);
     }

     function horizontalRow(top) {
          return customRange(3 * top, 1, 3);
     }

     function verticalRow(left) {
          return customRange(left, 3, 3);
     }

     function progressingDiagonal() {
          return customRange(0, 4, 3);
     }

     function regressingDiagonal() {
          return customRange(2, 2, 3);
     }

     const matches = [];
     for (let top = 0; top < 3; ++top) {
          matches.push(horizontalRow(top));
     }
     for (let left = 0; left < 3; ++left) {
          matches.push(verticalRow(left));
     }
     matches.push(progressingDiagonal());
     matches.push(regressingDiagonal());
     return matches;
}

Warning! I assumed starting at 0 index

Don't use console.log(...); in solve function. Try to return list of matches instead and use user interface API outside of it. It will allow you to write some automatic (for instance unit) tests for your code (using Motcha, Jasmine, etc... depending on your target technology)
General advices:
- Use better names for variables: map -> flatBoard, arr -> row, arr2 -> reducedRow
- Split your code into smaller functions for each step, for instance:
```
const arr2 = [...new Set(arr)].join("");
```
  into:
```
function reduceRow(array) {
     return [...new Set(array)].join("");
}
const reducedRow = reduceRow(row);
```
Your original question is about performance. Let just start it now:
- IMHO you don't need to convert Set into array into string to test its size. Use something like this instead:
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/size
```
function rowDiversity(array) {
     return new Set(array).size;
}
const rowDiversity = rowDiversity(row);
```
- Not sure if destructuring operator is needed at all at previous line too (most likely its performance impact is already neutral) But I would write this instead anyway:
```
function fetchRow(flattenBoard, match) {
     return match.map(index => flattenBoard[index]);
}
const row = fetchRow(flattenBoard, match);
```

Community · Accepted Answer · 2020-06-10 13:24:26Z

Use loops

The game setup is not really conducive to optimization. Tic Tac Toe does not require a board, only each player's moves matter, which makes the game logic much simpler.

Your code

Anyways to your code.

Don't be shy of using standard loops to solve problems. To me it looks like you are finding ways to avoid the straight forward solution of iterating all the match arrays, checking for a match on each.

You are also offsetting the match indexes by 1, start at 0 to match the board array indexing.

Use an array rather than an object for map.

Also storing the board as a 2D array seams a bit odd. You need to convert it to a flat array, why not store it as such in the first place. Indexing from a 2D coordinate x,y to a flat index is quick, boardFlat[x + y * 3]

'use strict';

const board = // as a string for the example  but could be a 2D array
  "xxx"+
  "xoo"+
  "xxx";

const matches = [[0,3,6],[1,4,7],[2,5,8],[0,1,2],[3,4,5],[6,7,8],[0,4,8][2,4,6]];

const solver = (board, matches) => {
  const counts = {x : 0, o : 0};
  var foundMatch;
  for (const match of matches) {
    counts.x = 0;
    counts.o = 0;
    for (const index of match) {
      const char = board[index];
      if (counts[char] !== undefined) {
        if (counts[char] === 2) { // pre-empt the 3
          foundMatch = match;
          break;
        }
        counts[char] += 1;
        if (!counts.x && !counts.o) { break }
      } else { break }
    }
    if(foundMatch){
      console.log(`Match found at set: ${foundMatch}`);
      return;
    }
  }
  console.log(`No match found.`);
}

solver(board, matches)

Only moves matter.

For TicTacToe the general solutions I see use the 2D array to hold the board as a sort of mirror of the game state. But the reality is that you need only store each players moves. You build the displayed board from the player moves.

Eliminating the board make the rest of the game logic much simpler. Checking for wins, draw, valid positions, blocking moves, winning moves only relate to player's current moves.

To simplify it even further, all moves can be represented as a single number using the first 9 bits to represent the 9 possible moves. The you need only do bit logic (player.moves & wins[0] === wins[0]) will be true if the player has the top row (see example)

Example

The example was going to be for another question but I never posted (Because its not finished), so with a slight mod I add it here as purely an example of moves only and bitwise logic to play the game. Its CPU V CPU only and is dumb, random moves unless there is a need to block, or a winning move.

Update Quite day so added human player.

// Wait till all code has been run befor starting
setTimeout(()=>game.state = game.states.start,0);
const options = {
    startPause : 2000,
    statePause : 1000,
    text : {
        start: `Tic Tac Toe` ,
        win : "## wins!", // ## is replaced with player name
        draw : "It's a draw.",
        turn : "Player ##'s turn", // ## is replaced with player name
        moves : {
            block : "blocking move",
            win : "winning move",
            random : "move",
        },
        playerA : "CPU X",
        playerB : "CPU O",
    }
}

/*===================================================================*/
/* Game rules in logic form */
const ticTacToe = {
    layout : "876543210",
    get positions() { return  [1,2,4,8,16,32,64,128,256] },
    wins : [7,56,448,273,84,292,146,73],
    moveStr(move) { return " @ " + (3-(Math.log2(move) % 3)) + "," + (3-(Math.log2(move)/3 | 0)) }, 
    isWin(moves) { return ticTacToe.wins.some(win => (moves & win) === win ) },    
}

/*===================================================================*/
/* Manages players and their turns  */

const player = (name, as) => ({name, as, moves : 0, toString() { return this.name } });
const players = {
    playing : [player(options.text.playerA, "X"), player(options.text.playerB, "O")],
    turn : 0,
    get next() { return this.playing[(++this.turn) % 2] },
    get current() { return this.playing[this.turn % 2] },
    get opponant() { return this.playing[(this.turn + 1) % 2] },
    reset() { 
        this.playing[0].moves = 0;
        this.playing[1].moves = 0;
        this.turn = Math.random() * 2 | 0;
    },
}

/*===================================================================*/
/* handles board related stuff */
const board = {
    reset() { board.moves = ticTacToe.positions },
    get full() { return board.moves.length === 0 },
    get randomMove() { return board.moves.splice(Math.random() * board.moves.length | 0, 1)[0] },
    show(players) {
        const p1 = players.playing[0], p2 = players.playing[1], m1 = p1.moves, m2 = p2.moves
        return ticTacToe.layout.replace(/[0-9]/g, i => m1 & (1 << i) ? p1.as : m2 & (1 << i) ? p2.as : ".");
    },
    winningMove(moves){
        var index = -1;
        ticTacToe.wins.some(win =>(index = board.moves.findIndex(move => ((moves | move) & win) === win)) > -1);
        if(index > -1) { return board.moves.splice(index,1)[0] }
        return -1;
    },    
}
/*===================================================================*/
/* Plays the game */
const game = {
    states : { start: 1, nextMove: 2, win: 3, draw: 4, humansTurn: 5, waitForNext: 6},
    set humanPlaying(val) {
        this.humanFoe = true;
        board.reset(); 
        players.playing[0].name = "Man X";
        players.playing[0].isHuman = true;
        log("board", board.show(players));
    },
    set state(state) {
        clearTimeout(this.timerHdl);
        var next,time = options.statePause;
        switch(state){
            case game.states.humansTurn: 
                time = 100000;
                next = game.states.humansTurn;
                break;
            case game.states.waitForNext:    
                next = game.states.nextMove;
                time = options.startPause / 3;
                break;
            case game.states.nextMove:   
                next = game.playTurn();        
                break;                
            case game.states.start:
                log("status", options.text.start);
                players.reset()
                board.reset();                
                next = game.states.nextMove;
                break;
            case game.states.win: 
                log("status", options.text.win.replace("##",players.current)); 
                next = game.states.start;
                break;
            case game.states.draw: 
                log("status", options.text.draw);    
                next = game.states.start;     
        }
        this.timerHdl = setTimeout(() => game.state = next, time);
    },
    set humanPlays(move){
      const player = players.current
      if(player.isHuman){
        const moveIdx = board.moves.indexOf(move);
        if(moveIdx === -1) {
            log("status","INVALID move Man stupid... forfits game.");
            players.next;
            clearTimeout(this.timerHdl);
            this.timerHdl = setTimeout(() => game.state = game.states.win, 2000);
            return;
        }
        board.moves.splice(moveIdx,1);    
        log("info",   ticTacToe.moveStr(move))
        player.moves += move;
        log("board", board.show(players));        
        var nextState = game.states.waitForNext; 
        if (ticTacToe.isWin(player.moves)) { nextState = game.states.win }
        if (board.full) { nextState = game.states.draw }
        game.state = nextState;
      } else {
        log("status","Man caught cheating! forfits game.");
        players.next;
        clearTimeout(this.timerHdl);
        this.timerHdl = setTimeout(()=> game.state = game.states.win, 2000);
      }
    
    },
    playTurn() {
        const player = players.next;
        if(player.isHuman) {
            log("board", board.show(players));   
            log("status", options.text.turn.replace("##",player));
            return game.states.humansTurn;
        
        }
 
        log("status", options.text.turn.replace("##",player));
        var moveStr =  player + "'s "; 
        var move = board.winningMove(player.moves);

        if (move === -1) {
            move = board.winningMove(players.opponant.moves);

            if (move === -1) {
                moveStr += options.text.moves.random; 
                move = board.randomMove;
             
        } else { moveStr += options.text.moves.block }
        } else { moveStr += options.text.moves.win }

        log("info", moveStr +  ticTacToe.moveStr(move))
       
        player.moves += move;
        
        log("board", board.show(players));        
        if (ticTacToe.isWin(player.moves)) { return  game.states.win }
        if (board.full) { return game.states.draw }
        return game.states.nextMove;
    },
}


/*===================================================================*/
/* Default display interface is to the console */
/* You need to config the ticTacToe.layout string for what you need */
const log = (type, ...args) => {
    if (type === "register") {
        log.board = args[0];
        log.status = args[1];
        log.info = args[2];
    } else if (type === "board") {
        log.board(...args);
    } else if (type === "info") {
        log.info(...args);
    } else {
        log.status(...args);
    }
}
log.info = log.status = log.board = console.log;




/*===================================================================*/
/* An interface to the display as the game is writen for the console */
log("register",showBoard, showStatus, showInfo); // point logger to new display
const displayTable = [b0,b1,b2,b3,b4,b5,b6,b7,b8];
function showBoard(posString) {
  var i = 9
  while (i--) { displayTable[i].textContent = posString[i] }
}
function showStatus(str) { statusContainer.textContent = str }
function showInfo(str) { infoContainer.textContent = str }



addEventListener("click",(e) => {
    if(game.humanFoe) {
        if(e.target.id[0] === "b") {
          game.humanPlays = 1 << (8-Number(e.target.id[1]));
       }
    
    } else {
        toPlay.textContent = "Man V Machine";
        game.state = game.states.start;
        game.humanPlaying = true;
   }

});

code {
   font-size : 20px;
   text-align: center;

}
#toPlay {
    position: absolute;
    bottom: 0px;
    font-size : 12px;
}
table {
    position: absolute;
    left: 42%;
    top: 60px;
    border-spacing: 0px;
    font-size : 28px;
    background : #eef;
}
td {
    padding : 0px 8px 0px 8px;
    cursor: pointer;

}
#infoContainer {
  font-size : 12px;
}
.allB {
  border : 1px solid black;
}
.topB {
  border-top : 0px;
}
.botB {
  border-bottom :  0px;
}
.leftB {
  border-left :  0px;
}
.rightB {
  border-right :  0px;
}

<code>
<div id="statusContainer"></div>
<table>
<tr><td id="b0" class="allB topB leftB">-</td><td id="b1" class="allB topB">-</td><td id="b2" class="allB topB rightB">-</td></tr>
<tr><td id="b3" class="allB leftB">-</td><td id="b4" class="allB">-</td><td id="b5" class="allB rightB">-</td></tr>
<tr><td id="b6" class="allB leftB botB">-</td><td id="b7" class="allB botB">-</td><td id="b8" class="allB rightB botB">-</td></tr>
</table>
<div id="infoContainer"></div>
<div id="toPlay">Click board to play!</div>
</code>

Stack Exchange Network

TicTacToe solver in JavaScript

2 Answers 2

Use loops

Your code

Only moves matter.

Example

You must log in to answer this question.

Hot Network Questions

TicTacToe solver in JavaScript

2 Answers 2

Use loops

Your code

Only moves matter.

Example

You must log in to answer this question.

Related

Hot Network Questions