how to implement the makemove function of negamax

I am currrently working on a checkers game in unity3d. I have been trying to implement a single player vs. AI for some time now using the negamax algorithm. The negamax code works well but the function that makes a temporary move on a cloned board is where am having problems. I would like to know how can do this.

Negamax functions

private static int evalBoard(checkerMan[,] board, bool turn)
{
    int whiteCount = 0;
    int blackCount = 0;
    int whoToMove;

    if (turn = boardManager.Instance.isWhiteTurn)
    {
        whoToMove = -1;
    }
    else
    {
        whoToMove = 1;
    }

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if(board[i, j]!=null)
            if (board[i, j].isWhite)
            {
                whiteCount++;
            }
            else
            {
                blackCount++;
            }
        }
    }

    return (whiteCount - blackCount) * whoToMove;
}

public List<bool[,]> getAllValidMoves(checkerMan[,] checks, bool color)
{
    List<bool[,]> validMoves = new List<bool[,]>();

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if(checks[i, j] != null && checks[i, j].isWhite==color)
            {
                if(checks[i, j].isForcedToMove())
                {
                    if checks[i, j].isKing)
                    {
                        ArrayList a = checks[i, j].kingKillMoves(i,j);
                        validMoves.Add((bool[,])a[0]);
                        checks[i, j].setMove((bool[,])a[0]);
                    }
                    else
                    {
                        validMoves.Add(checks[i, j].KillMoves(i, j));
                        checks[i, j].setMove(checks[i, j].KillMoves(i, j));
                    }
                }
                else
                {
                    if(checks[i, j].isKing)
                    {
                        validMoves.Add(checks[i, j].KingPossibleMove());
                        checks[i, j].setMove(checks[i, j].KingPossibleMove());
                    }
                    else
                    {
                        validMoves.Add(checks[i, j].possibleMove());
                        checks[i, j].setMove(checks[i, j].possibleMove());
                    }
                }
            }
        }
    }

    return validMoves;
}

private static bool[,] GetBestMove(checkerMan[,] board, bool color,int depth)
{
    aiPlaying = true;
    int highestScore = int.MinValue;
    checkerMan[,] tmp = boardManager.Instance.deppCopy(board);
    List<bool[,]>validMoves=
    boardManager.Instance.getAllValidMoves(tmp,color);
    List<bool[,]> bestMove = new List<bool[,]>();
    System.Random rand = new System.Random();

    foreach (bool[,] b in validMoves)
    {
        boardManager.Instance.applyMoves(tmp, b, color);
        int score = -NegaMax(tmp, !color, depth);
        Debug.Log("score "+score+" highestScore "+highestScore);

        if (score > highestScore)
        {
            bestMove.Clear();
            highestScore = score;
            bestMove.Add(b);
        }
        else if(score == highestScore)
        {
            bestMove.Add(b);
        }
    }

    return bestMove[rand.Next(bestMove.Count)];
}

private static int NegaMax(checkerMan[,] board, bool color, int depth)
{
    int highestScore = int.MinValue;
    List<bool[,]> validMoves = boardManager.Instance.getAllValidMoves(board, color);

    if (depth == 0 || validMoves==null)
    {
        return evalBoard(board,color);
    }

    foreach (bool[,] b in validMoves)
    {
        boardManager.Instance.applyMoves(board, b, color);
        int score = -NegaMax(board, !color, depth - 1);
        highestScore = Mathf.Max(highestScore, score);
    }

    return highestScore;
}

The problem functions are this:

public void applyMoves(checkerMan[,] board,bool[,] moves, bool color)
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (moves[i, j])
            {
                for (int k = i; k < 8; k++)
                {
                    for (int l = j; l < 8; l++)
                    {
                        if (board[k, l] != null && board[k, l].isWhite == color && board[k,l].moves[i, j] )
                        {
                            board[k, l].setPosition(i, j);
                        }
                    }
                }
            }
        }
    }
}

private checkerMan[,] deppCopy(checkerMan[,] original)
{
    checkerMan[,] clone = new checkerMan[8, 8];

    for (int k = 0; k < 8; k++)
    {
        for (int l = 0; l < 8; l++)
        {
            if(original[k, l]!= null)
            {
                clone[k, l] = (checkerMan)Instantiate(original[k, l]);
            }
        }
    }

    return clone;
}

Things to note my board is an 8*8 multidimensional boolean array of class checkerMan

using UnityEngine;
using System.Collections;

public class checkerMan : MonoBehaviour
{
    public bool isWhite;
    public bool isKing;
    public int CurrentX { set; get; }
    public int CurrentY { set; get; }
    public bool[,] moves { set; get; }
    public void setPosition(int x, int y)
    {
        CurrentX = x;
        CurrentY = y;
    }
    public void setMove(bool[,] move)
    {
        moves = move;
    }
    public virtual bool[,] possibleMove()
    {
        return new bool[8, 8];
    }
    public virtual bool isForcedToMove()
    {
        return false;
    }
    public virtual bool[,] KillMoves(int a, int b)
    {
        return new bool[8, 8];
    }
    public virtual bool[,] KingPossibleMove()
    {
        return new bool[8, 8];
    }
    public virtual ArrayList kingKillMoves(int i, int j)
    {
        return new ArrayList();
    }
}

链接地址: http://www.djcxy.com/p/56360.html

上一篇: beta修剪在我的解决方案中用minimax去除随机性？

下一篇: 如何实现negamax的makemove功能