国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

手把手教你用 JavaScript 實(shí)現(xiàn)一個(gè)簡(jiǎn)單的國(guó)際象棋 AI

baihe / 2915人閱讀

摘要:實(shí)現(xiàn)這一功能最簡(jiǎn)單的方法是計(jì)算棋盤(pán)上棋子的相對(duì)強(qiáng)度大小,用下面的對(duì)照表。本鏈接是基于算法優(yōu)化的國(guó)際象棋。我們來(lái)稍微調(diào)整一下棋盤(pán)上棋子狀態(tài)的權(quán)重,這一圖表是在國(guó)際象棋程序維基百科中給出的。

本文作者: Lauri Hartikka
編譯:胡子大哈

翻譯原文:http://huziketang.com/blog/posts/
英文連接:A step-by-step guide to building a simple chess AI

轉(zhuǎn)載請(qǐng)注明出處,保留原文鏈接以及作者信息

首先讓我們先看幾個(gè)對(duì)開(kāi)發(fā)簡(jiǎn)單國(guó)際象棋 AI 很有幫助的概念:

移動(dòng)生成

局面評(píng)估

極大極小算法

α-β 剪枝

每一步中我們都會(huì)對(duì)經(jīng)過(guò)時(shí)間檢驗(yàn)的國(guó)際象棋程序進(jìn)行改進(jìn),我會(huì)展示不同算法風(fēng)格所產(chǎn)生的影響。你也可以在 GitHub 上看到最終的 AI 算法。

步驟 1:移動(dòng)生成和棋盤(pán)可視化

使用 chess.js 庫(kù)來(lái)生成移動(dòng)規(guī)則,使用 chessboard.js 來(lái)可視化棋盤(pán)。移動(dòng)生成庫(kù)實(shí)現(xiàn)了所有國(guó)際象棋的規(guī)則,對(duì)于任意給定的棋盤(pán)狀態(tài)我們都可以計(jì)算出下一步的合法的走棋方法。

(移動(dòng)生成函數(shù)的可視化版本。起始位置作為輸入,輸出是所有可能的走法。)

使用這些庫(kù)可以使我們專(zhuān)注于我們所感興趣的任務(wù):開(kāi)發(fā)最佳下棋的算法。我們首先從創(chuàng)建以一個(gè)函數(shù)開(kāi)始,在所有可能走法中返回一個(gè)隨機(jī)的結(jié)果。

    var calculateBestMove =function(game) {
        //generate all the moves for a given position
        var newGameMoves = game.ugly_moves();
        return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
    };

用這種方法,盡管它不是一個(gè)合格的棋手,但是起碼我們可以和它玩起來(lái)了。

步驟 2:位置評(píng)估

下面我們?cè)囍屗斫庠谝粋€(gè)確定的位置上怎么走比較好。實(shí)現(xiàn)這一功能最簡(jiǎn)單的方法是計(jì)算棋盤(pán)上棋子的相對(duì)強(qiáng)度大小,用下面的對(duì)照表。

通過(guò)評(píng)估函數(shù),可以選擇評(píng)估結(jié)果最佳的走法。

    var calculateBestMove = function (game) {
    
        var newGameMoves = game.ugly_moves();
        var bestMove = null;
        //use any negative large number
        var bestValue = -9999;
    
        for (var i = 0; i < newGameMoves.length; i++) {
            var newGameMove = newGameMoves[i];
            game.ugly_move(newGameMove);
    
            //take the negative as AI plays as black
            var boardValue = -evaluateBoard(game.board())
            game.undo();
            if (boardValue > bestValue) {
                bestValue = boardValue;
                bestMove = newGameMove
            }
        }
    
        return bestMove;
    
    };

這樣一來(lái),一個(gè)切實(shí)的改善是,算法會(huì)吃掉它可以吃掉的棋子。

