2

嗨，我在为 connect 4 游戏的 minMax 算法中添加alpha beta 修剪时遇到问题，你能帮我吗？这是我的 minMax 过程的代码，在我看来，我需要做的只是一点点：S scoreBoard() 是我的启发式函数，我返回一个包含 2 个值的数组，第一个是位置的在桌子上，另一个是这个位置的分数。

-(NSArray*) miniMaxWihtAlphaBetaPrunning:(BOOL)maxOrMin withAlpha:(NSInteger)alpha
 withBeta:(NSInteger)beta withPlayer:(enum playerColor)player andTreeDepth:
(NSInteger)depth
{
if (depth == 0)
{
    return [NSArray arrayWithObjects:[NSNumber numberWithInt:-1],
[NSNumber  numberWithInt:scoreBoard()],nil];
}
else
{
    NSInteger bestScore = maxOrMin ? redWins: blueWins;
    NSInteger bestMove = -1;

    for (NSInteger column = 0; column < 10; column++)
    {
        if (discPlacedMatrix[0][column] != 0)
        {
            continue;
        }

        NSInteger rowFilled = dropDiscAtPoint(column, player);

        if (rowFilled == -1)
        {
            continue;
        }

        NSInteger s = scoreBoard();

        if (s == (maxOrMin? blueWins : redWins))
        {
            bestMove = column;
            bestScore = s;
            discPlacedMatrix[rowFilled][column] = 0;

            break;
        }

        NSArray* result =  [NSArray arrayWithArray:[self miniMaxWihtAlphaBetaPrunning:!maxOrMin withAlpha:alpha withBeta:beta withPlayer:(player == 1 ? RED : BLUE) andTreeDepth:depth - 1]];

        NSInteger scoreInner = [[result objectAtIndex:1] intValue];

        discPlacedMatrix[rowFilled][column] = 0;

        if (scoreInner == blueWins || scoreInner == redWins)
        {
            scoreInner -= depth * player;
        }
        if (maxOrMin)
        {
            if (scoreInner >= bestScore)
            {
                bestScore = scoreInner;
                bestMove = column;
            }
        }
        else
        {
            if (scoreInner <= bestScore)
            {
                bestScore = scoreInner;
                bestMove = column;
            }
        }
    }

    return [NSArray arrayWithObjects:[NSNumber numberWithInt:bestMove],[NSNumber numberWithInt:bestScore],nil];
}

}

我尝试了一些场景，但艾开始

4

1 回答 1

0

听起来您正在寻找类似jamboree algorithm的东西。该算法的基本思想是递归地遍历你的树，并在每个级别上，对该级别的部分节点运行 alpha beta 算法，然后在其余节点上运行 mini-max 算法。我现在正在工作，但我会在我回家时详细说明。

一个实现：
http ://chessprogramming.wikispaces.com/Jamboree

于 2013-07-29T21:01:22.047 回答