Pull to refresh

Lines и теория вероятностей

Reading time 6 min
Views 34K


Каждый, кто играл в эту игру, знает: если сейчас попытаться вытащить голубой шарик, на который показывает курсор, чтобы поставить вместо него бордовый, то один из приходящих новых трёх шариков скорее всего «заткнёт» это место. Если попытаться ещё раз вытащить — заткнёт снова. На протяжении всех долгих лет существования этого эффекта между моими коллегами периодически возникали споры, случайно ли это получилось, или нарочно сделана такая «подлянка», чтобы было труднее играть.

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

В этой статье вы сможете вернуться на 20 лет назад и увидеть, как примерно проходил тогда процесс реверс-инжиниринга. Мы рассмотрим 16-битный ассемблерный код, который выбирает место для шариков. Здесь не будет современных 32- и 64-битных инструкций, обрастающих специальными наборами команд, не будет вызовов всяких там dll, потоков и прочих ухищрений. Только простой код. Мне кажется, его поймут даже те, кто ни разу не видел ассемблера. Желающие смогут исправить алгоритм, чтобы он работал «честно».

Начнём с теории. Самый простой напрашивающийся алгоритм такой: выбрать случайное место на доске, а если оно занято, повторить. И так пока не попадём на свободное место. 20 лет назад я думал, что именно такой алгоритм выбрал автор игры и именно поэтому игра такая «нечестная». Я рассуждал так: какова вероятность, что в такой ситуации следующий шарик выпадет в единственное свободное поле в верхней части доски?



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

Но человек, знакомый с теорией вероятности, сразу скажет, что это неправильно. Это как вероятность встретить на улице динозавра. Или встретишь, или нет. Вероятность попадания шарика в любую клетку одинакова, независимо от того, сколько и какие клетки заняты. Если за последние 10 ходов ни разу не выпал красный шарик, то я понимаю, что на 11-й ход, скорее всего, он всё-таки выпадет, хотя на самом деле вероятность его выпадения сейчас точно такая же, как 10 ходов назад. Если тут есть еще кто-нибудь, кто не видел "бога тетриса", обязательно посмотрите.

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

Возьмем например, английскую floppy-версию игры, хотя вы можете взять любую другую. Для запуска понадобится эмулятор, например dosbox. Для изучения и исправления кода используем Hiew. Его старую DOS-версию автор предлагает скачать на своём сайте бесплатно.

С чего же начать? Как найти то место в программе, где выбирается случайное число? Доска у нас 9х9 клеток. Попробуем поискать 16-битные числа 9 или 81. Девяток находится много, а вот 81 — всего одно. (81 = 51h)



Вот как раз и 9-ки рядом с ним, видимо мы напали на след. Попробуем наобум поменять 51 на 30 и посмотрим, что получится. Запускаем игру, а она сразу закидывает всё поле шариками и зависает. Вот это неожиданно. Неужели это 81 не имеет отношения к размеру поля? Посмотрим, что это за ячейка [343E], куда его записали.



Ну вот же, чуть ниже по коду значение этой ячейки сравнивают с «4C». Хммм. 76? Это еще что такое? Не помню, на какое время этот вопрос поставил меня в тупик, но неожиданно (как и всё в этом процессе) до меня дошло: это число свободных клеток. В самом начале игры появляется 5 шариков. Сначала поле пустое, свободных клеток 81. Потом выкидывают шарики, пока это число не станет 76. Значит это и есть участок кода, где выполняется начальная инициализация доски. Одна из подпрограмм между этими операциями как раз должна выбирать позицию для шарика. Переход по «не равно», помеченный как (8) у нас образует маленький цикл, в котором всего 2 вызова. Посмотрим первый из них.



После стандартных операций со стеком, как видим, берётся число 50h (80), и передаётся как аргумент для вызова какой-то процедуры. Результат она, очевидно, возвращает в регистре AX, который сохраняем в переменной [bp][-2]. Потом берём это число, делим его на 9 (div cx), увеличиваем на 1 (inc ax), меняем местами частное и остаток, и частное сохраняем в ячейке [39E4]. Потом делаем всё то же самое, только сохраняем уже остаток этого же деления в ячейке [39E6].

Ну да, похоже это оно. Подпрограмма — это наверняка случайное число. На выходе мы имеем случайный номер поля. Потом делим его на 9, получаем две координаты, X и Y. На нормальном языке это могло бы выглядеть так:

	cell = random(80);

	x = cell / 9 + 1;
	y = cell % 9 + 1;

