1
\$\begingroup\$

I'm creating a Tic Tac Toe solver algorithm. The idea is to iterate through each row, column and both diagonals and put them into a map in JavaScript. With that map I can run other logic to check for a winner and where that winner's position is.

I'm not building an actual TTT game nor am I writing any AI for now. My question is if there's a better way of achieving the same results without having to use two for loops to get the columns and second diagonals.

let board = [
  ['x','o','x'],
  ['o','o','o'],
  ['o','o','x']
];

const mapper = board => {
  let map = {}, 
  d1 = [],
  d2 = [];

  for (let i = 0; i < board.length; i++) {
    let tmp = [];
    // get all rows
    map[`ROW${i}`] = board[i];

    // get second diagonals
    d2.push(board[i][board.length-1-i]);

    for (let j = 0; j < board.length; j++) {
      // get all columns
      tmp.push(board[j][i]);

      // get first diagonals
      if (i === j) {
        d1.push(board[i][j])
      }
    }
    
    map[`COL${i}`] = tmp;
  }

  map[`DIA1`] = d1;
  map[`DIA2`] = d2;

  return map;
}

const checkForWinner = board => {
  return mapper(board);
}

checkForWinner(board);

\$\endgroup\$
  • \$\begingroup\$ hard code it (i.e. unroll the loops) and cross your fingers that the TTT board never changes. You know, like zip codes never changed and 2 digit years was good enough. \$\endgroup\$ – radarbob Oct 7 '18 at 6:19
1
\$\begingroup\$

Not the board, store the moves

A TicTacToe board can be mapped to two 9bit numbers that represent each player's moves then the test for winning moves is just a simple bitwise test against the 8 possible combinations of move that are a win.

My question is if there's a better way of achieving the same results without having to use two for loops to get the columns and second diagonals.

The following may be what you want

// top left is low bit, bottom right is high bit
// coord to bit pos is x + y * 3
// Bit positions on board
// 0,1,2
// 3,4,5
// 6,7,8


const board = [['x','o','x'], ['o','o','o'], ['o','o','x']];
const players = ["x","o"];
const winMoves = [448,56,7,292,146,73,273,84];

const getMoves = (board, player) => {
  var moves = 0;
  for(var i = 0; i < 9; i ++){
     moves += board[i / 3 | 0][i % 3] === player ? 1 << i : 0;
  }
  return moves;
}
const checkWin = (board, player) =>{
  const moves = getMoves(board, player);
  return winMoves.some(win => (win & moves) === win);
}
if(!players.some(player => {
    if(checkWin(board, player)) { 
        console.log("Player " + player + " wins");
        return true;
    }
}){
  console.log("No winner");
}

Complete game state in 18bits

If you look into the problem further you can reverse the board/moves relationship so that the board is created from two sets of moves. This means you can store the complete game state with only 2 9bit numbers and you would not have to examine the board to find the win

const move = (player, x, y) => player |= 1 << (x + y * 3);
const checkWin = moves => winMoves.some(win => (win & moves) === win);
const winMoves = [448,56,7,292,146,73,273,84];
var movesX = 0, movesO = 0; // moves for each player game start

// or from your example the moves would be
// x o x
// o o o
// o o x
movesX = 0b100000101;
movesO = 0b011111010;

// with
console.log(checkWin(movesX)); // >> false
console.log(checkWin(movesO)); // >> True
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.