Skip to content

Instantly share code, notes, and snippets.

@qsona
Created August 18, 2019 18:03
Show Gist options
  • Save qsona/1b04945334ef2f372b0c72645cf82b0c to your computer and use it in GitHub Desktop.
Save qsona/1b04945334ef2f372b0c72645cf82b0c to your computer and use it in GitHub Desktop.
yubisen後退解析
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment