Игра «Определители 3x3»
Правила: игроки выбирают знаки, после чего по очереди заполняют матрицу 3x3 разными числами от 1 до 9. Чей знак имеет определитель полученной матрицы, тот и выиграл.
Моя программа, исходя из 9! = 362880 финальных позиций проанализировала все
позиций в игре, тем самым найдя оптимальную стратегию для всех 9!2 = 131681894400 игр.
Вывод: первый игрок имеет выигрышную стратегию независимо от выбранного им знака.
Любопытно, что первый ход может быть в любую клетку, но только цифрами от 4 до 8, независимо от знака. Создать непобедимую реализацию несложно, если использовать простой memory-time trade-off: хранить первые два хода первого игрока (1 первый и 64 вторых) и рассчитывать последующие 120 финальных позиций и 1546 промежуточных. Вот пример вторых ходов, записанных в очевидном JSON-формате:
{"000080001": "02", "000080002": "01", "000080003": "04", "000080004": "03", "000080005": "04", "000080006": "04", "000080007": "03", "000080009": "03", "000080010": "07", "000080020": "05", "000080030": "05", "000080040": "05", "000080050": "04", "000080060": "04", "000080070": "03", "000080090": "03", "000080100": "05", "000080200": "05", "000080300": "04", "000080400": "06", "000080500": "21", "000080600": "21", "000080700": "21", "000080900": "21", "000081000": "07", "000082000": "05", "000083000": "05", "000084000": "05", "000085000": "04", "000086000": "04", "000087000": "03", "000089000": "03", "000180000": "22", "000280000": "19", "000380000": "19", "000480000": "05", "000580000": "03", "000680000": "04", "000780000": "04", "000980000": "05", "001080000": "05", "002080000": "05", "003080000": "04", "004080000": "06", "005080000": "16", "006080000": "61", "007080000": "61", "009080000": "61", "010080000": "52", "020080000": "39", "030080000": "39", "040080000": "05", "050080000": "03", "060080000": "04", "070080000": "04", "090080000": "05", "100080000": "82", "200080000": "81", "300080000": "15", "400080000": "15", "500080000": "14", "600080000": "14", "700080000": "21", "900080000": "21"}
К слову, максимальный определитель, который можно получить в этой игре, равен 412 (очевидно, что минимальный равен −412), а общее решение задачи о максимальном определителе из перестановки 1..N2 неизвестно. Неизвестен даже максимальный определитель матрицы 7x7, составленной из чисел 1..49, а на поиск лучшего (и, похоже, неверного) приближения было потрачено 4 CPU-года на хороших современных Itanium'ах.
Эта последовательность имеет в справочнике Слоана номер A085000.
Моя программа, исходя из 9! = 362880 финальных позиций проанализировала все
Вывод: первый игрок имеет выигрышную стратегию независимо от выбранного им знака.
Любопытно, что первый ход может быть в любую клетку, но только цифрами от 4 до 8, независимо от знака. Создать непобедимую реализацию несложно, если использовать простой memory-time trade-off: хранить первые два хода первого игрока (1 первый и 64 вторых) и рассчитывать последующие 120 финальных позиций и 1546 промежуточных. Вот пример вторых ходов, записанных в очевидном JSON-формате:
{"000080001": "02", "000080002": "01", "000080003": "04", "000080004": "03", "000080005": "04", "000080006": "04", "000080007": "03", "000080009": "03", "000080010": "07", "000080020": "05", "000080030": "05", "000080040": "05", "000080050": "04", "000080060": "04", "000080070": "03", "000080090": "03", "000080100": "05", "000080200": "05", "000080300": "04", "000080400": "06", "000080500": "21", "000080600": "21", "000080700": "21", "000080900": "21", "000081000": "07", "000082000": "05", "000083000": "05", "000084000": "05", "000085000": "04", "000086000": "04", "000087000": "03", "000089000": "03", "000180000": "22", "000280000": "19", "000380000": "19", "000480000": "05", "000580000": "03", "000680000": "04", "000780000": "04", "000980000": "05", "001080000": "05", "002080000": "05", "003080000": "04", "004080000": "06", "005080000": "16", "006080000": "61", "007080000": "61", "009080000": "61", "010080000": "52", "020080000": "39", "030080000": "39", "040080000": "05", "050080000": "03", "060080000": "04", "070080000": "04", "090080000": "05", "100080000": "82", "200080000": "81", "300080000": "15", "400080000": "15", "500080000": "14", "600080000": "14", "700080000": "21", "900080000": "21"}
К слову, максимальный определитель, который можно получить в этой игре, равен 412 (очевидно, что минимальный равен −412), а общее решение задачи о максимальном определителе из перестановки 1..N2 неизвестно. Неизвестен даже максимальный определитель матрицы 7x7, составленной из чисел 1..49, а на поиск лучшего (и, похоже, неверного) приближения было потрачено 4 CPU-года на хороших современных Itanium'ах.
Эта последовательность имеет в справочнике Слоана номер A085000.
