摘要:實(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
摘要:實(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 編...
摘要:探探機(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 先看一下...
摘要:實(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)大自己啦!!...
摘要:實(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)大自己啦??!...
閱讀 794·2019-08-30 15:55
閱讀 1538·2019-08-30 15:52
閱讀 2699·2019-08-30 15:44
閱讀 2112·2019-08-30 11:14
閱讀 2631·2019-08-29 13:59
閱讀 1832·2019-08-29 13:45
閱讀 1018·2019-08-29 13:21
閱讀 3381·2019-08-26 13:31