黑白棋AI（完整版） | 程式專案

{"id":660348,"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        \u003cinput type=\\\"checkbox\\\" v-model=\\\"enableAI\\\"/\u003e enable AI\\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\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\":\"// 點擊「run AI」時會執行此函式\\n// 如果有啟用 enable AI 每次點擊棋盤下棋後，也會自動執行此函式\\nfunction AI(game, depth) {\\n    var startTime = Date.now()\\n    var result = alphabeta(game.clone(), depth, -Infinity, Infinity)\\n    game.place(result.x, result.y)\\n    console.log(`depth: ${depth} cost: ${Date.now() - startTime}ms`)\\n}\\n\\n\\nfunction alphabeta(game, depth, alpha, beta) {\\n    \\n    // 紀錄目前找到最佳的策略下法以及棋分數\\n    var best = {\\n        x: undefined,\\n        y: undefined,\\n        score: game.turn === 'w' ? -Infinity: Infinity\\n    }\\n\\n    for (var x = 0; x \u003c 8; x++) {\\n        for (var y = 0; y \u003c 8; y++) {\\n            if (game.place(x, y)) {\\n\\n                if (depth \u003e 1) {\\n                    var score = alphabeta(game, depth - 1, alpha, beta).score\\n                } else {\\n                    var score = evaluation(game.grid)\\n                }\\n\\n                if (game.turn === 'b' \u0026\u0026 score \u003e best.score) {\\n                    best.x = x\\n                    best.y = y\\n                    alpha = best.score = score\\n                }\\n                if (game.turn === 'w' \u0026\u0026 score \u003c best.score) {\\n                    best.x = x\\n                    best.y = y\\n                    beta = best.score = score\\n                }\\n                game.undo()\\n                \\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\\n// 評估函式\\nfunction evaluation(grid) {\\n    var score = 0\\n    for (var x = 0; x \u003c 8; x++) {\\n        for (var y = 0; y \u003c 8; y++) {\\n            var 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] === 'w') score += i\\n            if (grid[y][x] === 'b') score -= i\\n        }\\n    }\\n    return score\\n}\\n\\n\"}","created_at":"2023-12-12T11:37:19.966+08:00","updated_at":"2023-12-12T11:37:27.270+08:00","name":"黑白棋AI（完整版）","language":"web","screenshot":{"url":null},"parent_id":2,"plugin":"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 = -1; y \u003c 9; y++) {\n            this.grid[y] = {}\n            for (let x = -1; x \u003c 9; 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\nconst game = new Othello()\n\nnew Vue({\n    el: '#game',\n    data: {\n        game,\n        validPos: game.getValidPos(),\n        level: 4,\n        enableAI: true,\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.active.x \u0026\u0026 y == this.active.y) arr.push('active')\n            return arr\n        },\n\n        place(x, y) {\n            if (this.game.place(x, y)) {\n                this.validPos = this.game.getValidPos()\n                if (this.validPos.length === 0) {\n                    this.game.switch()\n                } else {\n                    if (this.enableAI) {\n                        setTimeout(this.runAI, 2000)\n                    }\n                }\n            }\n        },\n\n        runAI() {\n            this.validPos = this.game.getValidPos()\n            if (this.validPos.length === 0) return this.game.switch()\n            AI(this.game, this.level)\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 {\n                black, white\n            }\n        },\n\n        status() {\n            if (this.validPos.length \u003e 0) {\n                return game.turn === 'b' ? 'black turn': 'white turn'\n            } else {\n                const {\n                    black, white\n                } = this.scores\n                if (black === white) return 'tie'\n                return black \u003e white ? 'black win': 'white win'\n            }\n        },\n\n        active () {\n            const logs = this.game.logs\n            return logs.length \u003e 0 ? logs[0]: {}\n        }\n    }\n})","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":74,"hashid":"9ygs5vdv5","is_content_changed":true,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}