(黑子使用了簡(jiǎn)單評(píng)估算法,在這里可以看到:https://jsfiddle.net/lhartikk...)

步驟 3:用極大極小算法搜索樹(shù)

接下來(lái)我們來(lái)創(chuàng)建一個(gè)搜索樹(shù),通過(guò)它算法可以選擇最佳走法,這里需要用到極大極小算法。

在這個(gè)算法中,會(huì)根據(jù)給定的樹(shù)深度對(duì)遞歸樹(shù)進(jìn)行遍歷,所要評(píng)估的狀態(tài)就是樹(shù)的葉子節(jié)點(diǎn)。

這一步完成以后我們把子節(jié)點(diǎn)中的最大或者最小值返回給父節(jié)點(diǎn),這要依賴(lài)于白棋還是黑棋來(lái)走這一步(這就是說(shuō)在樹(shù)的每一層中都最大或者最小化輸出)。

(給定狀態(tài)的最大最小算法的可視化。白棋最好的走法是 b2-c3,因?yàn)榭梢员WC獲取一個(gè)狀態(tài)評(píng)估值是 -50)

    var minimax = function (depth, game, isMaximisingPlayer) {
        if (depth === 0) {
            return -evaluateBoard(game.board());
        }
        var newGameMoves = game.ugly_moves();
        if (isMaximisingPlayer) {
            var bestMove = -9999;
            for (var i = 0; i < newGameMoves.length; i++) {
                game.ugly_move(newGameMoves[i]);
                bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
                game.undo();
            }
            return bestMove;
        } else {
            var bestMove = 9999;
            for (var i = 0; i < newGameMoves.length; i++) {
                game.ugly_move(newGameMoves[i]);
                bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
                game.undo();
            }
            return bestMove;
        }
    };

有了最大最小步驟以后,我們的算法可以下出一些國(guó)際象棋的基本策略了。

極大極小算法的效率取決于搜索樹(shù)的深度,這就是我們后面步驟要優(yōu)化的地方。

步驟 4:α-β 剪枝

Alpha-beta 剪枝是極大極小算法的一種優(yōu)化方法,可以砍掉搜索樹(shù)中的某些分支。這可以幫助我們用同樣的資源的情況下,盡可能深地遍歷極大極小搜索樹(shù)。

α-β 剪枝的原理是在遍歷搜索樹(shù)的過(guò)程中發(fā)現(xiàn)可以終止遍歷的狀態(tài),進(jìn)而把整個(gè)分支剪掉的過(guò)程。這是因?yàn)榘l(fā)現(xiàn)下一步會(huì)導(dǎo)致比上一步更糟的結(jié)果,那么就不用再遍歷下去了。

α-β 剪枝不影響極大極小算法的結(jié)果,僅僅是使極大極小算法運(yùn)行的更快。假設(shè)遍歷時(shí)恰巧第一個(gè)狀態(tài)就是最佳走法,那么 α-β 剪枝會(huì)更加有效。

有了 α-β,極大極小算法如虎添翼,可以看下面的例子。

(本圖是給定的起始棋盤(pán)狀態(tài),下面的數(shù)字是如果遍歷深度是 4 的話,需要評(píng)估的狀態(tài)總數(shù)。)

本鏈接是基于 α-β 算法優(yōu)化的國(guó)際象棋 AI。

步驟 5:改善評(píng)估函數(shù)

初始的評(píng)估函數(shù)非常簡(jiǎn)單,只是數(shù)了盤(pán)面上的數(shù)值而已。下面我們來(lái)改善它,把棋子的位置因素也考慮到評(píng)估結(jié)果里面去。例如在棋盤(pán)中間的馬會(huì)比在棋盤(pán)邊緣的馬位置更好(因?yàn)樗目蛇x擇性更多,也更加活躍)。

我們來(lái)稍微調(diào)整一下棋盤(pán)上棋子狀態(tài)的權(quán)重,這一圖表是在國(guó)際象棋程序維基百科中給出的。

(棋盤(pán)權(quán)值表的可視化??梢愿鶕?jù)棋子的位置增加或者減少相應(yīng)位置的權(quán)重)

通過(guò)上面的一系列改進(jìn),我們的算法可以下出像樣的棋局了,起碼開(kāi)始像一個(gè)業(yè)余棋手這樣了。

