Послушал лекцию чемпиона — и выиграл с битовой маской на 2 МБ

В Progmeistars проводили турнир компьютерных программ: на каждый тур давалась игра, и программы участников играли в неё друг против друга. Моя программа на 11-м турнире играла в «матричный покер»: поле 5×5, 25 карточек с цифрами 0–4, игроки по очереди выкладывают их, и у каждого есть пять линий плюс диагональ, которые считаются как покерные комбинации. Большую часть партии программа играла жадно — улучшала свои линии и портила линии соперника, — а на последних семи карточках включала полный перебор. Комментарий в начале исходника говорит всё: «Комп у меня выиграл».

Один из преподавателей выигрывал эти турниры раз за разом. Однажды он прочитал лекцию о том, как правильно писать такие программы, — про минимакс и про то, как ускорить перебор.

Я послушал, применил его советы на следующем турнире — и выиграл 12-й Турнир компьютерных программ в 2003 году.

Было и забавное осложнение. Как раз тогда у меня сломалась оперативная память — какой-то сбой, — а сдавать компьютер в ремонт было некогда. Тогда я вернулся в DOS: он использует только первый мегабайт памяти, и до сломанной части дело не доходило. Программу для турнира я писал на Паскале под DOS. Такой откат назад во времени — но своего я добился.

Играли на поле 8×6. Игроки по очереди закрывали полосками соседние клетки — в основном полосками на две клетки, плюс три полоски на три клетки; игра заканчивалась, когда свободного места не оставалось. Полный перебор на таком поле был недоступен, поэтому план был в том, чтобы обмануть размер задачи:

1. Пораньше избавиться от трёхклеточных полосок, чтобы остались только ходы на две клетки.
2. Разделить поле надвое. Когда средние столбцы заполнены, левая и правая половины становятся независимыми играми, каждая 4×6 — всего 2²⁴, около 16 миллионов возможных позиций.
3. Посчитать каждую половину заранее. Для каждой из этих 16 миллионов позиций программа знала, чётным или нечётным будет число оставшихся ходов при лучшей игре противника. Один бит на позицию: вся таблица помещалась в файл с битовыми масками на 2 МБ.
4. Играть по чётности. Когда половины независимы, правильный ход — тот, после которого сумма чётностей складывается в твою пользу. Это поиск по таблице, а не перебор.

Позиция в середине партии (иллюстрация, не реальная игра). В каждой строке центральная линия уже перекрыта, так что дальше левая и правая половины — две отдельные игры, каждую из которых можно посчитать заранее.

Партии проводили вручную: преподаватель запускал две программы на двух компьютерах и переносил ходы с одного на другой. Больше всего его удивило, что уже на втором-третьем ходу моя программа почти уверенно объявляла, что выиграет.

Что я из этого вынес: лучшая оптимизация часто не в более быстром переборе, а в другом представлении задачи — разбей её на независимые части и заранее посчитай то, что не меняется.