Разработчик запустил сайт с миллионом шахматных онлайн-досок

[artptr86]

двумерный массив из 64 миллионов объектов типа uint64

Это 64*8*1000000 = 488 МБ

Но ведь для хранения одной доски достаточно шести 64-битных чисел (цвет фигур, пешки, ладьи, кони, слоны, ферзи) + 2 байта для королей. В крайнем случае для удобства можно королям тоже 64-битное число выделить. И даже одно оставить для выравнивания. Всё равно памяти в 8 раз меньше понадобится.

[mrqak]

1 бит на цвет фигуры, 3 бита на тип фигуры (6 вариаций), 6 бит на позицию (64 вариации). Итого 10 бит на одну фигуру, 32 фигуры = 320 бит (40 байт) = пять 64-битных чисел (зачем числа?)

[Quiensabe]

Если хранить фигуры то выборки видимых фигур и проверки доступных ходов будут куда затратнее, тем более, что у него фигуры могут не только в рамках своей доски перемещаться.

Так что, чем экономить несколько сотен мегабайт, куда выгоднее хранить данные в том виде в котором с ними удобно работать. Тем более если это его первый опыт в данном ЯП.

[artptr86]

Вам цвет даже не нужен: первые 16 фигур можно считать белыми, вторые 16 — чёрными. Цвет они поменять не могут. Более 16 фигур у каждой стороны тоже быть не может. То есть в 3 бита можно уместить 6 типов фигуры + тип «пусто». Итого выходит 32 фигуры * 9 бит = 288 бит = 36 байт. Только в обоих случаях с таким массивом работать будет очень неудобно.

[artptr86]

Придумал как упростить раскладку в памяти:

Для каждой из 32 фигур храним по 1 байту: 1 бит «фигура жива», 1 бит «пешка превращена», 6 бит — клетка. Цвет и тип фигуры определяем по индексу. Для 16 пешек храним тип превращённой фигуры по 2 бита — (ладья, конь, слон, ферзь) = 32 бита = 4 байта. Итого 32 байта + 4 байта = те же 36 байт, но хранящиеся в более удобном для программиста и процессора виде.

[wxmaper]

Более 16 фигур у каждой стороны тоже быть не может.

Там же есть переход на соседнее поле. Сам не проверял как это работает, но по описанию из статьи звучит так, что доску можно полностью заполнить фигурами.

[daniilshat]

Переход на соседнюю доску выглядит так:

Гифка

[artptr86]

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

7 карт * 64 бита = 448 бит = 56 байт

[DrGluck07]

С этой штукой есть одна проблема. Миллион досок и 300 игроков онлайн (я видел максимум 500 игроков). У них даже не очень много шансов встретиться в одном квадрате. Лучше бы сделал 100х100.