Tetris AI | 程式專案 | 橘蘋學習平台

{"id":298343,"student_id":10,"content":"{\"html\":\"\u003c!DOCTYPE html\u003e\\n\u003chtml lang=\\\"en\\\"\u003e\\n\\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    \u003cstyle\u003e\\n        canvas { border: 1px solid #333333; }\\n    \u003c/style\u003e\\n\u003c/head\u003e\\n\\n\u003cbody\u003e\\n    \u003ccanvas id=\\\"stage\\\"\u003e\u003c/canvas\u003e\\n\u003c/body\u003e\\n\\n\u003c/html\u003e\",\"css\":\"/* 設定整個頁面內容水平置中、內寬為 30 像素：*/\\nbody {\\n    text-align: center;\\n    padding: 30px;\\n}\\n\\n/* 設定圖片的寬度為銀幕一半寬 */\\nimg {    \\n    max-width: 50%; \\n}\\n\\n/* 設定文字的顏色為淡黑色 */\\np {\\n    color: #555555;\\n}\",\"js\":\"const BLOCKS = [\\n    [{x: 0, y: 2}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 1, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 2, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 3, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 2, y: 1}, {x: 3, y: 1}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 1, y: 1}, {x: 2, y: 1}, {x: 2, y: 2}, {x: 3, y: 2}],\\n    [{x: 2, y: 1}, {x: 3, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}],\\n    \\n]\\nconst COLORS = ['#db312b', '#569f14', '#1366af', '#fd680b', '#d7b815', '#582479']\\n\\nclass Tetris {\\n\\n    constructor() {\\n        this.width = 10\\n        this.height = 20\\n        this.blocks = []\\n        this.posX = undefined\\n        this.posY = undefined\\n        this.status = 'playing' // playing, gameover\\n        this.scores = 0\\n        this.nextBlock = this.randomBlock()\\n        this.loadBlocks()\\n    }\\n\\n    getGrid () {\\n        let grid = []\\n        for (let y = 0; y \u003c this.height; y++) {\\n            grid[y] = []\\n            for (let x = 0; x \u003c this.width; x++) {\\n                grid[y][x] = ' '\\n            }\\n        }\\n        this.blocks.filter(b =\u003e b.state === 'fixed').forEach(b =\u003e grid[b.y][b.x] = '*')\\n        return grid\\n    }\\n\\n    loadBlocks() {\\n\\n        if (this.status === 'gameover') return false\\n        if (this.blocks.some(b =\u003e b.state === 'fixed' \u0026\u0026 b.y \u003c= 2)) {\\n            return this.status = 'gameover'\\n        }\\n\\n        const state = 'moving'\\n        const color = this.nextBlock.color\\n        const block = this.nextBlock.block\\n\\n        this.blocks = this.blocks.concat(block.map(b =\u003e {\\n            return { color, state, x: b.x + 2, y: b.y }\\n        }))\\n\\n        this.posX = 4\\n        this.posY = 2\\n\\n        this.nextBlock = this.randomBlock()\\n    }\\n\\n    randomBlock() {\\n        const rand1 = Math.floor(Math.random() * BLOCKS.length)\\n        const rand2 = Math.floor(Math.random() * COLORS.length)\\n        return {\\n            block: BLOCKS[rand1],\\n            color: COLORS[rand2],\\n        }\\n    }\\n\\n    moveDownToEnd() {\\n        while(this.moveDown()) {}\\n    }\\n\\n    moveDown() {\\n        const bool = this.move(this._moveDown)\\n        if (bool) this.posY++\\n        else {\\n            this.blocks.forEach(b =\u003e b.state = 'fixed')\\n            this.eraseLines()\\n            this.loadBlocks()\\n        }\\n        return bool\\n    }\\n\\n    moveRight() {\\n        const bool = this.move(this._moveRight)\\n        if (bool) this.posX++\\n        return bool\\n    }\\n\\n    moveLeft() {\\n        const bool = this.move(this._moveLeft)\\n        if (bool) this.posX--\\n        return bool\\n    }\\n\\n    turnRight() {\\n        return this.move(this._turnRight.bind(this))\\n    }\\n\\n    move(func) {\\n        if (this.status === 'gameover') return false\\n        const fixedBlocks = this.blocks.filter(b =\u003e b.state === 'fixed')\\n        const movingBlocks = this.blocks.filter(b =\u003e b.state === 'moving')\\n        const bool = movingBlocks.every(b =\u003e {\\n            const pos = func(b)\\n            return this._isValidPos(pos.x, pos.y) \u0026\u0026 !fixedBlocks.some(target =\u003e {\\n                return target.x == pos.x \u0026\u0026 target.y == pos.y\\n            })\\n        })\\n        if (bool) {\\n            movingBlocks.forEach(b =\u003e {\\n                const pos = func(b)\\n                b.x = pos.x\\n                b.y = pos.y\\n            })\\n        }\\n        return bool\\n    }\\n\\n    eraseLines() {\\n        for (let y=0; y\u003cthis.height; y++) {\\n            let row = this.blocks.filter(b =\u003e b.y === y)\\n            if (row.length === this.width) {\\n                this.blocks = this.blocks.filter(b =\u003e b.y !== y)\\n                this.blocks.filter(b =\u003e b.y \u003c y).forEach(b =\u003e b.y++)\\n                this.scores++\\n            }\\n        }\\n    }\\n\\n    _moveDown(b) {\\n        return { x: b.x, y: b.y + 1 }\\n    }\\n\\n    _moveRight(b) {\\n        return { x: b.x + 1, y: b.y }\\n    }\\n\\n    _moveLeft(b) {\\n        return { x: b.x - 1, y: b.y }\\n    }\\n\\n    _turnRight (b) {\\n        let vx = b.x - this.posX\\n        let vy = b.y - this.posY\\n        if (vx*vy !== 0 || vx === 0) vy *= -1\\n        return {\\n            x: this.posX + vy,\\n            y: this.posY + vx,\\n        }\\n    }\\n\\n    _isValidPos(x, y) {\\n        return y \u003e= 0 \u0026\u0026 y \u003c this.height \u0026\u0026\\n               x \u003e= 0 \u0026\u0026 x \u003c this.width\\n    }\\n}\\n\\nclass Renderer {\\n\\n    constructor(canvasId, gameInstance, size = 25) {\\n\\n        const canvas = document.getElementById(canvasId) \\n        canvas.width = size * gameInstance.width\\n        canvas.height = size * gameInstance.height\\n\\n        this.ctx = canvas.getContext('2d')\\n        this.size = size\\n        this.game = gameInstance\\n    }\\n\\n    render = () =\u003e {\\n\\n        this._clear()\\n\\n        this.game.blocks.forEach(this._drawRect)\\n        this.game.blocks.forEach(this._drawRectStroke)\\n\\n        this.ctx.scale(0.3, 0.3)\\n        this.game.nextBlock.block.forEach(this._drawRect)\\n        this.game.nextBlock.block.forEach(this._drawRectStroke)\\n\\n        this.ctx.setTransform(1, 0, 0, 1, 0, 0)\\n\\n        this._drawText()\\n    }\\n\\n    _clear = () =\u003e {\\n        this.ctx.fillStyle = '#222222'\\n        this.ctx.fillRect(0, 0, this.size * 10, this.size * 20)\\n    }\\n\\n    _drawRect = (b) =\u003e {\\n        const { size, ctx, game } = this\\n        ctx.fillStyle = game.status === 'gameover' ? '#666' : b.color\\n        ctx.fillRect(b.x * size, b.y * size, size, size)\\n    }\\n\\n    _drawRectStroke = (b) =\u003e {\\n        const { size, ctx } = this\\n        ctx.lineWidth = 2\\n        ctx.strokeStyle = '#111111'\\n        ctx.beginPath()\\n        ctx.rect(b.x * size, b.y * size, size, size)\\n        ctx.stroke()\\n    }\\n\\n    _drawText = () =\u003e {\\n        const { size, ctx, game } = this\\n        ctx.fillStyle = '#ffffff';\\n        ctx.textAlign = 'end'\\n        ctx.font = '20px Comic Sans MS';\\n        ctx.fillText(game.scores, game.width * size - 10, 25);\\n    }\\n}\\n\\nfunction undoWrapper(game) {\\n\\n    const snapshot = []\\n    const actions = []\\n\\n    function undo(i = 1) {\\n        if (i \u003c= 0) return\\n        const data = snapshot.splice(0, i).pop()\\n        if (data) {\\n            let d = JSON.parse(data)\\n            game.blocks = d.blocks\\n            game.scores = d.scores\\n            game.status = d.status\\n            game.nextBlock = d.nextBlock\\n        }\\n        actions.splice(0, i)\\n    }\\n\\n    function decorator(method, action) {\\n        return function () {\\n            snapshot.unshift(JSON.stringify({\\n                blocks: game.blocks,\\n                scores: game.scores,\\n                status: game.status,\\n                nextBlock: game.nextBlock,\\n            }))\\n            actions.unshift(action)\\n            let bool = method.call(game)\\n            if (bool === false) {\\n                snapshot.splice(0, 1)\\n                actions.splice(0, 1)\\n            }\\n            return bool\\n        }\\n    }\\n\\n    function clearAllActions() {\\n        actions.length = 0\\n        snapshot.length = 0\\n    }\\n\\n    game.moveRight = decorator(game.moveRight, 'R')\\n    game.moveLeft = decorator(game.moveLeft, 'L')\\n    game.turnRight = decorator(game.turnRight, 'T')\\n    game.moveDownToEnd = decorator(game.moveDownToEnd, 'D')\\n    game.snapshot = snapshot\\n    game.actions = actions\\n    game.undo = undo\\n    game.clearAllActions = clearAllActions\\n    \\n    return game\\n}\\n\\nlet bestScore = 0\\nlet bestActions = ''\\n\\nfunction AI(game) {\\n    bestScore = 0\\n    game.clearAllActions()\\n    search(game, 2)\\n    return bestActions\\n}\\n\\nfunction search(game, depth = 2) {\\n\\n    let step, turnStep\\n    \\n    for (turnStep = 0; turnStep \u003c 4; turnStep++) {\\n        \\n        game.moveDownToEnd()\\n        evaluation(game, depth - 1)\\n        game.undo()\\n\\n        step = 0\\n        while (game.moveRight()) {\\n            step++\\n            game.moveDownToEnd()\\n            evaluation(game, depth - 1)\\n            game.undo()\\n        }\\n        game.undo(step)\\n\\n        step = 0\\n        while (game.moveLeft()) {\\n            step++\\n            game.moveDownToEnd()\\n            evaluation(game, depth - 1)\\n            game.undo()\\n        }\\n        game.undo(step)\\n\\n        if (game.turnRight() === false) break\\n    }\\n\\n    game.undo(turnStep)\\n}\\n\\n\\nfunction evaluation(game, depth) {\\n\\n    if (depth \u003e 0) return search(game, depth)\\n\\n    let score = 0\\n    let grid = game.getGrid()\\n    \\n\\n    for (let y = 0; y \u003c 20; y++) {\\n        for (let x = 0; x \u003c 10; x++) {\\n            score += 20\\n            if (grid[y][x] == '*') {\\n                score -= (20 - y)\\n            } else {\\n                if (x \u003e 0 \u0026\u0026 grid[y][x - 1] == '*') score -= 10\\n                if (x \u003c 9 \u0026\u0026 grid[y][x + 1] == '*') score -= 20\\n                if (y \u003e 0 \u0026\u0026 grid[y - 1][x] == '*') score -= 50\\n                if (y \u003c 19 \u0026\u0026 grid[y + 1][x] == '*') score -= 10\\n            }\\n\\n        }\\n    }\\n\\n    if (score \u003e bestScore) {\\n        bestScore = score\\n        bestActions = game.actions.slice() // shallow clone\\n    }\\n}\\n\\nconst game = undoWrapper(new Tetris())\\nconst renderer = new Renderer('stage', game)\\n        \\nlet actions = []\\nlet timer = 0\\n        \\nfunction gameloop () {\\n    timer++\\n    if (timer % 1 == 0) {\\n        if (actions.length \u003c= 0) {\\n            actions = AI(game)\\n        } else {\\n            let a = actions.pop()\\n            if (a === 'R') game.moveRight()\\n            if (a === 'L') game.moveLeft()\\n            if (a === 'T') game.turnRight()\\n            if (a === 'D') game.moveDownToEnd()\\n            if (a === 'D') actions = []\\n        }\\n    }\\n            \\n    renderer.render()\\n    requestAnimationFrame(gameloop)\\n}\\ngameloop()\\n\\ndocument.addEventListener('keydown', (e) =\u003e {\\n    if (e.keyCode === 40) game.moveDownToEnd()\\n    if (e.keyCode === 37) game.moveLeft()\\n    if (e.keyCode === 39) game.moveRight()\\n    if (e.keyCode === 38) game.turnRight()\\n})\"}","created_at":"2021-09-17T20:10:33.082+08:00","updated_at":"2021-09-17T20:14:04.956+08:00","name":"Tetris AI","language":"web","screenshot":{"url":null},"parent_id":3,"plugin":"","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":181,"hashid":"p93skv3n9","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}