0x88

Представление шахматной доски 0x88 — это квадратно-ориентированный метод представления шахматной доски в компьютерных шахматных программах . Число 0x88 представляет собой шестнадцатеричное целое число (136 ₁₀ , 210 ₈ , 10001000 ₂ ). Ранговые и файловые позиции представлены полубайтами ( шестнадцатеричными цифрами), а битовые промежутки упрощают ряд вычислений до побитовых операций .

Макет

В представлении доски 0x88 макет распространяется на доску 8х16, равную размеру двух соседних шахматных досок. Каждому квадрату матрицы 8х16 присвоен номер, как можно увидеть в таблице компоновки платы. В этой схеме каждый полубайт представляет ранг или файл, так что 8-битное целое число 0x42 представляет квадрат в (4,2) в нумерации, начинающейся с нуля, то есть c5 в стандартной алгебраической записи . ^[1]

Прибавление 16 к числу квадрата дает число квадрата на одну строку выше, а вычитание 16 дает число квадрата на одну строку ниже. При переходе из одного столбца в другой число увеличивается или уменьшается на единицу. ^[2] В шестнадцатеричной записи допустимые шахматные позиции (A1-H8) всегда ниже 0x88. Такая схема упрощает многие вычисления, которые необходимо выполнять шахматным программам , позволяя выполнять побитовые операции вместо сравнений. ^[3]

Расположение платы 0x88 ^[1]
	0x00 (а)	0x01 (б)	0x02 (с)	0x03(д)	0x04 (е)	0x05 (ф)	0x06 (г)	0x07 (ч)	0x08	0x09	0x0A	0x0B	0x0C	0x0D	0x0E	0x0F
0x70 (8)	70	71	72	73	74	75	76	77	78	79	7А	7Б	7С	7Д	7Е	7F
0x60 (7)	60	61	62	63	64	65	66	67	68	69	6А	6Б	6С	6Д	6Е	6F
0x50 (6)	50	51	52	53	54	55	56	57	58	59	5А	5Б	5С	5Д	5Е	5F
0x40 (5)	40	41	42	43	44	45	46	47	48	49	4А	4Б	4С	4D	4Е	4F
0x30 (4)	30	31	32	33	34	35	36	37	38	39	3А	3Б	3С	3D	3Е	3эт.
0x20 (3)	20	21	22	23	24	25	26	27	28	29	2А	2Б	2С	2D	2Е	2F
0x10 (2)	10	11	12	13	14	15	16	17	18	19	1А	1Б	1С	1Д	1Е	1F
0x00 (1)	00	01	02	03	04	05	06	07	08	09	0А	0Б	0С	0D	0Е	0Ф

Алгебраические обозначения и преобразования

Современным стандартом для идентификации полей на шахматной доске и ходов в игре является алгебраическая запись , при которой каждая клетка доски идентифицируется уникальной парой координат — буквой между a и h для горизонтальной координаты, известной как файл, и число от 1 до 8 для вертикальной координаты, известное как ранг.

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

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

{\text{square}}_{0{\rm {{x}88}}}=({\text{rank}}_{\text{0 to 7}}<<4)+{\text{file}}_{\text{0 to 7}}

Таким образом, 1 соответствует $00000000_{2}$ , при этом все 8 бит установлены в $0$ , b 2 соответствует $00010001_{2}$ , а h 8 соответствует $01110111_{2}$ . ^[1]

Чтобы преобразовать значение 0x88 в пару координат «ранг файла»:

{\text{file}}_{\text{0 to 7}}={\text{square}}_{0{\rm {{x}88}}}\ \&\ 7

{\text{rank}}_{\text{0 to 7}}=({\text{square}}_{0{\rm {{x}88}}}\ >>4)

Примечание. В приведенных выше формулах << и >> представляют сдвига логических битов операции влево и вправо соответственно, а & представляет побитовые и .

Приложения

Внешнее обнаружение

