优化打乱的数组——我需要遍历整个数组吗？

Question

我会尽力解释我的问题。我正在尝试在 PHP 中创建一个国际象棋引擎（只是为了好玩 :-)）代码中的整数只是返回有效的移动（为简单起见 - 在实际代码中它是对象和移动模式取决于它是关于哪一块的）

我正在寻找一种有效搜索数组的方法。有效地我的意思是尽可能快。看看我在下面代码中的评论“是否可以在不遍历所有 1000 个值的情况下跳出循环？” 我希望评论能解释我想要达到的目标。我只是在寻找优化以下代码的想法，而不是完整的代码:-)

//This is for demonstrating

//1000 values to go through

$moves_maybe_valid = range(1,1000);

shuffle($moves_maybe_valid);

//Go through possible values

$move_checked = [];

$nr=0;

foreach($moves_maybe_valid as $mmv) {

    $move_is_valid = check_move($mmv);

    //Check if not in checked array

    if ($move_is_valid === false && !in_array($mmv, $move_checked)) {

        //Add to checked move array

        $move_checked[] = $mmv;

    }

    //IS it possible to break out of loop without 

    //going through all 1000 values?

    //When all valid moves are true I want to break here

    //but I don't know when that is.

}

//for demonstration purpose only

//numbers (5,6) that returns true are unknown until an

//an actual check is done in this function

function check_move($nr) {

    if ($nr == 5 || $nr == 6) {

        return true;

    }

    return false;

}

如果我说我会从一开始就生成有效的移动（基于下面的评论）

$valid_moves = [5,6];

跳出循环的最佳方法是什么？

Answer 1

在正常情况下，您可能遇到的最大有效移动数约为 100。随着升级，它可能会更高一些，所以如果您有 9 个皇后，您可能会达到 200。不过，1000 还是太大了。生成有效动作列表应该意味着您甚至不需要检查它们是否有效。但是，我想你正在生成所有组合的列表，即使它们涉及通过另一块，用你自己的块落在一个正方形上，或者落在棋盘域之外。我会说，在你的第一代做这些检查：对于每个棋子，检查 4 种可能的移动并存储有效的移动对于每个城堡或主教，按顺序检查 14 个可能的位置，从棋子位置开始，向 4 个方向前进，直到你击中一个无效空间（击中你自己的棋子意味着你走得太远了。击中对手棋子意味着你'我打了最后一个）对于皇后，与城堡或主教相同，但有 8 个方向而不是 4 个对于骑士，检查 8 种可能的动作是否有效对于国王，检查 8 种可能的移动是否有效检查两个城堡移动中的任何一个是否可行对于每一步，您还需要确保它不会让您受制于人。该功能可能可以优化，因此您只能从国王的位置向外看。一旦你遍历了所有棋子，最多 16 个，你的动作列表应该只包含有效的动作。事情变得昂贵的地方是你的前瞻性。您想模拟未来的多少步？你如何衡量每一步的价值/风险？然后是简介。您需要一个好的采样分析器来优化和找到您的热点。注意昂贵的便利功能，如有in_array可能请避免使用。循环中的循环会降低性能。