Разбор: непобедимый алгоритм для игры «4 в ряд»

У наше­го куми­ра Code Bullet есть видео, где он пишет алго­ритм для побе­ды в игре «4 в ряд». 

В роли­ке есть одна любо­пыт­ная деталь: Эван (кото­рый Code Bullet) реша­ет зада­чу пере­бо­ром всех воз­мож­ных зна­че­ний и пони­ма­ет, что их чис­ло слиш­ком вели­ко, что­бы их мож­но было быст­ро пере­брать на ком­пью­те­ре. В ито­ге он исполь­зу­ет один хит­рый трюк, что­бы сокра­тить коли­че­ство пере­бо­ров и уско­рить рабо­ту алгоритма.

Если вы зна­е­те англий­ский, то луч­ше посмот­ри­те видео, а если нет — почи­тай­те наш крат­кий пересказ. 

Что такое «4 в ряд»

Есть два игро­ка, один из кото­рых игра­ет крас­ны­ми фиш­ка­ми, а вто­рой — жёл­ты­ми. Ещё есть игро­вое поле — 7 яче­ек в шири­ну и 6 в высо­ту. Игро­ки по оче­ре­ди роня­ют фиш­ки сво­е­го цве­та в любой стол­бец, а цель игры — собрать 4 фиш­ки сво­е­го цве­та в ряд по гори­зон­та­ли, вер­ти­ка­ли или диагонали.

Разбор: непобедимый алгоритм для игры «4 в ряд» «4 в ряд» в клас­си­че­ском виде 

Эван хочет напи­сать алго­ритм, кото­рый будет выда­вать самый луч­ший сле­ду­ю­щий ход для любо­го поло­же­ния фишек. 

Готовим поле

Как обыч­но, Эван дела­ет всё по шагам, малень­ки­ми пор­ци­я­ми добав­ляя новые воз­мож­но­сти в код. Это нуж­но для того, что­бы быст­ро про­ве­рять, в том ли направ­ле­нии идёт алго­ритм, и если нет — быст­ро его поправить. 

Сна­ча­ла он рису­ет окно, в кото­ром нет вооб­ще ниче­го — про­сто окно буду­щей про­грам­мы, что­бы убе­дить­ся, что код вооб­ще работает:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Потом Эван добав­ля­ет раз­би­е­ние игро­во­го поля на квад­ра­ты, что­бы уви­деть игро­вую сетку:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Финаль­ный штрих: квад­ра­ты пре­вра­ща­ют­ся в кру­ги, что­бы игра была похо­жа на настоящую:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Добавляем круги

Поле гото­во, мож­но добав­лять кру­ги, заод­но про­ве­ряя, как они ложат­ся в поле по сво­им координатам:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Но здесь Эва­на ждёт пер­вая непри­ят­ность: он забыл преду­смот­реть паде­ние фишек вниз, как это про­ис­хо­дит в насто­я­щей игре. В ито­ге фиш­ки висят в воз­ду­хе и лома­ют всю логику:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Добав­ля­ем про­вер­ку на пустые ячей­ки вни­зу, и если они есть — роня­ем фиш­ку вниз до упо­ра. Теперь всё рабо­та­ет как нужно:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Это уже доста­точ­но, что­бы мож­но было про­сто играть в игру, но нам нужен алго­ритм для побе­ды, поэто­му дви­га­ем­ся дальше.

Определяем наилучший ход

Эван реша­ет постро­ить выиг­рыш­ный алго­ритм по такой стратегии:

  1. Берём теку­щую рас­ста­нов­ку фишек на поле.
  2. Стро­им для неё все воз­мож­ные вари­ан­ты сле­ду­ю­ще­го хода и смот­рим, есть ли сре­ди них выиг­рыш­ный. Если нет — идём дальше.
  3. Для каж­дых из этих вари­ан­тов стро­им все воз­мож­ные вари­ан­ты сле­ду­ю­ще­го хода и смот­рим, есть ли сре­ди них выиг­рыш­ный. Если нет — идём дальше.
  4. Для каж­дых из новых вари­ан­тов стро­им все вари­ан­ты и так далее до тех пор, пока не закон­чат­ся клет­ки на поле или пока не най­дём выиг­рыш­ную комбинацию.

После того как все вари­ан­ты будут пере­бра­ны, алго­ритм выби­ра­ет самый луч­ший из них — тот, кото­рый веро­ят­нее все­го ведёт к победе. 

👉 Здесь Эван исхо­дит из логи­ки «жад­ных» алго­рит­мов: если при­ни­мать наи­луч­шее реше­ние на каж­дом ходу, то это авто­ма­ти­че­ски при­ве­дёт к выиг­ры­шу (или как мини­мум поз­во­лит сде­лать ничью).

Гра­фи­че­ски это мож­но пред­ста­вить так:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Когда Эван запус­ка­ет свой алго­ритм, то он зави­са­ет на пер­вом же ходу:

Разбор: непобедимый алгоритм для игры «4 в ряд»

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

Оптимизация — таблицы проверенных ходов

Что­бы уско­рить рабо­ту сво­е­го алго­рит­ма, у Эва­на есть три пути:

  1. Пере­пи­сать код на C++, что даст ему неко­то­рый при­рост про­из­во­ди­тель­но­сти и эффективности.
  2. Занять­ся опти­ми­за­ци­ей алго­рит­ма с мате­ма­ти­че­ской точ­ки зрения.
  3. Сжуль­ни­чать и под­смот­реть рабо­та­ю­щее реше­ние, а потом внед­рить его себе.

Вари­ан­ты 1 и 2 — это пра­виль­но, но дол­го, поэто­му Эван выби­ра­ет тре­тий и идёт читать мате­ри­а­лы Пас­ка­ля (Pascal Pons), кото­рый уже нашёл реше­ние этой проблемы.