Идём дальше:



Берём ранее вычисленные X и Y. Одно из них сдвигаем влево (shl) на 1 бит (умножаем на 2), запоминаем в CX. Другое умножаем на 12 (18), складываем с CX и используем как индекс массива по адресу [3490]. Что это может быть? Ну конечно, содержимое игрового поля, как 2-мерный массив из 16-битных чисел. Поэтому X умножается на 2, а Y на 18. То есть имеем уже:

	cell = random(80);  // случ.число от 0 до 79

	x = cell / 9 + 1;
	y = cell % 9 + 1;

	if (field[x,y]!=0) ...

И следующий, последний участок, который нам понадобится:



Содержимое клетки сравниваем с нулём. Если это так (видимо клетка свободна?), переходим вперёд на 1E5A. Если нет — увеличиваем номер клетки (который у нас имеет сплошную нумерацию от 0 до 80). Сравниваем его с 51 (81), если меньше — опять же переходим на 1E5A. Если больше — записываем туда ноль, то есть переходим к началу доски. На этом месте все условные ветки у нас сходятся, и что же мы делаем? Повторяется точь-в-точь код с предыдущей картинки для выборки содержимого игрового поля и ещё раз сравнивается с нулём. Если не равно, то переходим назад, на адрес 1E15, а это как раз не самое начало, где выбирается случайное число, а место, где мы из него вычисляем отдельные координаты:

	cell = random(80);  // случ.число от 0 до 79

next:x = cell / 9 + 1;
     y = cell % 9 + 1;

	if (field[x,y]!=0)
	{
	  cell++;
	  if(cell==81) cell=0;
	}
	
	if (field[x,y]!=0) goto next;

Вот такой получается алгоритм. Выбираем случайную клетку, а потом, если она занята, просто сдвигаемся по полю слева направо и сверху вниз и по кругу, пока не найдём пустую клетку. Вот и найдена причина «нечестности». Конечно же, при таком алгоритме, вероятность выбора клеток будет очень разная, и зависеть от расположения уже имеющихся на доске шариков.

Проверим, что эта часть кода действительно работает в игре так, как мы предполагаем. Поменяем в начале 50 на 28. Теперь по идее новые шарики должны выпадать только в верхнюю половину доски. Запускаем, и ничего не меняется. Шарики появляются по всей доске.

Оказалось, в программе две почти одинаковых подпрограммы, одна из которых выкидывает 5 шариков случайного цвета в начале игры, а другая — по 3 шарика в ходе игры, но цвета их уже известны (потому что их надо показывать заранее). Copy/paste rules! Ну хорошо, меняем эту вторую подпрограмму, и убеждаемся, что она работает.

Теперь, чтобы алгоритм «честно» ставил шарики на случайные поля, достаточно изменить самый последний переход чуть выше, чтобы он шёл на повторный выбор случайного числа.

Для тех, кто никогда не пользовался hiew, точная последовательность действий
1. Запускаем hiew, выбираем lines.exe
2. Переходим в режим дизассемблера (Enter, Enter)
3. Ищем начало процедуры (F7, набираем байты B8 50 00)
4. Смещаемся вниз до нужного перехода (на 1D51)
5. Изменяем адрес перехода (F3, F2, меняем 1CF4 на 1CE8)
6. Выходим из редактирования и сохраняем изменения (Esc, F9)
7. Выходим из hiew

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

Осталось добавить, что на самом деле должно быть cell = random(81), а не 80. Из-за этой ошибки шарики никогда не выпадают в самую правую нижнюю клетку. Разве что если все клетки левее неё заняты, тогда он попадёт туда за счёт этого «неправильного» алгоритма.

Ах да, и ещё одно. Правильно было бы конечно выбрать случайное число от 1 до числа свободных клеток, и ставить шарик сразу на нужное место, точно зная, что оно свободно, а не повторять цикл, пока он сам не попадёт куда надо. Ведь если останется всего одна последняя клетка, кто знает, сколько раз придётся повторяться? Сколько времени понадобится 16-битному процессору, чтобы выполнить столько циклов? А по теории вероятности, может случиться так, что он вообще никогда туда не попадёт. Но мы ведь знаем, что все эти теории — ерунда, и рано или поздно, а скорее всего циклов через 80, шарик обязательно попадёт в эту единственную клетку.
Tags:
Hubs:
+75
Comments 33
Comments Comments 33

Articles