Все знают игру крестики-нолики 3x3. При правильной игре при первом ходе крестиков результатом является ничья. Можно вручную составить дерево ходов, где на любой ход ноликов, существует ход крестиков, который ведет к наилучшему результату (для крестиков), то есть к ничьей или выигрышу. Это дерево ходов исчерпывает все варианты, поэтому говорят, что игра «решена». Существует трехмерная разновидность крестиков-ноликов 4x4x4 для которой ответ на вопрос, кто победит при первом ходе крестиков, не очевиден. Более того, возникает вопрос, можно ли построить такое минимальное дерево, которое будет решать эту задачу.
Ответ на этот вопрос под катом.
Читать полностью »