neural-network - 让 ANN 学习识别跳棋游戏中的优势状态？

Question

作为大学作业，我们的任务是创建一个简单的 AI，它可以使用带 alpha-beta 修剪的极小极大算法来玩选秀游戏。我们使用的其他技术由我们决定。

在我们的团队中，我们决定使用人工神经网络作为评估函数(主要是为了好玩)，这样，随着时间的推移，它会学会识别对 AI 有利或不利的棋盘状态。这确实意味着我们在 AI 方面是菜鸟。

这是一个相当简单的前馈神经网络，有 50 个输入神经元(对应于 50 个方格的棋盘)、单层中的 25 个隐藏神经元和 1 个输出神经元。

输出在 -1 和 1 之间变化，较高的值表示对玩家有利的状态，较低的值表示不好。它使用 tanh 作为激活函数。

我们使用反向传播算法让它学习。

反复向它提供一组输入和期望的输出，它实际上很好地学习了这些模式!

我们首先对其进行一些初始训练，生成随机棋盘状态，并将目标值设置为“你的”棋子与“对手”的棋子之比，始终限制为 [-1,1]。 ANN 似乎也很好地掌握了这种模式。

但是，我们也希望它从经验中学习，我们可以让它玩几百场游戏，并从中学习。所以，首先，我们对其进行“初始训练”，然后，在每场比赛之后，我们用伪代码这样做:

learnRate = 0.05;
if ( the game was won ) {
    desireability_adjust = 0.1f;
} else {
    desireability_adjust = -0.1f;
}

foreach boardState in (board states recorded during play in reverse order) {

    currentOutput = neuralnet.evaluate(boardState)

    targetOutput = currentOutput + desireability_adjust * (1 - abs(currentOutput))

    neuralnet.learn(boardState, targetOuput, learnRate)

    // Decrease the desireability_adjust for every step
    desireability_adjust *= 0.9; 
}

这给出了非常复杂的结果。 “有经验”的玩家经常输给刚完成初始训练的玩家，而简单地计算棋子的经典 minimax 玩家只会屠杀 NN 驱动的玩家。

您建议对这种方法进行哪些更改，让 NN 学习游戏？让网络更大或更深会有什么用吗？赛后学习算法有什么明显不好的地方吗？

编辑:

我把赛后算法改成这样，而不是上面提出的“调整”方法:

learnRate = 0.1f;

if (win) {
    resultValue = 0.95 // Not 1 because tanh cannot reach 1 or -1
} else {
    resultValue = -0.95
}

// 0-based index is assumed
recordedstates = (list of states recorded during the game, in order)

for (index from recordedstates.length - 1 to 0) { {

    t = (index / recordedstates.length - 1);

    targetOutput = t * resultValue;

    nn.learn(recordedstates[index], targetOutput, learnRate)
}

直觉上目标值表示“结果的进展”，其中接近 0 的值表示游戏接近初始状态，-0.95 和 0.95 表示接近输或赢，分别。

不管怎样，作业主要是关于带有 alpha-beta 的 minimax，我们将举行一场比赛，看看谁创造了最好的 AI。我们可能会输得很惨，但它可能会产生大量非常强大的对手球员来训练。神经网络让我着迷，所以我可能会继续研究它。

我还注意到，一些失败的网络经常变得“沮丧”，他们会报告几乎任何状态都是消极的。希望上面的新学习方法会减少很多。

EDIT:2 我还添加了一些单元测试用例。最值得注意的是这个:

int[] hitPositionNearWin = {0,
              EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
        EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
              EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
        EMPTY,      EMPTY,      BLACKPIECE, EMPTY,      EMPTY,
              EMPTY,      EMPTY,      WHITEPIECE, EMPTY,      EMPTY,
        EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
              EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
        EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
              EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
        EMPTY,      EMPTY,      EMPTY,      EMPTY,      EMPTY,
    };

我期望的是神经网络从黑色和白色玩家的角度返回 1，因为棋盘总是从即将走棋的玩家的角度进行评估，而无论谁走棋这里赢了。

此时，神经网络给出:

• 白方一击获胜:-0.04490412(预期接近 1)
• 黑色一击获胜:0.08066118(预计接近 1)

3 层网络(1 个隐藏、1 个输入、1 个输出)应该能够识别这种情况是否正确？ (无论它出现在棋盘上的什么位置。)

只剩下一个棋子会使分数更接近极端，因为这是一个获胜的位置，这是正确的。

Answer 1

这对我来说听起来像是一项强化学习技术的任务。看一下时间差异学习。查看 Tesauro 撰写的 TD-gammon 文章。请注意，您在训练时可能需要探索节点。 (西洋双陆棋不需要探索，因为它会从掷骰子中获得变化。)

要获得强化学习的最佳介绍，您应该阅读 Sutton and Barto .

编辑:我认为您可以通过向前训练(而不是您建议的向后过程)来学习。让我详细说明一些(受 C 启发的)伪代码:

/* First initialize your neural net with random weights */
for( int i = 0; i < N_TRAINING_GAMES; i++ ){
    board b = board_of_initial_state;
    do {
        movelist ml = find_all_legal_moves( b );
        /* evaluate and score each move in the list of legal moves */
        for(each move m in ml){
             board b_tmp = do_move( b, m );
             if (b_tmp == won_game_state)
                 m.score = +1.0;
             else if (b_tmp == lost_game_state)
                 m.score = -1.0;
             else
                 m.score = neuralnet_forward_calculate( b_tmp );
        }            
        move m = pick_a_move_for_movelist( ml ); /* do not be greedy all time. Maybe use softmax. See Sutton & Barto Ch. 2 */
        neuralnet_backpropagation( b, m.score ); 
        b = do_move( b, m );  /* Update the board state */
    } while( game_is_not_over( b ) ); 
}

我没有在草图上测试过这段代码，但我猜它会在几千场比赛后收敛。请告诉我您的进展情况，因为这对我来说真的很有趣。

另一个编辑:我在代码中指定了一些细节。希望它是清楚的。所以在每次训练比赛中:

• 您在每次合法移动后评估棋盘状态。
• 然后您选择其中一个 Action - 概率最高的得分最高的 Action 。 (使用softmax来挑选)。
• 然后你在神经网络上进行反向传播以原始棋盘状态为模式，下一个棋盘状态的分数。 (我认为你必须乘以 -1 因为它来自其他玩家的观点。)
• 用您选择的 Action 更新棋盘。

以上代码是我认为的 TD(0) 算法。 (如果某些强化学习大师不同意我的观点，请告诉我。)这是您在 Sutton & Barto Ch.6 中找到的算法的游戏特定实现。 .然而，书中的行话有点笼统。书中的状态通常是游戏中的棋盘位置。书中的 Action 通常是在游戏板上移动。

上面的代码仍然是伪代码，还有很多东西是缺失的。你当然应该有一种方法来衡量你的代理人的实力，这样你就知道什么时候它不再改进了。完成 TD 训练后，您的静态神经网络评估器函数可用于极小极大搜索。