yubisen後退解析

yubisen.ts

import assert from 'assert';

type State = [number, number, number, number];

function stateToHashNum(state: State): number {
  const [x1, x2, y1, y2] = state;
  return (x1 << 9) | (x2 << 6) | (y1 << 3) | y2;
}

function hashNumToState(num: number): State {
  return [
    (num >> 9) & 7,
    (num >> 6) & 7,
    (num >> 3) & 7,
    num & 7,
  ];
}
enum Result {
  MARKED = 1,
  WIN = 2,
  LOSE = 3,
}

const dp: { [key: number]: Result | undefined } = {};
const deg: { [key: number]: number } = {};

function calcInitialState() {
  for (let x2 = 0; x2 <= 4; x2++) {
    for (let x1 = x2; x1 <= 4; x1++) {
      if (x1 === 0 && x2 === 0) continue;
      for (let y2 = 0; y2 <= 4; y2++) {
        for (let y1 = y2; y1 <= 4; y1++) {
          if (y1 === 0 && y2 === 0) continue;
          const state: State = [x1, x2, y1, y2];
          const hashNum = stateToHashNum(state);
          deg[hashNum] = calcDeg(state);
        }
      }
    }
  }
}

function calcDeg(state: number[]): number {
  const [x1, x2, y1, y2] = state;
  let deg = 1;
  if (x2 !== 0 && x1 !== x2) deg *= 2;
  if (y2 !== 0 && y1 !== y2) deg *= 2;
  return deg;
}

calcInitialState();

// for (let hash of Object.keys(deg)) {
//   console.log(`${hashNumToState(+hash)}, ${deg[+hash]}`)
// }

const queue: State[] = [];

koutai();

for (let hash of Object.keys(dp)) {
  console.log(`${hashNumToState(+hash)}, ${dp[+hash]}`)
}

function koutai() {
  for (let y2 = 0; y2 <= 4; y2++) {
    for (let y1 = y2; y1 <= 4; y1++) {
      if (y1 === 0 && y2 === 0) continue;
      const state: State = [0, 0, y1, y2];
      const hashNum = stateToHashNum(state);
      dp[hashNum] = Result.LOSE;
      queue.push(state);
    }
  }
  while (queue.length > 0) {
    const currentState = queue.pop()!;
    const currentHashNum = stateToHashNum(currentState);
    const prevStates = getPrevStates(currentState);
    for (const prevState of prevStates) {
      const prevHashNum = stateToHashNum(prevState);
      if (dp[prevHashNum] !== undefined) {
        continue;
      }
      // console.log(`${prevState} deg ${deg[prevHashNum]}`)
      assert(deg[prevHashNum] !== undefined, `undef ${prevState}`);
      deg[prevHashNum]--;
      if (dp[currentHashNum] === Result.LOSE) {
        dp[prevHashNum] = Result.WIN;
        queue.push(prevState);
      } else if (dp[currentHashNum] === Result.WIN && deg[prevHashNum] === 0) {
        dp[prevHashNum] = Result.LOSE;
        queue.push(prevState);
      }
    }
  }
}

function getPrevNum(x: number, y: number): number {
  assert(x !== y);
  if (x < y) return y - x;
  return y + 5 - x;
}

function getPrevStates(state: State): State[] {
  let [y1, y2, x1, x2] = state;
  const result: State[] = [];

  if (x1 !== y1) {
    const prevY1 = getPrevNum(x1, y1);
    result.push(prevY1 > y2 ? [x1, x2, prevY1, y2] : [x1, x2, y2, prevY1]);
  }
  if (x1 !== y2 && y1 !== y2) {
    const prevY2 = getPrevNum(x1, y2);
    result.push(y1 > prevY2 ? [x1, x2, y1, prevY2] : [x1, x2, prevY2, y1]);
  }
  if (x2 !== 0 && x1 !== x2) {
    if (x2 !== y1) {
      const prevY1 = getPrevNum(x2, y1);
      result.push(prevY1 > y2 ? [x1, x2, prevY1, y2] : [x1, x2, y2, prevY1]);
    }
    if (x2 !== y2 && y1 !== y2) {
      const prevY2 = getPrevNum(x2, y2);
      result.push(y1 > prevY2 ? [x1, x2, y1, prevY2] : [x1, x2, prevY2, y1]);
    }
  }
  return result;
}

const firstState: State = [1, 1, 1, 1];

function getNextNum(x: number, y: number) {
  return (x + y) % 5;
}

function calcNextStates(state: State): State[] {
  let [x1, x2, y1, y2] = state;
  const result: State[] = [];

  {
    const nextY1 = getNextNum(x1, y1);
    result.push(nextY1 > y2 ? [nextY1, y2, x1, x2] : [y2, nextY1, x1, x2]);
  }
  if (y1 !== y2 && y2 !== 0) {
    const nextY2 = getNextNum(x1, y2);
    result.push(y1 > nextY2 ? [y1, nextY2, x1, x2] : [nextY2, y1, x1, x2]);
  }
  if (x1 !== x2 && x2 !== 0) {
    {
      const nextY1 = getNextNum(x2, y1);
      result.push(nextY1 > y2 ? [nextY1, y2, x1, x2] : [y2, nextY1, x1, x2]);
    }
    if (y1 !== y2 && y2 !== 0) {
      const nextY2 = getNextNum(x2, y2);
      result.push(y1 > nextY2 ? [y1, nextY2, x1, x2] : [nextY2, y1, x1, x2]);
    }
  }
  return result;
}

function guide(state: State) {
  console.log('GUIDE===============================================')
  const [x1, x2, y1, y2] = state;
  const nextStates = calcNextStates(state)
  console.log(`state: ${state}`)
  console.log("nextStates:")
  const bestMoveStates: State[] = [];
  for (const nextState of nextStates) {
    const result = dp[stateToHashNum(nextState)];
    assert(result !== Result.LOSE, `${state} ${nextState}`)
    console.log(`${nextState} ${result === undefined ? "DRAW" : "LOSE"} `)
    if (result === undefined) bestMoveStates.push(nextState);
  }
  if (x2 === 0 && y2 === 0) return;
  const rand = (Math.random() * bestMoveStates.length) | 0
  guide(bestMoveStates[rand]!);
}

guide(firstState);