Обнаружение вне доски — это функция шахматных программ, которая определяет, находится ли фигура на разрешенной шахматной доске или за ее пределами. В 0x88 старший бит каждого полубайта показывает, находится ли фигура на доске или нет. В частности, из 8 бит, представляющих квадрат, четвертый и восьмой должны быть равны 0, чтобы фигура находилась на доске. ^[4] Это позволяет осуществлять внешнее обнаружение побитовым способом. и операции. Если $square AND 0x88 (или, в двоичном формате, 0b10001000) не равно нулю, то квадрата нет на доске. ^[5] Эта побитовая операция требует меньше ресурсов компьютера, чем целочисленное сравнение. Это ускоряет такие вычисления, как обнаружение незаконных перемещений. ^[5]

Квадратные отношения

Разница действительных координат A и B 0x88 уникальна в отношении расстояния и направления, что неверно для классических упакованных трехбитных ранговых и файловых координат. Это делает поиск манхэттенского расстояния , возможных атак фигур и допустимых ходов фигур более экономичным. В то время как для классических квадратных координат в диапазоне 0–63 требуются таблицы размера 4 КБ (64×64), разница 0x88 требует 1/16 этого размера или таблиц размера 256 — или даже на 16 меньше. ^[6]

Добавляется смещение 119 (0x77 как максимальный допустимый квадратный индекс), чтобы сделать ±119 диапазоном 0–238 (размер 240 для целей выравнивания). ^[6]

0x88Diff = 0x77 + A − B

Принятие

Хотя представление 0x88 изначально было популярным, в большинстве случаев оно было заменено системой битбордов . ^[7]

Ссылки

Цитируемые работы

Хаятт, Роберт (2013). «Представления на доске шахматной программы» . Архивировано из оригинала 12 февраля 2013 года . Проверено 6 марта 2020 г.
Реуль, Фриц Макс Генрих (2009). Новые архитектуры в компьютерных шахматах (Диссертация). Gildeprint, Серия диссертаций TICC 6. ISBN 9789490122249 .
Остенсен, Эмиль Фредрик (осень 2016 г.). Университет Осло (PDF) (магистерская диссертация в области программирования и сетей). Университет Осло.
Морленд, Брюс (16 июля 2007 г.). «0x88 Генерация перемещения» . Архивировано из оригинала 16 июля 2007 г. Проверено 12 марта 2020 г.
Шалк, Андреа (7 августа 2008 г.). «COMP30191 Теория игр и игровые модели» (PDF) . Факультет компьютерных наук Манчестерского университета . Проверено 18 марта 2020 г.
Кин, Бен (ноябрь 2009 г.). «История компьютерных шахмат» (PDF) . Бордосская лаборатория исследований и компьютерных наук . Архивировано из оригинала (PDF) 23 марта 2020 г. Проверено 23 марта 2020 г.
Дэйли, Пол; Готоюх, Доминик; Хеннинг, Нил; Лоусон, Кейр; Макдональд, Алек; Таджаддинов, Тамерлан (18 марта 2008 г.). «Шахматный богомол — шахматный двигатель» . Проверено 23 марта 2020 г.

Внешние ссылки

Изображения шахматной доски Роберта Хаятта
Как Зарьков играет в шахматы. Архивировано 19 августа 2020 г. в Wayback Machine. Джоном Стэнбеком
Представление 0x88 из Mediocre Chess, заархивировано 20 августа 2018 г. в Wayback Machine Джонатаном Петтерссоном.

[FOOTNOTEHyatt2013-1] Jump up to: ^а ^б ^с Хаятт 2013г .

[FOOTNOTESchalk2008-2] Шалк 2008 .

[FOOTNOTEØstensen2016-3] Остенсен 2016 .

[FOOTNOTEDaillyGotojuchHenningLawson2008-4] Дайли и др. 2008 год .

[FOOTNOTEReul2009-5] Jump up to: ^а ^б Звезда 2009 года .

[FOOTNOTEMoreland2007-6] Jump up to: ^а ^б Морленд 2007 .

[FOOTNOTEKeen2009-7] Кин 2009 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]