Minimax博弈算法设计井字棋AI(Golang)
RedJACK~
帮助1人
Minimax博弈算法设计井字棋AI(Golang)
算法简介
Minimax算法即极小极大值算法，是一种回溯算法，用于决策制定和博弈论。尤其是在双人之间的零和博弈中，假定两人都是绝对理性的情况下找出最佳决策方式。他广泛应用于两人回合制游戏，例如井字棋，国际象棋等。
在 Minimax 中，两人被称为最大化者和最小化者。最大化者试图获得尽可能高的分数，而最小化者试图做相反的事情并获得尽可能低的分数。
每个棋盘状态都有一个与之关联的值。在给定的状态下，如果最大化者占上风，那么棋盘的得分将趋向于某个正值。如果最小化者在该棋盘状态下占上风，那么它往往是一些负值。棋盘的价值是通过一些启发式计算的，这些启发式对于每种类型的游戏都是独一无二的。
评价函数
func evaluate(board [][]byte) int {
var score int
// 计算得失
return score
}
对于双人零和博弈游戏来说，我必须首先制定一套根据实际状态计算双方得失的函数，我们称其为评价函数。
拿棋类游戏来举例的话，就是根据当前的棋盘状态board制定一套计算双方得失的规则，然后计算分数score返回。
minimax函数
func minimax(board [][]byte,depth int,isMax bool) int {
/*
board是当前棋盘状态
depth当前递归深度
isMax是回合布尔值
*/
// 边界条件
if /*终端状态*/ {
return /*当前状态下的评价分数值*/
}
// 决策树的遍历
if isMax {
// 最大化者的最大化评价分数的选择
score := -INFINITY
for /*当前回合的所有状态*/ {
// 状态假定选择
// 选择撤销
}
return score
} else {
// 最小化者的最小化评价分数的选择
score := INFINITY
for /*当前回合的所有状态*/ {
// 状态假定选择
// 选择撤销
}
return score
}
}
max最大化者代表我方，min最小化者代表对手。我方要尽可能令评价分数最大化，对方要尽可能令评价分数最小化。
这个函数实质上就是对决策树进行遍历，返回对我方最有利，即评价分数最高的值。
最佳走法函数
// 决策（棋法）结构体
type Move struct {
Position int
...
}
func findBestMove(board [][]byte) Move {
var bestMove Move
// 遍历当前回合的所有决策，寻找最大值
return bestMove
}
利用minima函数返回最佳决策（走法）。
数学原理
v i = m a x a i m i n a − i v i ( a i , a − i ) v_i = \mathop{max}\limits_{a_i} \ \mathop{min}\limits_{a_{-i}} \ v_i(a_i,a_{-i}) vi=aimax a−imin vi(ai,a−i)
i i i 是当前玩家索引
− i -i −i 是对手玩家索引
a i a_i ai 代表当前玩家采取的行动
a − i a_{-i} a−i 代表对手玩家采取的行动
v i v_i vi 是当前局势状态的评估价值
v i v_i vi 越是大的正数代表当前局势对于玩家 i i i 更有利， v i v_i vi 越是小的的负数代表当前局势对于玩家 − i -i −i 更有利
minimax算法伪代码
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := ∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
图解算法：实际上就是决策树的遍历过程
实例代码-Go语言
minimax算法游戏AI
package main
import "fmt"
// 走法结构体
type Move struct {
row, col int
}
// 评价函数
func evaluate(board [3][3]byte) int {
// Rows
for row := 0; row < 3; row {
if board[row][0] == board[row][1] && board[row][1] == board[row][2] {
if board[row][0] == 'x' {
return 1
}
if board[row][0] == 'o' {
return -1
}
}
}
// Colums
for col := 0; col < 3; col {
if board[0][col] == board[1][col] && board[1][col] == board[2][col] {
if board[0][col] == 'x' {
return 1
}
if board[0][col] == 'o' {
return -1
}
}
}
// Diagonals
if board[0][0] == board[1][1] && board[1][1] == board[2][2] {
if board[0][0] == 'x' {
return 1
}
if board[0][0] == 'o' {
return -1
}
}
if board[0][2] == board[1][1] && board[1][1] == board[2][0] {
if board[0][2] == 'x' {
return 1
}
if board[0][2] == 'o' {
return -1
}
}
return 0
}
// minimax函数
func minimax(board [3][3]byte, isMax bool) int {
score := evaluate(board)
if score != 0 {
return score
}
if isFull(board) {
return 0
}
if isMax {
maxVal := -10
for row := 0; row < 3; row {
for col := 0; col < 3; col {
if board[row][col] == '-' {
board[row][col] = 'x'
maxVal = max(maxVal, minimax(board, !isMax))
board[row][col] = '-'
}
}
}
return maxVal
} else {
minVal := 10
for row := 0; row < 3; row {
for col := 0; col < 3; col {
if board[row][col] == '-' {
board[row][col] = 'o'
minVal = min(minVal, minimax(board, !isMax))
board[row][col] = '-'
}
}
}
return minVal
}
}
// 最佳走法函数
func bestMove(board [3][3]byte) Move {
var move Move
move.row, move.col = -1, -1
minVal := 10
for row := 0; row < 3; row {
for col := 0; col < 3; col {
if board[row][col] == '-' {
board[row][col] = 'o'
moveVal := minimax(board, true)
board[row][col] = '-'
if moveVal < minVal {
move.row = row
move.col = col
minVal = moveVal
}
}
}
}
fmt.Println()
return move
}
// 判断是否棋盘已满
func isFull(board [3][3]byte) bool {
for row := 0; row < 3; row {
for col := 0; col < 3; col {
if board[row][col] == '-' {
return false
}
}
}
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
主程序
package main
import "fmt"
// 游戏状态结构体
type GameState struct {
board [3][3]byte
}
// 判断是否为空棋格
func isEmpty(board [3][3]byte, row, col int) bool {
if board[row][col] == '-' {
return true
}
return false
}
// 判断是否获胜
func isWin(board [3][3]byte) bool {
// Rows
for row := 0; row < 3; row {
if board[row][0] == board[row][1] && board[row][1] == board[row][2] && board[row][0] != '-' {
return true
}
}
// Colums
for col := 0; col < 3; col {
if board[0][col] == board[1][col] && board[1][col] == board[2][col] && board[0][col] != '-' {
return true
}
}
// Diagonals
if board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != '-' {
return true
}
if board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[0][2] != '-' {
return true
}
return false
}
// 判断是否游戏结束
func isEnd(board [3][3]byte) bool {
if isWin(board) {
return true
}
for row := 0; row < 3; row {
for col := 0; col < 3; col {
if isEmpty(board, row, col) {
return false
}
}
}
return true
}
// 显示棋盘状态
func showBoard(board [3][3]byte) {
for row := 0; row < 3; row {
for col := 0; col < 3; col {
fmt.Printf("%c ", board[row][col])
}
fmt.Println()
}
}
func main() {
var gs GameState
gs.board = [3][3]byte{
{'-', '-', '-'},
{'-', '-', '-'},
{'-', '-', '-'},
}
showBoard(gs.board)
var row, col int
for !isEnd(gs.board) {
fmt.Scanf("%d %d", &row, &col)
if isEmpty(gs.board, row, col) {
gs.board[row][col] = 'x'
showBoard(gs.board)
fmt.Println()
if isEnd(gs.board) {
fmt.Println("Game Over")
break
}
oMove := bestMove(gs.board)
gs.board[oMove.row][oMove.col] = 'o'
showBoard(gs.board)
fmt.Println("------------------------------------------------")
}
}
}
- - -
- - -
- - -
1 1
- - -
- x -
- - -
o - -
- x -
- - -
------------------------------------------------
2 0
o - -
- x -
x - -
o - o
- x -
x - -
------------------------------------------------
2 2
o - o
- x -
x - x
o o o
- x -
x - x
------------------------------------------------
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgfbifh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
