Эта статья является частью серии статей, посвященных |
Шахматное программирование |
---|
Представительства Совета |
Шахматные компьютеры |
Шахматные движки |
Представление шахматной доски 0x88 - это квадратно-ориентированный метод представления шахматной доски, используемый некоторыми шахматными программами . Номер 0x88 представляет собой шестнадцатеричное число (136 10 , 210 8 , 10001000 2 ). Каждая позиция в ряду и в файле представлена полубайтом (шестнадцатеричной цифрой), а битовые промежутки упрощают ряд вычислений до побитовых операций .
Макет [ править ]
В представлении доски 0x88 макет распространяется на доску 8 на 16, равную размеру двух соседних шахматных досок. Каждому квадрату матрицы 8 на 16 присвоен номер, как показано в таблице компоновки платы. В этой схеме каждый полубайт представляет ранг или файл, так что 8-битовое целое число 0x42 представляет квадрат в (4,2) в нумерации с нулевым отсчетом, то есть c5 в стандартной алгебраической нотации . [1]
Добавление 16 к числу квадрата дает число квадрата на одну строку выше, а вычитание 16 дает число квадрата на одну строку ниже. Для перехода от одного столбца к другому число увеличивается или уменьшается на единицу. [2] В шестнадцатеричной системе счисления допустимые шахматные позиции (A1-H8) всегда ниже 0x88. Эта компоновка упрощает многие вычисления, которые необходимо выполнять шахматным программам , позволяя использовать побитовые операции вместо сравнений. [3]
0x00 (а) | 0x01 (б) | 0x02 (с) | 0x03 (г) | 0x04 (e) | 0x05 (f) | 0x06 (г) | 0x07 (ч) | 0x08 | 0x09 | 0x0A | 0x0B | 0x0C | 0x0D | 0x0E | 0x0F | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0x70 (8) | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 7А | 7B | 7C | 7D | 7E | 7F |
0x60 (7) | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 6А | 6B | 6C | 6D | 6E | 6F |
0x50 (6) | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 5А | 5B | 5C | 5D | 5E | 5F |
0x40 (5) | 40 | 41 год | 42 | 43 год | 44 | 45 | 46 | 47 | 48 | 49 | 4А | 4B | 4C | 4D | 4E | 4F |
0x30 (4) | 30 | 31 год | 32 | 33 | 34 | 35 год | 36 | 37 | 38 | 39 | 3А | 3B | 3C | 3D | 3E | 3F |
0x20 (3) | 20 | 21 год | 22 | 23 | 24 | 25 | 26 год | 27 | 28 год | 29 | 2А | 2B | 2C | 2D | 2E | 2F |
0x10 (2) | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1А | 1B | 1С | 1D | 1E | 1F |
0x00 (1) | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | 0C | 0D | 0E | 0F |
Алгебраическая запись и преобразование [ править ]
Каждая клетка шахматной доски идентифицируется уникальной парой координат - буквой между ( a и h ) для ряда и числом от 1 до 8 для ранга. Этот метод обозначения квадратов является частью алгебраической системы обозначений . Чтобы преобразовать пару координат в значение 0x88, файлы обрабатываются как целые числа, где a соответствует 0, а h соответствует 7.
Таким образом, a 1 соответствует , со всеми 8 битами, установленными на , b 2 соответствует , а h 8 соответствует . [1]
Чтобы преобразовать значение 0x88 в рядовую пару координат:
Приложения [ править ]
Внешнее обнаружение [ править ]
Обнаружение вне доски - это функция шахматных программ, которая определяет, находится ли фигура на допустимой шахматной доске или нет. В 0x88 старший бит каждого полубайта показывает, находится ли кусок на доске или нет. В частности, из 8 битов, представляющих квадрат, четвертый и восьмой должны быть равны 0, чтобы фигура располагалась на доске. [4] Это позволяет выполнять обнаружение вне платы с помощью побитовых операций и операций. Если $square AND 0x88
(или в двоичной системе 0b10001000
) не ноль, значит, квадрата нет на доске. [5] Эта побитовая операция требует меньше компьютерных ресурсов, чем целочисленные сравнения. Это ускоряет вычисления, такие как обнаружение незаконного перемещения. [5]
Квадратные отношения [ править ]
Разница действительных координат 0x88 A и B уникальна по отношению к расстоянию и направлению, что неверно для классических упакованных трехбитовых координат ранга и файла. Это делает поиски расстояния Манхэттена , возможных атак фигур и правильных ходов фигур более удобными для ресурсов. В то время как классические квадратные координаты в диапазоне 0–63 требуют таблиц размером 4K (64 × 64), разница 0x88 занимает 1/16 от этого значения, или таблицы размером 256, или даже на 16 меньше. [6]
Смещение 119 (0x77 как максимальный допустимый квадратный индекс) добавляется, чтобы сделать ± 119 диапазоном 0–238 (размер 240 для целей выравнивания). [6]
0 × 88Diff = 0 × 77 + A - B
Принятие [ править ]
Хотя представление 0x88 было изначально популярным, его в основном заменила система битовых плат . [7]
Ссылки [ править ]
- ^ а б в Hyatt 2013 .
- Перейти ↑ Schalk, 2008 .
- ^ Østensen 2016 .
- ^ Дайли и др. 2008 .
- ^ а б Reul 2009 .
- ^ а б Морленд 2007 .
- Перейти ↑ Keen 2009 .
Процитированные работы [ править ]
- Хаятт, Роберт (2013). «Представления доски шахматной программы» . Архивировано из оригинального 12 февраля 2013 года . Дата обращения 6 марта 2020 .
- Реул, Фриц Макс Генрих (2009). Новые архитектуры в компьютерных шахматах (Дис.). Gildeprint, Серия диссертаций TICC 6. ISBN 9789490122249.
- Остенсен, Эмиль Фредрик (осень 2016 г.). Университет Осло (PDF) (диплом магистра программирования и сетей). Университет Осло.
- Морленд, Брюс (16 июля 2007 г.). «Генерация перемещения 0x88» . Архивировано из оригинала на 2007-07-16 . Проверено 12 марта 2020 .
- Шалк, Андреа (7 августа 2008 г.). "COMP30191 Теория игр и игровых моделей" (PDF) . Департамент компьютерных наук Манчестерского университета . Проверено 18 марта 2020 .
- Кин, Бен (ноябрь 2009 г.). «История компьютерных шахмат» (PDF) . Лаборатория Bordelais de Recherche en Informatique . Архивировано из оригинального (PDF) 23 марта 2020 года . Проверено 23 марта 2020 .
- Дайли, Пол; Годоюч, Доминик; Хеннинг, Нил; Лоусон, Кейр; Макдональд, Алек; Таджаддинов, Тамерлан (18 марта 2008 г.). «Шахматный богомол - шахматный двигатель» . Проверено 23 марта 2020 .
Внешние ссылки [ править ]
- Шахматная доска представления по Роберту Hyatt
- Как Зарьков играет в шахматы Архивировано 19 августа 2020 года в Wayback Machine, автор: Джон Стэнбэк
- 0x88 представления от посредственной шахматных Архивированных 2018-08-20 в Wayback Machine по Jonatan Pettersson