https://2048.sisisin.house/ のゲームAI

2048-sisisin.ts

const $ = (selector: string): HTMLElement => document.querySelector(selector)!
const $$ = (selector: string): HTMLElement[] =>
    Array.from(document.querySelectorAll(selector))

type Coord = { x: number; y: number }
type Nyan = { pos: Coord; point: number }

const plusCoord = (pos1: Coord, pos2: Coord): Coord => {
    return { x: pos1.x + pos2.x, y: pos1.y + pos2.y }
}
const minusCoord = (pos1: Coord, pos2: Coord): Coord => {
    return { x: pos1.x - pos2.x, y: pos1.y - pos2.y }
}
const coordEqual = (pos1: Coord, pos2: Coord): boolean => {
    return pos1.x === pos2.x && pos1.y === pos2.y
}

const copyMatrix = (base: number[][]): number[][] => {
    const result = []
    for (const line of base) {
        result.push([...line])
    }
    return result
}

const toKeyCode = (com: string): number => {
    switch (com) {
        case 'U':
            return 38
        case 'D':
            return 40
        case 'L':
            return 37
        case 'R':
            return 39
        default:
            throw Error('おしめえだ！')
    }
}

const dispatchKeydown = (keyCode: number): void => {
    document.dispatchEvent(new KeyboardEvent('keydown', { keyCode }))
    document.dispatchEvent(new KeyboardEvent('keyup', { keyCode }))
}

const getNyans = (): Nyan[] => {
    const gap = 112
    const nyans = $$('.gameCell').filter((nyan: HTMLElement) =>
        nyan.style.getPropertyValue('background-image')
    )
    return nyans.map((nyan: HTMLElement) => {
        const x = Math.floor(
            Number(nyan.style.getPropertyValue('left').match(/(\d*)px/)![1]) /
                gap
        )
        const y = Math.floor(
            Number(nyan.style.getPropertyValue('top').match(/(\d*)px/)![1]) /
                gap
        )
        const pos = { x, y }
        const point = Number(
            nyan.style
                .getPropertyValue('background-image')
                .match(/.*sisisin(\d*)\./)![1]
        )

        return { pos, point }
    })
}

const mkWhiteBoard = (): number[][] => {
    return [
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
    ]
}

const inputBoard = (): number[][] => {
    const board = mkWhiteBoard()

    for (const { pos, point } of getNyans()) {
        board[pos.y][pos.x] = point
    }

    return board
}

// [操作後のボード, 操作が成立したか] の組を返す
const dispatchCommand = (
    board: number[][],
    com: string
): [number[][], boolean] => {
    const [initPoint, initDelta, simuDelta] = (() => {
        switch (com) {
            case 'U':
                return [
                    { x: 0, y: 0 },
                    { x: 1, y: 0 },
                    { x: 0, y: 1 },
                ]
            case 'D':
                return [
                    { x: 3, y: 3 },
                    { x: -1, y: 0 },
                    { x: 0, y: -1 },
                ]
            case 'L':
                return [
                    { x: 0, y: 3 },
                    { x: 0, y: -1 },
                    { x: 1, y: 0 },
                ]
            case 'R':
                return [
                    { x: 3, y: 0 },
                    { x: 0, y: 1 },
                    { x: -1, y: 0 },
                ]
            default:
                throw Error('おしめえだ！')
        }
    })()

    let isSuccesful = false

    // そのままスライド
    const slideBoard = mkWhiteBoard()
    let startPoint = Object.assign({}, initPoint)
    for (let i = 0; i < 4; i++) {
        let putPoint = Object.assign({}, startPoint)
        let focusPoint = Object.assign({}, startPoint)
        for (let j = 0; j < 4; j++) {
            let focus = board[focusPoint.y][focusPoint.x]
            if (focus > 0) {
                slideBoard[putPoint.y][putPoint.x] = focus
                if (!coordEqual(putPoint, focusPoint)) {
                    isSuccesful = true
                }
                putPoint = plusCoord(putPoint, simuDelta)
            }

            focusPoint = plusCoord(focusPoint, simuDelta)
        }
        startPoint = plusCoord(startPoint, initDelta)
    }

    // 合成
    const retBoard = mkWhiteBoard()
    startPoint = Object.assign({}, initPoint)
    for (let i = 0; i < 4; i++) {
        let putPoint = Object.assign({}, startPoint)
        let focusPoint = Object.assign({}, startPoint)
        for (let j = 0; j < 4; j++) {
            if (j <= 2) {
                const focus1 = slideBoard[focusPoint.y][focusPoint.x]
                const focusPoint2 = plusCoord(focusPoint, simuDelta)
                const focus2 = slideBoard[focusPoint2.y][focusPoint2.x]
                if (focus1 === focus2) {
                    retBoard[putPoint.y][putPoint.x] = focus1 * 2
                    if (focus1 > 0) {
                        isSuccesful = true
                    }

                    // ２マス進む
                    j++
                    focusPoint = plusCoord(focusPoint, simuDelta)
                } else {
                    retBoard[putPoint.y][putPoint.x] =
                        slideBoard[focusPoint.y][focusPoint.x]
                }
            } else {
                retBoard[putPoint.y][putPoint.x] =
                    slideBoard[focusPoint.y][focusPoint.x]
            }

            putPoint = plusCoord(putPoint, simuDelta)
            focusPoint = plusCoord(focusPoint, simuDelta)
        }
        startPoint = plusCoord(startPoint, initDelta)
    }

    return [retBoard, isSuccesful]
}