Пер­вое, что дела­ет Эван — созда­ёт таб­ли­цу про­ве­рен­ных ходов. Это зна­чит, что ком­пью­тер на каж­дом ходу загля­ды­ва­ет в таб­ли­цу с рас­ста­нов­ка­ми и смот­рит, есть там такая пози­ция или нет. Если есть, то алго­ритм берёт из этой таб­ли­цы уже гото­вый наи­луч­ший ход для этой ситу­а­ции, а если нет — про­счи­ты­ва­ет рас­ста­нов­ку сам и запи­сы­ва­ет в таб­ли­цу наи­луч­ший ход.

Такой под­ход сокра­ща­ет вре­мя обра­бот­ки каж­до­го хода, пото­му что после раз­ных ходов могут полу­чить­ся оди­на­ко­вые рас­ста­нов­ки, у кото­рых будет оди­на­ко­вое про­дол­же­ние. Нам оста­ёт­ся толь­ко загля­нуть в таб­ли­цу и выяс­нить, было такое уже или нет.

Что­бы сге­не­ри­ро­вать себе такую таб­ли­цу, Эван идёт на хит­рость: он захо­дит на сайт Пас­ка­ля, где мож­но сыг­рать про­тив его алго­рит­ма. После это­го Эван пере­про­грам­ми­ру­ет свой код так, что­бы он играл про­тив алго­рит­ма Пас­ка­ля и запи­сы­вал в таб­лич­ку каж­дый его ход:

Разбор: непобедимый алгоритм для игры «4 в ряд»

Через два дня непре­рыв­ной рабо­ты про­грам­мы Эван посчи­тал, сколь­ко запи­сей у него полу­чи­лось в таб­ли­це: око­ло 15 000 запи­сей. Это зна­чит, что его алго­ритм может момен­таль­но обра­бо­тать 15 000 рас­ста­но­вок, а осталь­ные при­дёт­ся счи­тать само­сто­я­тель­но. Про­бле­ма в том, что все­го рас­ста­но­вок в этой игре в 300 000 раз боль­ше: 4 531 985 219 вари­ан­тов. Это зна­чит, что два дня непре­рыв­ной рабо­ты кода опти­ми­зи­ро­ва­ли нашу игру все­го на 0,0000033%. Нужен дру­гой подход.

Оптимизация таблиц — улучшенный вариант

Что­бы сокра­тить коли­че­ство вари­ан­тов для пере­бо­ра, Эван при­ду­мы­ва­ет дру­гой ход: играть про­тив алго­рит­ма Пас­ка­ля все­го 6 ходов, потом сбра­сы­вать и начи­нать всё сна­ча­ла. Кажет­ся, что выхлоп от это­го будет такой же мизер­ный, но на самом деле нет. 

Дело в том, что корот­кие пар­тии по 6 ходов с каж­дой сто­ро­ны игра­ют­ся намно­го быст­рее, чем пол­ные, а зна­чит, мож­но быст­рее най­ти все вари­ан­ты рас­ста­но­вок после пер­вых 6 ходов.

С дру­гой сто­ро­ны, пол­но­стью сыг­ран­ные 6 ходов с каж­дой сто­ро­ны дадут нам при­мер­но 1 мил­ли­он воз­мож­ных рас­ста­но­вок (срав­ни­те с 15 000 вари­ан­та­ми в пер­вом слу­чае). Это зна­чит, что если игра не най­дёт теку­щую рас­ста­нов­ку в таб­ли­це, ей доста­точ­но будет про­ве­рить все­го 4500 ком­би­на­ций, запи­сать най­ден­ный резуль­тат в таб­ли­цу и выдать пра­виль­ный ход. Такое ком­пью­тер может сде­лать за пару секунд.

В ито­ге Эван полу­чил алго­ритм, кото­рый почти сра­зу выда­ёт наи­луч­ший ход и не про­иг­ры­ва­ет ни одной партии. 

И что? Мне-то это зачем, я же не собираюсь играть в игры?

А вот зачем:

  1. Каж­дый алго­ритм мож­но опти­ми­зи­ро­вать несколь­ки­ми спо­со­ба­ми. Выбор спо­со­ба зави­сит от вре­ме­ни, ресур­сов и резуль­та­та, кото­рый нам нуж­но получить. 
  2. Нет пра­виль­но­го и непра­виль­но­го под­хо­да к опти­ми­за­ции алго­рит­мов, всё зави­сит от внеш­них усло­вий. Если бы код Эва­на дол­жен был быст­ро рабо­тать в кар­ман­ной игруш­ке на дешё­вой мик­ро­схе­ме, ему при­шлось бы пере­пи­сы­вать его на C++, пото­му что там луч­ше производительность.
  3. Если нет огра­ни­че­ний, кото­рые могут повли­ять на про­ект, мож­но выбрать любую опти­ми­за­цию, даже ту, кото­рая кажет­ся нечест­ной, но даёт нуж­ный результат.
  4. Необя­за­тель­но исполь­зо­вать ней­ро­се­ти, что­бы научить алго­ритм играть в игры. 
  5. Если кто-то уже напи­сал опти­ми­зи­ро­ван­ный алго­ритм, кото­рый под­хо­дит для вашей зада­чи, мож­но его брать и исполь­зо­вать у себя в про­ек­те. Почти все­гда реаль­ное про­грам­ми­ро­ва­ние — это не поиск и при­ду­мы­ва­ние самой ори­ги­наль­ной идеи, а исполь­зо­ва­ние того, что под­хо­дит луч­ше всего.

Текст:

Миха­ил Полянин

Редак­тор:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Ана­ста­сия Гаврилова

Соц­се­ти:

Олег Веш­кур­цев