(改進(jìn)后的評(píng)估函數(shù)加上搜索樹(shù)深度設(shè)置成 3 的 α-β 算法,可以在這個(gè)地址看到:https://jsfiddle.net/q76uzxwe/1/)

總結(jié)

這個(gè)簡(jiǎn)單的國(guó)際象棋算法不會(huì)犯一些很傻的錯(cuò)誤,但是它依然是缺乏策略理解的。

通過(guò)我所介紹的這種方法,可以開(kāi)發(fā)一個(gè)國(guó)際象棋程序來(lái)實(shí)現(xiàn)一些基本的玩法?!癆I 部分”(不包括移動(dòng)生成)只有 200 行代碼,也就是說(shuō)這里只實(shí)現(xiàn)了基本的概念。你可以在 GitHub 中獲取最終版本的代碼。

關(guān)于算法的一些更深層次的改善可以見(jiàn)下面鏈接:

移動(dòng)順序

快速移動(dòng)生成策略

游戲結(jié)束策略評(píng)估

如果你想要了解更多,查看國(guó)際象棋程序維基百科,這里介紹了很多有用的資源,本文只是演示了國(guó)際象棋 AI 算法實(shí)現(xiàn)的基本步驟。

Happy Coding!如果本文對(duì)你有幫助,歡迎關(guān)注我的專(zhuān)欄-前端大哈,定期發(fā)布高質(zhì)量前端文章。


我最近正在寫(xiě)一本《React.js 小書(shū)》,對(duì) React.js 感興趣的童鞋,歡迎指點(diǎn)。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/19622.html

相關(guān)文章

  • 把手你用 JavaScript 實(shí)現(xiàn)一個(gè)簡(jiǎn)單國(guó)際象棋 AI

    摘要:實(shí)現(xiàn)這一功能最簡(jiǎn)單的方法是計(jì)算棋盤(pán)上棋子的相對(duì)強(qiáng)度大小,用下面的對(duì)照表。本鏈接是基于算法優(yōu)化的國(guó)際象棋。我們來(lái)稍微調(diào)整一下棋盤(pán)上棋子狀態(tài)的權(quán)重,這一圖表是在國(guó)際象棋程序維基百科中給出的。 showImg(https://segmentfault.com/img/remote/1460000009143081?w=2000&h=1317); 本文作者: Lauri Hartikka 編...

    NickZhou 評(píng)論0 收藏0
  • 【“探探”為例】把手你用最少代碼實(shí)現(xiàn)各種“機(jī)器人”

    摘要:探探機(jī)器人,自動(dòng)根據(jù)不同妹紙漢子顏值年齡等類(lèi)型,喜歡忽略,歡迎各位先看一下實(shí)現(xiàn)的結(jié)果吧今天要講的主題是使用腳本實(shí)現(xiàn)你自己想要自動(dòng)操控的任意手機(jī)。 前言 之前寫(xiě)了篇文章:【全是干貨】談?wù)勅绾螌W(xué)習(xí)一項(xiàng)新技能,沒(méi)有理論,全是實(shí)戰(zhàn),里面第五點(diǎn)提到用腳本玩探探,昨天花了一個(gè)小時(shí)實(shí)現(xiàn)了該功能。 Github:探探機(jī)器人,自動(dòng)根據(jù)不同妹紙/漢子顏值、年齡等類(lèi)型,喜歡、忽略,歡迎各位star 先看一下...

    worldligang 評(píng)論0 收藏0
  • 把手你用koa+mongoodb實(shí)現(xiàn)自己接口

    摘要:實(shí)際前端開(kāi)發(fā)中我們常常需要模擬數(shù)據(jù)市場(chǎng)上有許多工具提供使用但是基本都是提供數(shù)據(jù)展示如果我們想要一個(gè)具備增刪改查功能的接口怎么辦呢當(dāng)然是強(qiáng)大自己啦首先我們需要新建一個(gè)目錄安裝依賴(lài)及以上版本,首先確認(rèn)版本在以上,版本低的請(qǐng)自行搞定寫(xiě)個(gè)試 實(shí)際前端開(kāi)發(fā)中我們常常需要模擬數(shù)據(jù),市場(chǎng)上有許多工具提供使用但是基本都是提供數(shù)據(jù)展示,如果我們想要一個(gè)具備增刪改查功能的接口怎么辦呢?當(dāng)然是強(qiáng)大自己啦!!...

    ingood 評(píng)論0 收藏0
  • 把手你用koa+mongoodb實(shí)現(xiàn)自己接口

    摘要:實(shí)際前端開(kāi)發(fā)中我們常常需要模擬數(shù)據(jù)市場(chǎng)上有許多工具提供使用但是基本都是提供數(shù)據(jù)展示如果我們想要一個(gè)具備增刪改查功能的接口怎么辦呢當(dāng)然是強(qiáng)大自己啦首先我們需要新建一個(gè)目錄安裝依賴(lài)及以上版本,首先確認(rèn)版本在以上,版本低的請(qǐng)自行搞定寫(xiě)個(gè)試 實(shí)際前端開(kāi)發(fā)中我們常常需要模擬數(shù)據(jù),市場(chǎng)上有許多工具提供使用但是基本都是提供數(shù)據(jù)展示,如果我們想要一個(gè)具備增刪改查功能的接口怎么辦呢?當(dāng)然是強(qiáng)大自己啦??!...

    piapia 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<