Скрытая эффективность троичной системы — и вопрос о том, не является ли построенная на ней игра втихомолку более изящной машиной.
Написано и отредактировано на английском языке. Эта русская версия создана машинным переводом; там, где важна точность, авторитетным остаётся английский оригинал. Читать оригинал на английском →
3927 — это 2048, перестроенная в трёх измерениях и в другой арифметике. Доска — куб 3×3×3, двадцать семь клеток, и вы сдвигаете весь куб в любом из шести направлений. Когда сталкиваются три плитки одинакового значения, они не удваиваются, а утраиваются. Тройка становится девяткой, девятка — двадцатью семью, и дальше: 81, 243, 729. Само название перечисляет первые три плитки, 3·9·27, и весь дизайн построен на тройках до самого основания: три клетки по каждой оси, три плитки на слияние, три как множитель роста. 4
Её предок упрямо двоичен. Классическая 2048 оперирует степенями двойки — 2, 4, 8, 16… — и сливает плитки парами. Два — число подброшенной монеты, транзистора, бита. Поэтому любопытный игрок естественно спрашивает: замена двойки на тройку — всего лишь новинка, или тройка всё это время скрывала настоящее преимущество? Оказывается, у математики есть мнение на этот счёт, и мнение удивительно твёрдое.
Представьте, что вам нужно построить машину, хранящую числа. Каждый разряд вам чего-то стоит — колеса, провода, лампы, — и эта стоимость растёт с основанием, потому что разряду в системе с основанием b нужно b различимых состояний. Но большее основание означает и то, что для записи любого числа нужно меньше разрядов. Здесь есть противоречие, и у него есть имя: экономичность системы счисления (radix economy).
Формально экономичность записи числа N в системе с основанием b — это основание, умноженное на число разрядов: E(b,N) = b ⌊log_b N + 1⌋ (log_b — логарифм по основанию b). 1 Большое основание даёт короткие числа, но дорогие разряды; малое основание дёшево в расчёте на разряд, но расползается. Где-то между двумя крайностями лежит золотая середина, и это не то место, где оказалась бо́льшая часть наших технологий.
| Основание | b ÷ ln b | относительно оптимума |
|---|---|---|
| 2 | 2.885 | +6.2% |
| 3 | 2.731 | +0.5% |
| e ≈ 2.718 | 2.718 | оптимум |
| 10 | 4.343 | +59.8% |
При больших N экономичность ведёт себя как (b ÷ ln b) · ln N, так что эффективность основания целиком зависит от множителя b ÷ ln b. Минимизируйте его с помощью немного анализа — и ответ окажется точным и странным: самое экономичное основание из всех — e, примерно 2,71828. 1 Построить компьютер с 2,718 состояния на разряд, разумеется, нельзя. Но можно спросить, какое целое число ближе всего к этому идеалу, — и победителем, обходящим и двойку, и десятку, оказывается тройка.
Разрыв не академический. Основание три отстоит от теоретического оптимума меньше чем на полпроцента, тогда как двоичная система платит шестипроцентную надбавку, а десятичная — сокрушительные шестьдесят. Вот наглядный способ это прочувствовать: чтобы записать любое число от 0 до 999 999, двоичной системе нужно 20 разрядов, десятичной — 6, а троичной — всего 13, и 13×3 в сумме меньше, чем 20×2. 1 Тройка действительно упаковывает больше счёта в меньшую конструкцию.
Природу спросили, как считать эффективнее всего, и она ответила иррациональным числом. Ближайшее к этому ответу целое число — три.
Это не просто диковинка из учебников. В 1958 году в Московском государственном университете коллектив под руководством Николая Брусенцова и математика Сергея Соболева построил «Сетунь» — самый знаменитый троичный компьютер из когда-либо созданных. 3 Пока Запад делал ставку на биты, «Сетунь» считала в тритах и использовала особенно красивую схему — уравновешенную (симметричную) троичную систему, цифры которой равны не 0, 1, 2, а −1, 0, +1. 2
Симметрия окупается сразу. Число само несёт свой знак — без отдельного знакового бита, без ухищрений дополнительного кода, — а чтобы сменить знак любого значения, достаточно просто инвертировать каждую цифру. Округление и отбрасывание дробной части становятся одной и той же операцией. Дональд Кнут назвал её «пожалуй, самой красивой системой счисления из всех». 2 Брусенцов, не имея транзисторов, добился трёх устойчивых состояний от спаренных ферритовых сердечников; было построено около пятидесяти «Сетуней», большинство отправили учить математике в университеты по всему Советскому Союзу. 3 Машина работала, была дешёвой и тихо опережала своих соседей.
Здесь внимательному автору приходится сдерживать себя. Экономичность системы счисления — утверждение о хранении и обработке чисел при определённых предположениях о стоимости, и даже математики отмечают, что эти предположения лишь приблизительны: более полный учёт часто снова оправдывает двоичную систему, и именно поэтому мир работает на ней. 1 Головоломка на слияние — не банк памяти; никто не минимизирует число ламп в перерыве на кофе. Так что 3927 не «эффективнее» ни в каком инженерно значимом смысле, и утверждать обратное было бы жульничеством.
И всё же. Игра наследует нечто истинное. Рост утроением достигает больших чисел за меньшее число более весомых ходов; каждое слияние совершает больше работы, а куб 3×3×3 — наименьшая доска, на которой тройному слиянию есть где развернуться в любом направлении. 4 Дизайн не наткнулся на тройку случайно — он пришёл к тому целому числу, которое математика счёта тихо предпочитает с самой зари электронных вычислений, к тому самому, которое инженеры «Сетуни» выбрали сознательно. Двойка — число, на котором мы остановились по умолчанию. Тройка — число, которое мы выбрали бы, если бы последнее слово было за эффективностью, а не за подброшенной монетой. То, что плитки складываются в 3, 9, 27, — маленькая шутка, которую вселенная рассказывала и без нас.
Game facts, the 3×3×3 board, six shift directions, three-tile ×3 merge, and the 3·9·27 naming, are measured from the game's design documents. Mathematical and historical claims are drawn from the references below.