Зображення шахівниці

При розробці комп'ютерних шахових програм, програміст мусить вибрати тип структури даних для представлення шахові позиції. Існує декілька методів для цього, які відомі як представлення шахівниці (англ. board representations). Для ефективності шахові рушії часто використовують більше одного методу представлення шахівниці.

Вимоги

Повний опис шахової позиції, тобто її «стан», повинен містити наступні елементи:

• Розташування кожної фігури на шахівниці
• Чия черга ходити
• Статус 50-ти ходового правила нічиєї. Наприклад, якщо перед цим 40 ходів пройшло без взяття або ходу пішака, це правило почне діяти після інших десяти ходів.
• Чи хтось із гравців зробив рокіровку.
• Чи можливе взяття на проході.

Представлення шахівниці зазвичай не включає статус правила , бо щоб його визначити, потрібна майже повна історія партії.

Типи

Список фігур

Деякі з найраніших шахових програм працювали з такими обмеженими кількостями пам'яті, що не було навіть пам'яті, щоб запам'ятати 64 позиції. Замість цього ці ранні програми підтримували списки 16 чорних та білих фігур. Зараз такий метод усе ще використовується в багатьох сучасних програмах разом з окремою структурою представлення шахівниці, щоб збільшити швидкість доступу до фігур. Замість виконання циклу через усі 64 (або більше) клітинок, щоб знайти всі: фігури, списки фігур дають прямий доступ до них.

Методи, базовані на масиві

Один із найпростіших способів представлення шахівниці — це створити двовимірний масив 8x8 (або, еквівалентно, 64 елементний одномірний масив). Кожен елемент цього масиву показує чи є на ньому фігура або навпаки, якщо квадрат порожній. Загальноприйняте кодування — розглядати 0 як порожнє поле, позитивне число як поле з білою фігурою, а негативне як поле із чорною фігурою. Наприклад, білий пішак +1, чорний пішак −1, білий кінь +2, чорний кінь −2, білий слон +3 і так далі.

Проблема із цим підходом з'являється протягом генерації ходів. Треба перевірити кожен хід, щоб упевнитися, що він на шахівниці. Програма буде робити цикли приблизно 20-30 разів за хід і це значно уповільнює процес.

Одне рішення — використовувати масив 12x12, із зовнішніми краями, заповненими, скажімо, значенням 99. Протягом генерації ходів, операція перевірки фігури на клітинці також укаже чи клітинка на шахівниці або ні.

Кращого використання пам'яті можна досягти з масивом 10x12, який забезпечує ті ж функціональні можливості, що й 12x12. Деякі шахові рушії використовують масиви 16x16, щоб поліпшити швидкість рядового перетворення чисел і дозволяють використовувати деякі спеціальні прийоми для збільшення агресивності програми.

Програмісти машинного коду мають іншу альтернативу. Використовуючи 4 біти на квадрат, повний ряд можна зобразити в 32 байтах, а дошка в 8 регістрах (із додатковою інформацією про позицію).

Метод 0x88

У цьому методі використовується масив розміром 16x8 = 128, пронумерований від 0 до 127. Це по суті дві шахівниці одна поряд з іншою, де справжня шахівниця розташована з лівого боку. Двійкова схема розміщення горизонталі та вертикалі справжньої шахівниці —- [0 r r r 0 f f f]. Генеруючи переміщення на основній дошці можна легко перевірити чи якийсь квадрат розташований на основній дошці просто накладаючи маску на номер клітинки із шістнадцятковим 0x88 (двійкове [1 0 0 0 1 0 0 0]). Ненульовий результат указує, що квадрат поза межами основної дошки. Крім того, різниця між двома координатами квадратів унікально визначає чи розташовані ті два квадрата вздовж тої самої горизонталі, вертикалі або діагоналі.

Бітборди

Ще один популярний спосіб представлення дошки — використання (англ. bitboard). Бітборд —- 64-розрядна послідовність бітів (нулів чи одиниць), яка вказує відсутність або присутність (хибність або істина) деякого стану на кожному місці шахівниці. Позицію на шахівниці потім зображують, використовуючи цикл бітбордів. Наприклад, цикл бітбордів для кожної фігури або пішака.

Перевага цього методу —- здатність використовувати операції на 64-бітних об'єктах замість ітерації, щоб отримувати інформацію про стан шахівниці. Використовуючи цей метод можна досягти значного збільшення швидкості програми, особливо на 64-бітних системах. До недоліків можна віднести відносну складність програмування порівняно з іншими способами.

Примітки

1. Роберт Хайатт. Представлення шахівниці шахових програм. Повна стаття [ 10 лютого 2012 у Wayback Machine.] (англ.)