Послушал лекцию чемпиона — и выиграл с битовой маской на 2 МБ
В Progmeistars проводили турнир компьютерных программ: на каждый тур давалась игра, и программы участников играли в неё друг против друга. Моя программа на 11-м турнире играла в «матричный покер»: поле 5×5, 25 карточек с цифрами 0–4, игроки по очереди выкладывают их, и у каждого есть пять линий плюс диагональ, которые считаются как покерные комбинации. Большую часть партии программа играла жадно — улучшала свои линии и портила линии соперника, — а на последних семи карточках включала полный перебор. Комментарий в начале исходника говорит всё: «Комп у меня выиграл».
Один из преподавателей выигрывал эти турниры раз за разом. Однажды он прочитал лекцию о том, как правильно писать такие программы, — про минимакс и про то, как ускорить перебор.
Я послушал, применил его советы на следующем турнире — и выиграл 12-й Турнир компьютерных программ в 2003 году.
Играли на поле 8×6. Игроки по очереди закрывали полосками соседние клетки — в основном полосками на две клетки, плюс три полоски на три клетки; игра заканчивалась, когда свободного места не оставалось. Полный перебор на таком поле был недоступен, поэтому план был в том, чтобы обмануть размер задачи:
- Пораньше избавиться от трёхклеточных полосок, чтобы остались только ходы на две клетки.
- Разделить поле надвое. Когда средние столбцы заполнены, левая и правая половины становятся независимыми играми, каждая 4×6 — всего 2²⁴, около 16 миллионов возможных позиций.
- Посчитать каждую половину заранее. Для каждой из этих 16 миллионов позиций программа знала, чётным или нечётным будет число оставшихся ходов при лучшей игре противника. Один бит на позицию: вся таблица помещалась в файл с битовыми масками на 2 МБ.
- Играть по чётности. Когда половины независимы, правильный ход — тот, после которого сумма чётностей складывается в твою пользу. Это поиск по таблице, а не перебор.
Партии проводили вручную: преподаватель запускал две программы на двух компьютерах и переносил ходы с одного на другой. Больше всего его удивило, что уже на втором-третьем ходу моя программа почти уверенно объявляла, что выиграет.
Что я из этого вынес: лучшая оптимизация часто не в более быстром переборе, а в другом представлении задачи — разбей её на независимые части и заранее посчитай то, что не меняется.