​

const n = 12;

const m = 12;

const canSize = 500;

const zoom = Math.min(canSize / n, canSize / m);

​

let moves;

​

let hoverMove;

let human = true;

​

const timeToThink = 5; //sec

​

function setup() {

  let zoom = Math.min(canSize / n, canSize / m);

  createCanvas(n * zoom, m * zoom);

​

  moves = [];

}

​

function draw() {

  drawBoard();

​

  let mx = human ? mouseX : mouseX - zoom / 2;

  let my = human ? mouseY - zoom / 2 : mouseY;

  if (mx < width && my < height) {

    let x = Math.floor(mx / zoom);

    let y = Math.floor(my / zoom);

    hoverMove = new Move(x, y, true);

    hoverMove.draw(true);

  } else {

    hoverMove = null;

  }

​

  if (checkFull(moves, false)) {

    drawBoard();

    createP('Mensch gewinnt');

    noLoop();

    return;

  }

  makeSmartMove();

  if (checkFull(moves, true)) {

    drawBoard();

    createP('AI gewinnt');

    noLoop();

    return;

  }

}

​

function touchStarted() {

  if (!human) return;

  let mx = human ? mouseX : mouseX - zoom / 2;

  let my = human ? mouseY - zoom / 2 : mouseY;

  if (mx < width && my < height) {

    let x = Math.floor(mx / zoom);

    let y = Math.floor(my / zoom);

    hoverMove = new Move(x, y, true);

  } else {

    hoverMove = null;

  }

​

  if (hoverMove && moveIsValid(moves, hoverMove)) {

    moves.push(hoverMove);

    human = !human;

  }

}

​

function makeSmartMove() {

  if (human) return;

  let poss = getPossibleStates(moves, human);

  let endTime = new Date().getTime() + timeToThink * 1000;

  let maxDepth = 2*(Math.log(1000) / Math.log(poss.length));

  print(maxDepth);

  //maxDepth = 2;

  poss = poss.map(board => ({

    state: board,

    points: bewerte(board, human, 1, maxDepth, -Infinity, +Infinity, endTime)

  }));

  poss.sort((a, b) => b.points - a.points);

  // print(poss.map(p => p.points));

  moves = poss.shift().state;

  human = true;

}

​

function bewerte(board, human, depth, maxDepth, alpha, beta, endTime) {

  // ist brett voll?

  let isFull = checkFull(board, !human);

  if (isFull && human) {

    return -15*n*m - depth;

  } else if (isFull && !human) {

    return 15*n*m - depth;

  }

​

  if (endTime < new Date().getTime() || depth >= maxDepth) {

    //print('Abschätzung')

    let movesForAI = numOfPossibleStates(board, false);

    let movesForHuman = numOfPossibleStates(board, true);

    return (125 * (movesForAI - movesForHuman)) - depth/2;

  }

​

  // go deeper

  let poss = getPossibleStates(board, !human);

  if (human) { // Mini

    let bestVal = +Infinity;

    for (let b of poss) {

      let value = bewerte(b, false, depth + 1, maxDepth, alpha, beta);

      bestVal = min(bestVal, value);

      beta = min(beta, bestVal);

      if (beta <= alpha) break;

    }

    return bestVal;

  } else { // Max

    let bestVal = -Infinity;

    for (let b of poss) {

      let value = bewerte(b, true, depth + 1, maxDepth, alpha, beta);

      bestVal = max(bestVal, value);

      alpha = max(alpha, bestVal);

      if (beta <= alpha) break;

    }

    return bestVal;

  }

}

​

function checkFull(board, human) {

  for (let x = 0; x < n; x++) {

    for (let y = 0; y < m; y++) {

      let newMove = new Move(x, y, human);

      if (moveIsValid(board, newMove)) return false;

    }

  }

  return true;

}

​

function numOfPossibleStates(moves, human) {

  let counter = 0;

  for (let x = 0; x < n; x++) {

    for (let y = 0; y < m; y++) {

      let newMove = new Move(x, y, human);

      if (moveIsValid(moves, newMove)) counter++;

    }

  }

​

  return counter;

}

​

function getPossibleStates(moves, human) {

  let possible = [];

​

  for (let x = 0; x < n; x++) {

    for (let y = 0; y < m; y++) {

      let newMove = new Move(x, y, human);

      if (moveIsValid(moves, newMove)) possible.push([...moves, newMove]);

    }

  }

​

  return possible;

}

​

function moveIsValid(moves, newMove) {

  if (!newMove) return false;

  if (newMove.start.x < 0 || newMove.start.y < 0) return false;

  if (newMove.vert) {

    if (newMove.start.y + 1 >= m) return false;

  } else {

    if (newMove.start.x + 1 >= n) return false;

  }

​

  for (let other of moves) {

    if (other.start.equals(newMove.start) || other.start.equals(newMove.end)) return false;

    if (other.end.equals(newMove.start) || other.end.equals(newMove.end)) return false;

  }

  return true;

}

​

function drawGrid() {

  stroke(0);

  strokeWeight(1);

  for (let x = 1; x < n; x++) {

    line(width * x / n, 0, width * x / n, height);

  }

  for (let y = 1; y < m; y++) {

    line(0, height * y / m, width, height * y / m);

  }

}

​

function drawBoard() {

  background(80);

  drawGrid();

  for (let move of moves) move.draw();

}