const countBlockNum = (board: number[][]): number => {
    let cnt = 0

    for (let y = 0; y < 4; y++) {
        for (let x = 0; x < 4; x++) {
            if (board[y][x] > 0) {
                cnt++
            }
        }
    }

    return cnt
}

/*
4 * 16*2 == 2^7 一操作後の全盤面は悲観的に見積もると左の通り
３回操作くらい行けそう
(2^7)^3 == 2_097_152
*/

// 右下からその上に掛けて大きいsisisinが集まってると高評価
const evaluate = (board: number[][]): number => {
    const rBoard = dispatchCommand(board, 'R')[0]
    const dBoard = dispatchCommand(board, 'D')[0]

    // 盤面の評価関数
    const calc = (targetBoard: number[][]): number => {
        let lineBoard = targetBoard.flat()
        lineBoard.sort((a, b) => b - a)

        let res = 0.0
        // 右端の列の下方にに大きい値が集まっているか
        if (targetBoard[3][3] === lineBoard[0]) {
            res += 7.0
            if (targetBoard[2][3] === lineBoard[1]) {
                res += 2.5
                if (targetBoard[1][3] === lineBoard[2]) {
                    res += 0.5
                }
            }
        }

        // ボード上の一番大きい数を掛ける
        res *= lineBoard[0]

        // ブロック数が多いほど減点
        res -= countBlockNum(board) * 0.01

        return res
    }

    return Math.max(calc(rBoard), calc(dBoard))
}

// TODO: 発生確率を織り込んで4を含める。2と4の生成確率は 9:1 の割合。
const mkRandomNyanGenBoards = (board: number[][]): number[][][] => {
    let res = []

    for (let y = 0; y < 4; y++) {
        for (let x = 0; x < 4; x++) {
            if (board[y][x] === 0) {
                const board2 = copyMatrix(board)
                // const board4 = copyMatrix(board)
                board2[y][x] = 2
                // board4[y][x] = 4
                res.push(board2)
                // ret.push(board4)
            }
        }
    }

    return res
}

const shuffle = ([...array]) => {
    for (let i = array.length - 1; i >= 0; i--) {
        const j = Math.floor(Math.random() * (i + 1))
        ;[array[i], array[j]] = [array[j], array[i]]
    }
    return array
}

const coms = ['R', 'D', 'L', 'U']

type State = { com: string; nextBoard: number[][]; isSuccesful: boolean }

const search = (sts: State[]): State => {
    const maxDepth = 3
    const func = (board: number[][], depth: number): number => {
        // 探索範囲削減のため絞る
        const genBoards = shuffle(mkRandomNyanGenBoards(board)).slice(0, 6)
        if (depth == maxDepth) {
            // 評価値の合算を返す
            return genBoards.length === 0
                ? 0
                : genBoards.map(evaluate).reduce((a, b) => a + b) /
                      genBoards.length
        } else {
            // ランダム生成全パターンのスコア一覧
            const scores = genBoards.map((board) => {
                // 操作全通り試して最も良いスコアを選ぶ
                const scores = coms.map((c) => {
                    let [nextBoard, isSuccesful] = dispatchCommand(board, c)
                    return isSuccesful ? func(nextBoard, depth + 1) : 0
                })
                return Math.max(...scores)
            })

            return scores.length === 0
                ? 0
                : scores.reduce((a, b) => a + b) / scores.length
        }
    }

    let bestScore = 0
    let res = sts[0]
    for (const st of sts) {
        const score = func(st.nextBoard, 1)
        if (score > bestScore) {
            bestScore = score
            res = st
        }
    }

    console.log(bestScore)
    return res
}

const solve = () => {
    setInterval(() => {
        let board = inputBoard()
        let validComs = coms
            .map((com: string) => {
                const [nextBoard, isSuccesful] = dispatchCommand(board, com)
                return { com, nextBoard, isSuccesful }
            })
            .filter((e) => e.isSuccesful)

        // 探索
        const choice = search(validComs)

        dispatchKeydown(toKeyCode(choice.com))
    }, 500)
}

const test = () => {
    let board = inputBoard()
    let validComs = coms
        .map((com: string) => {
            const [nextBoard, isSuccesful] = dispatchCommand(board, com)
            return { com, nextBoard, isSuccesful }
        })
        .filter((e) => e.isSuccesful)

    let res = search(validComs)
    console.log(res)
}

$('button')!.click()

// dispatchCommand(inputBoard(), 'U')