西洋棋AI 副本 | JavaScript 程式專案

{"id":119435,"student_id":1404,"content":"function AI () {\n    var result = minimax(4, 'b');\n    //執行最佳步驟\n    chess.move(result.from_x, result.from_y, result.to_x, result.to_y);\n}\n// function AI () {\n//     var result = minimax(4, 'b');\n//     chess.move(result.fromX, result.fromY, result.toX, result.toY);\n// }\n\nfunction minimax (depth, turn) {\n    var best_score = turn == 'b' ? -Infinity : Infinity;\n    var from_x = -1;\n    var from_y = -1;\n    var to_x = -1;\n    var to_y = -1;\n    // 雙層迴圈跑整個盤面的格子，找出最佳步驟\n    for (var x = 0; x \u003c 8; x++) {\n        for (var y = 0; y \u003c 8; y++) {\n            var available_choices = chess.getSteps(x, y); //(x,y)格可前進的格子，是一個 array of object\n            for (var i = 0; i \u003c available_choices.length; i++) {\n                chess.move(x, y, available_choices[i].x, available_choices[i].y)\n                \n                var score = -1;\n                if(depth \u003e 0){\n                    score = minimax(depth-1, turn == 'b' ? 'w' : 'b').score\n                }else{\n                    score = evaluation(chess.grid);\n                }\n                \n                if(turn == 'b' \u0026\u0026 score \u003e best_score){\n                    best_score = score;\n                    from_x = x;\n                    from_y = y;\n                    to_x = available_choices[i].x;\n                    to_y = available_choices[i].y;\n                }\n                if(turn == 'w' \u0026\u0026 score \u003c best_score){\n                    best_score = score;\n                    from_x = x;\n                    from_y = y;\n                    to_x = available_choices[i].x;\n                    to_y = available_choices[i].y;\n                }\n                \n                // chess.move(available_choices[i].x, available_choices[i].y, x, y);\n                chess.undo();\n            }\n        }\n    }\n    return {\n        from_x: from_x,\n        from_y: from_y,\n        to_x: to_x,\n        to_y: to_y,\n        score: best_score\n    }\n}\n\n// function minimax (depth, turn) {\n//     var fromX;\n//     var fromY;\n//     var toX;\n//     var toY;\n//     var bestScore = turn == 'b' ? -Infinity : Infinity;\n    \n//     for (var x=0; x\u003c8; x++) {\n//         for (var y=0; y\u003c8; y++) {\n//             var steps = chess.getSteps(x, y);\n//             for (var i=0; i\u003csteps.length; i++) {\n//                 var pos = steps[i];\n//                 chess.move(x, y, pos.x, pos.y);\n//                 if (depth \u003e 0) {\n//                     var score = minimax(depth - 1, turn == 'b' ? 'w' : 'b').score;\n//                 } else {\n//                     var score = evaluation(chess.grid)\n//                 }\n\n//                 if (turn == 'b' \u0026\u0026 score \u003e bestScore) {\n//                     bestScore = score;\n//                     fromX = x;\n//                     fromY = y;\n//                     toX = pos.x;\n//                     toY = pos.y;\n//                 }\n                \n//                 if (turn == 'w' \u0026\u0026 score \u003c bestScore) {\n//                     bestScore = score;\n//                     fromX = x;\n//                     fromY = y;\n//                     toX = pos.x;\n//                     toY = pos.y;\n//                 }\n    \n//                 chess.undo();\n//             }\n//         }\n//     }\n    \n//     return {\n//         fromX: fromX,\n//         fromY: fromY,\n//         toX: toX,\n//         toY: toY,\n//         score: bestScore,\n//     }\n// }\n\n\n\n\n\n//測試：主控台輸入  evaluation(chess.grid) =\u003e 0\n// function evaluation (grid) {\n//     var points = 0;\n//     // for 迴圈去看盤面每一格的棋子是什麼，\n//     // 決定加幾分或扣幾分\n//     for (var x = 0; x \u003c 8; x++) {\n//         for (var y = 0; y \u003c 8; y++) {\n//             // console.log( x + \" \" + y + \" \" + grid[x][y])\n//             if (grid[x][y] == 'b_pawn') points += 10;\n//             if (grid[x][y] == 'b_knight') points += 30;\n//             if (grid[x][y] == 'b_bishop') points += 30;\n//             if (grid[x][y] == 'b_rook') points += 50;\n//             if (grid[x][y] == 'b_queen') points += 300;\n//             if (grid[x][y] == 'b_king') points += 1000;\n\n//             if (grid[x][y] == 'w_pawn') points -= 10;\n//             if (grid[x][y] == 'w_knight') points -= 30;\n//             if (grid[x][y] == 'w_bishop') points -= 30;\n//             if (grid[x][y] == 'w_rook') points -= 50;\n//             if (grid[x][y] == 'w_queen') points -= 300;\n//             if (grid[x][y] == 'w_king') points -= 1000;\n//         }\n//     }\n//     return points;\n// };\n\nfunction evaluation (grid) {\n    var points = 0;\n    for (var x = 0; x \u003c 8; x++) {\n        for (var y = 0; y \u003c 8; y++) {\n            if (grid[x][y] == 'b_pawn') points += 10;\n            if (grid[x][y] == 'b_knight') points += 30;\n            if (grid[x][y] == 'b_bishop') points += 30;\n            if (grid[x][y] == 'b_rook') points += 50;\n            if (grid[x][y] == 'b_queen') points += 300;\n            if (grid[x][y] == 'b_king') points += 1000;\n\n            if (grid[x][y] == 'w_pawn') points -= 10;\n            if (grid[x][y] == 'w_knight') points -= 30;\n            if (grid[x][y] == 'w_bishop') points -= 30;\n            if (grid[x][y] == 'w_rook') points -= 50;\n            if (grid[x][y] == 'w_queen') points -= 300;\n            if (grid[x][y] == 'w_king') points -= 1000;\n        }\n    }\n    return points;\n};\n\n\n\n\n// //遞迴練習\n// //遞迴 (Recursive) 是程式中包含自我呼叫 (self-calling)。\n\n// // fractional(5); =\u003e 5*4*3*2*1\n// // fractional(8); =\u003e 8*7*6*5*4*3*2*1\n// function fractional(n){\n//     if(n == 1){\n//         return 1\n//     }\n//     else{\n//         return n * times(n-1)\n//     }\n// }\n\n\n// // 1, 1, 2, 3, 5, 8, 13, 21, 34.....\n// //fib(5) =\u003e 5\n// //fib(8) =\u003e 21\n// function fib(n){\n//     if(n == 1 || n == 2){\n//         return 1;\n//     }else{\n//         return fib(n-1) + fib(n-2);\n//     }\n// }\n\n\n// //最大公因數 Greatest Common Divisor\n// function GCD(a, b){\n//     if(a \u003e b){\n//         var remainder = a % b\n//         if(remainder ==0){\n//             return b\n//         }else{\n//             return GCD(remainder, b)\n//         }\n//     }else{\n//         var remainder = b % a\n//         if(remainder ==0){\n//             return a\n//         }else{\n//             return GCD(remainder, a)\n//         }\n//     }\n// }\n\n\n\n\n\n\n\n\n\n\n\n","created_at":"2020-01-12T09:39:25.771+08:00","updated_at":"2020-08-15T18:03:42.051+08:00","name":"西洋棋AI 副本","language":"javascript","screenshot":{"url":"https://cdn6.koding.school/uploads/project/screenshot/119435/3ef588b41505c20ce7c45b2a058e4df3.jpg"},"parent_id":52797,"plugin":"// noprotect\nvar chess = (function () {\n    \n    let instance = {\n        // w、b 表示當前回合下棋的顏色，遊戲開始白色先下\n        turn: 'w',\n        message: '',\n        gameOver: false,\n    };\n    \n    // 選定移動的格子\n    let focusOn = {\n        x: undefined,\n        y: undefined,\n    }\n    \n    // 紀錄所有的移動，在 undo 返回時調用\n    let logs = [];\n    \n    // 存放棋盤格子角色\n    let board = [[], [], [], [], [], [], [], []]; \n    \n    // 存放棋子角色\n    let chessman = [[], [], [], [], [], [], [], []];\n    \n    // 角色造型編號與名稱對照表\n    let chessmanCostumeIds = [\n        'b_rook', // 0\n        'b_knight', // 1\n        'b_bishop', // 2\n        'b_king', // 3\n        'b_queen', // 4\n        'b_pawn', // 5\n        'w_rook', // 6\n        'w_knight', // 7\n        'w_bishop', // 8\n        'w_king', // 9\n        'w_queen', // 10\n        'w_pawn', // 11\n    ];\n    \n    // 初始棋子的位置\n    let grid = [\n        ['b_rook',   'b_pawn', '', '', '', '', 'w_pawn',   'w_rook'],\n        ['b_knight', 'b_pawn', '', '', '', '', 'w_pawn', 'w_knight'],\n        ['b_bishop', 'b_pawn', '', '', '', '', 'w_pawn', 'w_bishop'],\n        ['b_king',   'b_pawn', '', '', '', '', 'w_pawn',   'w_king'],\n        ['b_queen',  'b_pawn', '', '', '', '', 'w_pawn',  'w_queen'],\n        ['b_bishop', 'b_pawn', '', '', '', '', 'w_pawn', 'w_bishop'],\n        ['b_knight', 'b_pawn', '', '', '', '', 'w_pawn', 'w_knight'],\n        ['b_rook',   'b_pawn', '', '', '', '', 'w_pawn',   'w_rook'],\n    ];\n    \n    // 初始化棋盤格子\n    for (let x = 0; x \u003c 8; x++) {\n        for (let y = 0; y \u003c 8; y++) {\n            let block = createSprite(['dark.jpg', 'light.jpg', 'red.jpg', 'blue.jpg']);\n            block.x = 120 + 50*x + 25;\n            block.y = 40  + 50*y + 25;\n            block.scale = .5;\n            board[x][y] = block;\n            \n            block.on('click', function () {\n                if (instance.gameOver) return;\n                if (focusOn.x === undefined \u0026\u0026 grid[x][y][0] === instance.turn) {\n                    focusOn.x = x;\n                    focusOn.y = y;\n                    block.costumeId = 3;\n                    // 將可移動到的格子上色\n                    getSteps(x, y).forEach((pos) =\u003e {\n                        board[pos.x][pos.y].costumeId = 2; // 上紅色\n                    });\n                } else {\n                    if (board[x][y].costumeId === 2) {\n                        move(focusOn.x, focusOn.y, x, y);\n                        \n                         // 暫時插在這裏\n                        setTimeout(function() {\n                            var startTime = Date.now();\n                            instance.message = 'thinking';\n                            if (window.AI) AI();\n                            if (!instance.gameOver)\n                                instance.message = 'Cost: ' + (Date.now() - startTime)/1000 + 's'\n                        }, 300);\n                    }\n                    focusOn.x = undefined;\n                    focusOn.y = undefined;\n                    clearBoardColor();\n                }\n            });\n        }\n    }\n    clearBoardColor(); // 重置棋盤的顏色\n    \n    // 初始化棋盤角色\n    for (let x = 0; x \u003c 8; x++) {\n        for (let y = 0; y \u003c 8; y++) {\n            let costumes = [];\n            for (let i=0; i\u003cchessmanCostumeIds.length; i++) {\n                costumes.push(chessmanCostumeIds[i] + '.png');\n            }\n            let piece = createSprite(costumes);\n            piece.scale = .2;\n            piece.x = 120 + 50*x + 25;\n            piece.y = 40 + 50*y + 25;\n            chessman[x][y] = piece;\n        }\n    }\n    \n    // 監聽 grid 二維陣列的狀態並即時反應在遊戲畫面上\n    forever(function() {\n        for (let x = 0; x \u003c 8; x++) {\n            for (let y = 0; y \u003c 8; y++) {\n                if (grid[x][y] !== '') {\n                    chessman[x][y].hidden = false;\n                    chessman[x][y].costumeId = chessmanCostumeIds.indexOf(grid[x][y]);\n                } else {\n                    chessman[x][y].hidden = true;\n                }\n            }\n        }\n        // 繪製棋盤外框\n        pen.fillColor = 'black';\n        pen.drawRect(120-2, 40-2, 400+4, 400+4);\n        // 顯示花費時間＆遊戲狀態\n        print(instance.message, 320 - instance.message.length*3.5, 15);\n    });\n    \n    // 清除棋盤上提示的顏色格子\n    function clearBoardColor () {\n        for (let x = 0; x \u003c 8; x++) {\n            for (let y = 0; y \u003c 8; y++) {\n                board[x][y].costumeId = (x + y)%2;\n            }\n        }\n    }\n    \n    // 返回 x, y 格子的棋子能到達的所有格子位置\n    function getSteps(x, y) {\n        if (grid[x][y] == undefined || grid[x][y][0] !== instance.turn || instance.gameOver) return [];\n    \n        if (grid[x][y] == 'b_rook' || grid[x][y] == 'w_rook') return rookSteps(x, y);\n        if (grid[x][y] == 'b_knight' || grid[x][y] == 'w_knight') return knightSteps(x, y);\n        if (grid[x][y] == 'b_bishop' || grid[x][y] == 'w_bishop') return bishopSteps(x, y);\n        if (grid[x][y] == 'b_king' || grid[x][y] == 'w_king') return kingSteps(x, y);\n        if (grid[x][y] == 'b_queen' || grid[x][y] == 'w_queen') return queenSteps(x, y);\n        if (grid[x][y] == 'b_pawn' || grid[x][y] == 'w_pawn') return pawnSteps(x, y);\n        return [];\n    }\n    \n    function knightSteps (x, y) {\n        let result = [];\n        [\n            { x:  2, y:  1 },\n            { x: -2, y: -1 },\n            { x:  1, y:  2 },\n            { x: -1, y: -2 },\n            { x: -1, y:  2 },\n            { x:  1, y: -2 },\n            { x: -2, y:  1 },\n            { x:  2, y: -1 },\n        ].forEach((pos) =\u003e {\n            let xx = pos.x + x;\n            let yy = pos.y + y;\n            if (xx \u003c 0 || yy \u003c 0 || xx \u003e= 8 || yy \u003e= 8) return;\n            if (grid[xx][yy][0] === instance.turn) return;\n            result.push({ x: xx, y: yy });\n        });\n        return result;\n    }\n    \n    function bishopSteps (x, y) {\n        return lineSteps(x, y, 1, -1)\n        .concat(lineSteps(x, y, -1, 1))\n        .concat(lineSteps(x, y, 1, 1))\n        .concat(lineSteps(x, y, -1, -1))\n    }\n    \n    function rookSteps (x, y) {\n        return lineSteps(x, y, 0, -1)\n        .concat(lineSteps(x, y, 0, 1))\n        .concat(lineSteps(x, y, 1, 0))\n        .concat(lineSteps(x, y, -1, 0))\n    }\n    \n    function queenSteps (x, y) {\n        return rookSteps(x, y).concat(bishopSteps(x, y));\n    }\n    \n    function kingSteps (x, y) {\n        let result = [];\n        [\n            { x: -1, y: -1 },\n            { x:  0, y: -1 },\n            { x:  1, y: -1 },\n            { x: -1, y:  0 },\n            { x:  1, y:  0 },\n            { x: -1, y:  1 },\n            { x:  0, y:  1 },\n            { x:  1, y:  1 }\n        ].forEach((pos) =\u003e {\n                let xx = pos.x + x;\n                let yy = pos.y + y;\n                if (xx \u003c 0 || yy \u003c 0 || xx \u003e= 8 || yy \u003e= 8) return;\n                if (grid[xx][yy][0] === instance.turn) return;\n                result.push({\n                    x: xx, y: yy\n                });\n            });\n        return result;\n    }\n    \n    function pawnSteps (x, y) {\n        let result = [];\n        if (instance.turn === 'b') {\n            if (grid[x][y + 1] === '') {\n                result.push({x: x, y: y + 1});\n                if (y == 1 \u0026\u0026 grid[x][y + 2] === '') result.push({x: x, y: y + 2});\n            }\n            if (x + 1 \u003c= 7 \u0026\u0026 grid[x + 1][y + 1][0] == 'w') result.push({x: x+1, y: y + 1});\n            if (x - 1 \u003e= 0 \u0026\u0026 grid[x - 1][y + 1][0] == 'w') result.push({x: x-1, y: y + 1});\n        } else {\n            if (grid[x][y - 1] === '') {\n                result.push({x: x, y: y - 1});\n                if (y == 6 \u0026\u0026 grid[x][y - 2] === '') result.push({x: x, y: y - 2});\n            }\n            if (x + 1 \u003c= 7 \u0026\u0026 grid[x + 1][y - 1][0] == 'b') result.push({x: x+1, y: y - 1});\n            if (x - 1 \u003e= 0 \u0026\u0026 grid[x - 1][y - 1][0] == 'b') result.push({x: x-1, y: y - 1});\n        }\n        return result;\n    }\n    \n    function lineSteps (x, y, offsetX, offsetY) {\n        let result = [];\n        for (let i = 1; i \u003c 8; i++) {\n            let xx = x + i*offsetX;\n            let yy = y + i*offsetY;\n            if (xx \u003c 0 || yy \u003c 0 || xx \u003e= 8 || yy \u003e= 8) break;\n            if (grid[xx][yy] !== '') {\n                if (grid[xx][yy][0] !== instance.turn) {\n                    result.push({ x: xx, y: yy });\n                }\n                break;\n            }\n            result.push({ x: xx, y: yy });\n        }\n        return result;\n    }\n    \n    // 角色移動\n    function move (fromX, fromY, toX, toY) {\n        logs.push(['move', fromX, fromY, toX, toY, grid[toX][toY]]);\n        checkIsGameOver(toX, toY);\n        grid[toX][toY] = grid[fromX][fromY];\n        grid[fromX][fromY] = '';\n        chackIsPromotion(toX, toY);\n        instance.turn = instance.turn === 'b' ? 'w' : 'b';\n    }\n    \n    // 判斷遊戲是否將軍\n    function checkIsGameOver (toX, toY) {\n        if (grid[toX][toY] === 'b_king') {\n            instance.gameOver = true;\n            instance.message = 'White is Winner';\n            logs.push(['gameOver']);\n        }\n        if (grid[toX][toY] === 'w_king') {\n            instance.gameOver = true;\n            instance.message = 'Black is Winner';\n            logs.push(['gameOver']);\n        }\n    }\n    \n    // 判斷是否升變\n    function chackIsPromotion (toX, toY) {\n        if (toY === 7 \u0026\u0026 grid[toX][toY] === 'b_pawn') {\n            grid[toX][toY] = 'b_queen';\n            logs.push(['promotion', toX, toY]);\n        }\n        if (toY === 0 \u0026\u0026 grid[toX][toY] === 'w_pawn') {\n            grid[toX][toY] = 'w_queen';\n            logs.push(['promotion', toX, toY]);\n        }\n    }\n    \n    // 返回上一個動作\n    function undo () {\n        if (logs.length \u003c= 0) return;\n        let action = logs.pop();\n        if (action[0] === 'move') {\n            grid[action[1]][action[2]] = grid[action[3]][action[4]];\n            grid[action[3]][action[4]] = action[5]; \n            instance.turn = instance.turn === 'b' ? 'w' : 'b';\n        }\n        if (action[0] === 'promotion') {\n            let x = action[1];\n            let y = action[2];\n            if (y === 0) grid[x][y] = 'w_pawn';\n            if (y === 7) grid[x][y] = 'b_pawn';\n            undo(); // 升變與移動是同一個回合\n        }\n        if (action[0] === 'gameOver') {\n            instance.gameOver = false;\n            undo();\n        }\n    }\n    \n    // 開放介面\n    instance.grid = grid;\n    instance.move = move;\n    instance.undo = undo;\n    instance.getSteps = getSteps;\n    \n    return instance;\n\n})();\n","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":67,"hashid":"qmdsp6q2","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}

[{"id":2051929,"file_name":"b_bishop.png","project_id":119435,"asset_id":105414,"created_at":"2020-01-12T09:39:25.777+08:00","updated_at":"2020-01-12T09:39:25.777+08:00"},{"id":2051930,"file_name":"b_king.png","project_id":119435,"asset_id":105413,"created_at":"2020-01-12T09:39:25.779+08:00","updated_at":"2020-01-12T09:39:25.779+08:00"},{"id":2051931,"file_name":"b_knight.png","project_id":119435,"asset_id":105412,"created_at":"2020-01-12T09:39:25.780+08:00","updated_at":"2020-01-12T09:39:25.780+08:00"},{"id":2051932,"file_name":"b_pawn.png","project_id":119435,"asset_id":105411,"created_at":"2020-01-12T09:39:25.781+08:00","updated_at":"2020-01-12T09:39:25.781+08:00"},{"id":2051933,"file_name":"b_queen.png","project_id":119435,"asset_id":105410,"created_at":"2020-01-12T09:39:25.782+08:00","updated_at":"2020-01-12T09:39:25.782+08:00"},{"id":2051934,"file_name":"b_rook.png","project_id":119435,"asset_id":105409,"created_at":"2020-01-12T09:39:25.783+08:00","updated_at":"2020-01-12T09:39:25.783+08:00"},{"id":2051935,"file_name":"w_bishop.png","project_id":119435,"asset_id":105408,"created_at":"2020-01-12T09:39:25.785+08:00","updated_at":"2020-01-12T09:39:25.785+08:00"},{"id":2051936,"file_name":"w_king.png","project_id":119435,"asset_id":105407,"created_at":"2020-01-12T09:39:25.786+08:00","updated_at":"2020-01-12T09:39:25.786+08:00"},{"id":2051937,"file_name":"w_knight.png","project_id":119435,"asset_id":105406,"created_at":"2020-01-12T09:39:25.787+08:00","updated_at":"2020-01-12T09:39:25.787+08:00"},{"id":2051938,"file_name":"w_pawn.png","project_id":119435,"asset_id":105405,"created_at":"2020-01-12T09:39:25.788+08:00","updated_at":"2020-01-12T09:39:25.788+08:00"},{"id":2051939,"file_name":"w_queen.png","project_id":119435,"asset_id":105404,"created_at":"2020-01-12T09:39:25.790+08:00","updated_at":"2020-01-12T09:39:25.790+08:00"},{"id":2051940,"file_name":"w_rook.png","project_id":119435,"asset_id":105403,"created_at":"2020-01-12T09:39:25.791+08:00","updated_at":"2020-01-12T09:39:25.791+08:00"},{"id":2051941,"file_name":"red.jpg","project_id":119435,"asset_id":105402,"created_at":"2020-01-12T09:39:25.792+08:00","updated_at":"2020-01-12T09:39:25.792+08:00"},{"id":2051942,"file_name":"blue.jpg","project_id":119435,"asset_id":105401,"created_at":"2020-01-12T09:39:25.793+08:00","updated_at":"2020-01-12T09:39:25.793+08:00"},{"id":2051943,"file_name":"dark.jpg","project_id":119435,"asset_id":105400,"created_at":"2020-01-12T09:39:25.795+08:00","updated_at":"2020-01-12T09:39:25.795+08:00"},{"id":2051944,"file_name":"light.jpg","project_id":119435,"asset_id":105399,"created_at":"2020-01-12T09:39:25.796+08:00","updated_at":"2020-01-12T09:39:25.796+08:00"}]