bash - 在 bash 中编写极小极大算法

Question

我为这个模糊的问题道歉，我完全迷失了，不知道现在出了什么问题。

我最近一直在尝试学习 bash 脚本，并决定编写一个带有 minimax 和 alpha beta 修剪的 tictactoe。我以非常 Pythonic 的方式编写了脚本，因为我对 UNIX 还是很陌生。当我尝试运行 minimax 函数时，我没有收到任何错误，但它没有输出任何内容，也没有正常退出（必须按 CTRL C）。

如果当前棋盘赢了，该函数能够告诉它赢了并返回我需要的东西。但是如果不赢，就无法下一个层次。

#!/bin/bash

declare -a board=( A1 " o" " x" " o" " o" " x" C1 C2 C3 )
shopt -s extglob


#draws the grid
draw(){
grid="| "${board[0]}" | ${board[1]} | ${board[2]} |
----------------
| ${board[3]} | ${board[4]} | ${board[5]} |
----------------
| ${board[6]} | ${board[7]} | ${board[8]} |" 

echo "$grid"
}

#test if board has a winning combination for either player
wintest(){
local testboard=("$@")
for p in " o" " x"
do
#test for vertical win
for i in $(seq 0 2) 
    do
        if [ "$p" == "${testboard[$i]}" -a "$p" == "${testboard[$(($i+3))]}" -a "$p" == "${testboard[$(($i+6))]}" ]; then
        echo 1
        fi
    done
#test for horizontal win
for i in 0 3 6 
    do  
        if [ "$p" == "${testboard[$i]}" -a "$p" == "${testboard[$i+1]}" -a "$p" == "${testboard[$i+2]}" ]; then
        echo 1
        fi
    done
#diagonal win   
if [ "$p" == "${testboard[0]}" -a "$p" == "${testboard[4]}" -a "$p" == "${testboard[8]}" ]; then
echo 1
fi
if [ "$p" == "${testboard[2]}" -a "$p" == "${testboard[4]}" -a "$p" == "${testboard[6]}" ]; then
echo 1
fi
done
}

#minimax function. parameters: player depth alpha beta board
minimax(){
if [ $1 -eq 1 ]; then
local player="1"
local p=" o"

elif [ $1 -eq 2 ]; then 
local player="2"
local p=" x"
fi

local depth=$2
local alpha=$3
local beta=$4

shift 4

#create array amove containing available moves
local boardc=("$@") 
local amove=("${boardc[@]/+(" x"|" o")}")
for i in "${!amove[@]}"; do 
if [[ -z "${amove[$i]}" ]]; then
unset amove[$i]
fi
done

#determine if anybody has won in the current board
#$player=1 is the maximing player. wintest is called on the start of the turn,
#if a winning combination exist, it belongs to the previous player

local winstat=$(wintest "${boardc[@]}")
if [ -n "$winstat" ]; then
    if [ "${player}" == 2 ]; then   
    echo "$depth"

    else  
    echo "-$depth"
    fi

else
    if [ "${player}" == 1 ]; then
    local bestval=-1000
        for i in "${amove[@]}"
        do      
            local boardcm="${boardc[@]}"    
            boardcm=("${boardcm[@]/"$i"/"$p"}")
            local value="$( minimax 2 $(( $depth+1 )) $alpha $beta "${boardcm[@]}" )"
            bestval=$(( "$bestval" > "$value" ? $bestval : "$value" ))
            alpha=$(( "$bestval" > "$alpha" ? "$bestval" : "$alpha" ))
            if [ "$beta" -le "$alpha" ] 
            then 
            break
            fi
        done
        echo "$bestval"

    elif [ "${player}" == 2 ]; then
    local bestval=1000
        for i in "${amove[@]}"
        do      
            local boardcm="${boardc[@]}"    
            boardcm=("${boardcm[@]/"$i"/"$p"}")
            local value="$( minimax 1 $(( $depth+1 )) $alpha $beta "${boardcm[@]}" )"
            bestval=$(( "$bestval" < "$value" ? "$bestval" : "$value" ))
            beta=$(( "$bestval" < "$beta" ? "$bestval" : "$beta" ))
            if [ "$beta" -le "$alpha" ]; then 
            break
            fi
        done
        echo "$bestval"
    fi
fi
}

理论上，minimax 函数应该返回一个值，该值是在当前棋盘状态下可以保证的最高（或最低，取决于玩家）值。该函数一直工作到递归发生的部分。

很抱歉无法在我的问题中更详细，我真的不知道为什么该功能不起作用

标签： bashunixminimax