絕對會輸的黑白棋 AI | Programming Project

{"id":296708,"student_id":10,"content":"{\"html\":\"\u003c!DOCTYPE html\u003e\\n\u003chtml lang=\\\"en\\\"\u003e\\n\u003chead\u003e\\n    \u003cmeta charset=\\\"UTF-8\\\"\u003e\\n    \u003cmeta name=\\\"viewport\\\" content=\\\"width=device-width, initial-scale=1.0\\\"\u003e\\n    \u003cmeta http-equiv=\\\"X-UA-Compatible\\\" content=\\\"ie=edge\\\"\u003e\\n    \u003ctitle\u003eDocument\u003c/title\u003e\\n    \u003cscript src=\\\"https://cdn.jsdelivr.net/npm/vue/dist/vue.js\\\"\u003e\u003c/script\u003e\\n    \u003clink rel=\\\"stylesheet\\\" href=\\\"index.css\\\"\u003e\\n\u003c/head\u003e\\n\u003cbody\u003e\\n    \u003cdiv id=\\\"game\\\"\u003e\\n        \u003cdiv class=\\\"grid\\\"\u003e\\n            \u003cdiv v-for=\\\"(_, y) in 8\\\" class=\\\"row\\\"\u003e\\n                \u003cdiv v-for=\\\"(_, x) in 8\\\" class=\\\"col\\\" :class=\\\"getClassOf(x, y)\\\" @click=\\\"place(x, y)\\\"\u003e\\n                \u003c/div\u003e\\n            \u003c/div\u003e\\n        \u003c/div\u003e\\n        \u003cp\u003e{{ scores.black }} : {{ scores.white }}\u003cbr\u003e{{ status }}\u003c/p\u003e\\n        \u003cselect v-model=\\\"level\\\"\u003e\\n            \u003coption v-for=\\\"i in 6\\\" :value=\\\"i\\\" :key=\\\"i\\\"\u003elevel {{ i }}\u003c/option\u003e\\n        \u003c/select\u003e\\n        \u003cbutton @click=\\\"runAI\\\"\u003erun AI\u003c/button\u003e\\n        \u003cbutton @click=\\\"undo\\\"\u003eundo\u003c/button\u003e\\n        \u003cbutton @click=\\\"restart\\\"\u003erestart\u003c/button\u003e\\n    \u003c/div\u003e\\n    \u003cscript src=\\\"othello.js\\\"\u003e\u003c/script\u003e\\n    \u003cscript src=\\\"ai.js\\\"\u003e\u003c/script\u003e\\n\u003c/body\u003e\\n\\n\u003c/html\u003e\",\"css\":\":root {\\n    --col-size: 50px;\\n    --circle-size: 35px;\\n}\\nbody {\\n    text-align: center;\\n    background-color: #ffc859;\\n    font-family: monospace;\\n    padding: 30px;\\n}\\n.grid {\\n    display: inline-block;\\n    border: 1px solid black;\\n}\\n.row {\\n    display: flex;\\n}\\n.col {\\n    position: relative;\\n    width: var(--col-size);\\n    height: var(--col-size);\\n    text-align: center;\\n    box-sizing: border-box;\\n    border: 1px solid black;\\n}\\n.col::after,\\n.col::before {\\n    content: '';\\n    position: absolute;\\n    top: 50%;\\n    left: 50%;\\n    width: 0px;\\n    height: 0px;\\n    border-radius: 50%;\\n    transform: translate(-50%, -50%);\\n}\\n.col.hint::before,\\n.col.black::after,\\n.col.white::after {\\n    width: var(--circle-size);\\n    height: var(--circle-size);\\n    border: 1px solid black;\\n}\\n.col.hint::before {\\n    cursor: pointer;\\n    border-style: dashed;\\n}\\n.col.black::after {\\n    background-color: black;\\n}\\n.col.white::after {\\n    background-color: white;\\n}\\n.col.black::after,\\n.col.white::after {\\n    transition: background-color 1s step-end;\\n}\\n.col.active::after {\\n    transition: width .2s linear, height .2s linear !important;\\n}\",\"js\":\"class Othello {\\n\\n    constructor() {\\n        this.width = 8\\n        this.height = 8\\n        this.grid = {}\\n        this.turn = 'b'\\n        this.logs = []\\n        this.steps = 0\\n        this.offsets = [{ x: 1, y: 0 }, { x: -1, y: 0 }, { x: 0, y: 1 }, { x: 0, y: -1 }, { x: 1, y: 1 }, { x: -1, y: -1 }, { x: 1, y: -1 }, { x: -1, y: 1 }]\\n\\n        this.initGrid()\\n    }\\n\\n    reset() {\\n        this.turn = 'b'\\n        this.logs = []\\n        this.steps = 0\\n        this.initGrid()\\n    }\\n\\n    initGrid() {\\n        for (let y = -2; y \u003c 10; y++) {\\n            this.grid[y] = {}\\n            for (let x = -2; x \u003c 10; x++) {\\n                this.grid[y][x] = ''\\n            }\\n        }\\n        this.grid[3][3] = 'b'\\n        this.grid[4][4] = 'b'\\n        this.grid[4][3] = 'w'\\n        this.grid[3][4] = 'w'\\n    }\\n\\n    getValidPos() {\\n        const arr = []\\n        for (let x = 0; x \u003c 8; x++) {\\n            for (let y = 0; y \u003c 8; y++) {\\n                if (this.place(x, y)) {\\n                    arr.push({ x, y })\\n                    this.undo()\\n                }\\n            }\\n        }\\n        return arr\\n    }\\n\\n    place(x, y) {\\n        if (this.grid[y][x] !== '') return false\\n\\n        let isValid = false\\n        this.offsets.forEach(o =\u003e {\\n            if (this.grid[y + o.y][x + o.x] === this.turn) return\\n            if (this.fillLine(x, y, o.x, o.y)) isValid = true\\n        })\\n\\n        if (isValid) {\\n            this.logs.unshift({ x, y, status: this.grid[y][x], steps: this.steps })\\n            this.grid[y][x] = this.turn\\n            this.switch()\\n            this.steps++\\n        }\\n\\n        return isValid\\n    }\\n\\n    fillLine(x, y, vx, vy) {\\n\\n        while (true) {\\n            x += vx\\n            y += vy\\n            const target = this.grid[y][x]\\n            if (target === '') return false\\n            if (target === this.turn) break\\n        }\\n\\n        while (true) {\\n            x -= vx\\n            y -= vy\\n            const target = this.grid[y][x]\\n            if (target === '') return true\\n            if (target === this.turn) return true\\n            if (target !== this.turn) {\\n                this.logs.unshift({ x, y, status: this.grid[y][x], steps: this.steps })\\n                this.grid[y][x] = this.turn\\n            }\\n        }\\n    }\\n\\n    switch() {\\n        this.turn = this.turn === 'b' ? 'w' : 'b'\\n    }\\n\\n    undo() {\\n        if (this.steps \u003e 0) {\\n            this.steps--\\n            while (this.logs[0] \u0026\u0026 this.logs[0].steps === this.steps) {\\n                const diff = this.logs.shift()\\n                this.grid[diff.y][diff.x] = diff.status\\n            }\\n            this.switch()\\n        }\\n    }\\n\\n    clone() {\\n        const virtual = new Othello()\\n        virtual.grid = JSON.parse(JSON.stringify(this.grid))\\n        virtual.logs = JSON.parse(JSON.stringify(this.logs))\\n        virtual.turn = this.turn\\n        virtual.steps = this.steps\\n        return virtual\\n    }\\n}\\n\\nfunction AI(game, level) {\\n    const startTime = Date.now()\\n    const result = alphabeta(game.clone(), level)\\n    console.log(`depth: ${level} cost: ${Date.now() - startTime}ms`)\\n    return result\\n}\\n\\nfunction alphabeta(game, deep, alpha = -Infinity, beta = Infinity) {\\n\\n    let best = {\\n        x: undefined,\\n        y: undefined,\\n        score: game.turn === 'w' ? -Infinity : Infinity\\n    }\\n\\n    for (let x = 0; x \u003c 8; x++) {\\n        for (let y = 0; y \u003c 8; y++) {\\n            if (game.place(x, y)) {\\n\\n                let result = deep \u003e 0 ? alphabeta(game, deep - 1, alpha, beta) : (\\n                    { x, y, score: evaluation(game.grid) }\\n                )\\n\\n                if (game.turn === 'w' \u0026\u0026 result.score \u003c best.score) {\\n                    alpha = best.score = result.score\\n                    best.x = x\\n                    best.y = y\\n                }\\n\\n                if (game.turn === 'b' \u0026\u0026 result.score \u003e best.score) {\\n                    beta = best.score = result.score\\n                    best.x = x\\n                    best.y = y\\n                }\\n\\n                game.undo()\\n\\n                if (alpha \u003e beta) return best\\n            }\\n        }\\n    }\\n\\n    if (best.x === undefined) {\\n        best.score = evaluation(game.grid)\\n    }\\n\\n    return best\\n}\\n\\nfunction evaluation(grid) {\\n    let score = 0\\n    for (let x = 0; x \u003c 8; x++) {\\n        for (let y = 0; y \u003c 8; y++) {\\n            let i = 1\\n            if (x === 0 || x === 7) i *= 10\\n            if (y === 0 || y === 7) i *= 10\\n            if (x === 1 || y === 1 || x === 6 || y === 6) i *= -1\\n            if (grid[y][x] === 'b') score += i\\n            if (grid[y][x] === 'w') score -= i\\n        }\\n    }\\n    return score\\n}\\n\\nconst game = new Othello()\\n\\nnew Vue({\\n    el: '#game',\\n    data: {\\n        game,\\n        validPos: game.getValidPos(),\\n        placeX: undefined,\\n        placeY: undefined,\\n        level: 4,\\n    },\\n    methods: {\\n        getClassOf(x, y) {\\n            const s = this.game.grid[y][x]\\n            const arr = []\\n            if (this.validPos.some(pos =\u003e pos.x === x \u0026\u0026 pos.y === y)) return 'hint'\\n            if (s === 'b') arr.push('black')\\n            if (s === 'w') arr.push('white')\\n            if (x == this.placeX \u0026\u0026 y == this.placeY) arr.push('active')\\n            return arr\\n        },\\n\\n        place(x, y) {\\n            if (this.game.place(x, y)) {\\n                this.placeX = x\\n                this.placeY = y\\n                this.validPos = this.game.getValidPos()\\n                if (this.validPos.length === 0) {\\n                    this.game.switch()\\n                } else {\\n                    setTimeout(this.runAI, 2000)\\n                }\\n            }\\n        },\\n\\n        runAI() {\\n            this.validPos = this.game.getValidPos()\\n            if (this.validPos.length === 0) return this.game.switch()\\n            const result = AI(this.game, this.level)\\n            this.placeX = result.x\\n            this.placeY = result.y\\n            game.place(result.x, result.y)\\n\\n            this.validPos = this.game.getValidPos()\\n            if (this.validPos.length === 0) {\\n                this.game.switch()\\n                this.runAI()\\n            }\\n        },\\n\\n        undo() {\\n            this.game.undo() // undo ai steps\\n            this.game.undo() // undo my steps\\n            this.validPos = this.game.getValidPos()\\n        },\\n\\n        restart () {\\n            this.game.reset()\\n            this.validPos = this.game.getValidPos()\\n        }\\n    },\\n\\n    computed: {\\n        scores() {\\n            let black = 0\\n            let white = 0\\n            for (let y = 0; y \u003c 8; y++) {\\n                for (let x = 0; x \u003c 8; x++) {\\n                    if (this.game.grid[y][x] === 'b') black++\\n                    if (this.game.grid[y][x] === 'w') white++\\n                }\\n            }\\n            return { black, white }\\n        },\\n\\n        status() {\\n            if (this.validPos.length \u003e 0) {\\n                return game.turn === 'b' ? 'black turn' : 'white turn'\\n            } else {\\n                const { black, white } = this.scores\\n                if (black === white) return 'tie'\\n                return black \u003e white ? 'black win' : 'white win'\\n            }\\n        }\\n    }\\n})\"}","created_at":"2021-09-07T16:41:19.340+08:00","updated_at":"2021-09-07T16:42:06.697+08:00","name":"絕對會輸的黑白棋 AI","language":"web","screenshot":{"url":null},"parent_id":294656,"plugin":"","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":351,"hashid":"yeysv3zwe","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}