|
||
|
БИТОВОЕ ПРЕДСТАВЛЕНИЕ ДОСКИ Одномерное представление доски Доску мы отображаем на 64- битное число. Это означает что, каждая клетка представлена одним битом. Для каждой клетки возможно два состояния - 1 или 0. Она имеет вид: (MSB) 0010…010001 (LSB) LSB – least significant bit младший бит MSB – most significant bit старший бит Мы знаем, что разряды - это степени числа 2 0001 это 2 **0 0010 это 2 **1 0100 это 2 **2 Таким образом: LSB это 2**0 MSB это 2**63 Но вот как это отображается в развертке? Возможно, 1 у нас запишется как 0000..001, а возможно и 1 у нас запишется как 1000..000 Сдвиг влево это << При его использовании самые старшие биты уходят в небытие. Значит, если опираться на графику этой операции, развертка у нас должна выглядеть так: 1 у нас запишется как 0000..001 Если еще вспомнить, что шестнадцатеричное представление у нас задается в виде: 1 = 0x1 16 = 0x10, то окончательно останавливаемся на развертке вида: 1 как 0000..001 Отображение доски на одномерный массив Доска это матрица 8 на 8. Или по-другому - это двухмерный массив. Его можно огромным количеством способов отобразить на одномерный массив. Для однозначности мы должны задать формулы отображения доски напрямую и обратно. Отображение доски напрямую задаем формулой: Line_index = 8 * Rank_index + File_index Обратное отображение прямой на доску: File_index = Line_index modulo 8 = Line_index % 8 = Line_index & 7 Rank_index = Line_index div 8 = Line_index / 8 = Line_index >> 3 Здесь у нас: Line_index – координата одномерной доски (от 0 до 63) Rank_index – координата доски по вертикали (от 0 до 7) File_index – координата доски по горизонтали (от 0 до 7) Таким образом, доску мы представляем в виде: A8(56) B8(57) C8(58) D8(59) E8(60) F8(61) G8(62) H8(63) A7(48) B7(49) C7(50) D7(51) E7(52) F7(53) G7(54) H7(55) A6(40) B6(41) C6(42) D6(43) E6(44) F6(45) G6(46) H6(47) A5(32) B5(33) C5(34) D5(35) E5(36) F5(37) G5(38) H5(39) A4(24) B4(25) C4(26) D4(27) E4(28) F4(29) G4(30) H4(31) A3(16) B3(17) C3(18) D3(19) E3(20) F3(21) G3(22) H3(23) A2(8) B2(9) C2(10) D2(11) E2(12) F2(13) G2(14) H2(15) A1(0) B1(1) C1(2) D1(3) E1(4) F1(5) G1(6) H1(7) т.е. битовая развертка выглядит следующим образом: H8(63) G8(62) F8(61) . . . . . .C1(2) B1(1) A1(0) A1(LSB)- это нулевой бит H8(MSB)-это 63 бит Мы не только развернули доску в линию, но и развернули эту линию. Структура доски Так как бит может принимать только два значения 1 или 0, то на битовой доске мы можем представить только факт присутствия или отсутствия фигуры. Конечно, нам этого недостаточно нам нужно знать, что это за фигура и какого она цвета. Для полного описания доски я использовал следующую структуру // битовая доска struct T_Bitboard { unsigned __int64 all_piece; все фигуры unsigned __int64 all_white_piece; все белые фигуры unsigned __int64 all_black_piece; все черные фигуры // битовые списки черных и белых фигур unsigned __int64 white_piece[NAME]; unsigned __int64 black_piece[NAME]; NAME это имя фигуры и оно принимает следующие значения: 0 - нет фигуры 1 - пешка 2 - конь 3 - слон 4 - ладья 5 - ферзь 6 - король Это значит, что для каждого класса фигур своя битовая доска. Для полноты картины добавлю, что используется еще два массива, задающие имя фигуры от координаты: int white_name_from_coord[COORDINATE]; int black_name_from_coord[COORDINATE]; по ним можно моментально узнать какая фигура на данном поле стоит. //------------------------------------------------- // ВСПОМОГАТЕЛЬНАЯ ИНФОРМАЦИЯ // цвет хода 0 - черные 1 - белые int colour_move; // разрешение бития на проходе 1/0 int taking_passage_yes; // х координата битого поля(конвертируем из буквы) // так а - 0 , h - 7 таким образом по х отображение прямое int taking_passage_x; // у координата битого поля // так '1' - 0 , '8' - 7 таким образом отображение тоже прямое только сдвинуто на 1 int taking_passage_y; // рокировка белых в длинную сторону 1/0 int castling_Q; // рокировка белых в короткую сторону 1/0 int castling_K; // рокировка черных в длинную сторону 1/0 int castling_q; // рокировка черных в короткую сторону 1/0 int castling_k; // 64 битный хеш ключ позиции unsigned __int64 hash_key ; // оценка позиции int eval ; };//struct T_Bitboard { Расположение фигуры на доске Допустим, единственная фигура стоит на поле А1. Доска выглядит так: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 или если ее развернуть то так: 0000000000000000000000000000000000000000000000000000000000000001 это у нас число 1 если фигура стоит на поле Н8 то: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 или если ее развернуть то так: 1000000000000000000000000000000000000000000000000000000000000000 это число 9223372036854775808 В результате любому положению фигуры на доске мы можем сопоставить 64 битное число в диапазоне от 1 до 9223372036854775808 Зная что: 2**0 это 00..001 2**1 это 00..010 2**2 это 00..100 т.е. просто бежим по степеням 2. Мы можем рассчитать массив констант для всевозможного расположения взведенного бита на доске. В программе это массив: const unsigned __int64 move_masks[] ={ // в примечании пишем какой бит установлен в 1 1, // 0 bit т.е. ....0001 2, // 1 bit т.е. ....0010 4, // 2 bit т.е. ....0100 8, // 3 bit и т.д. 16, // 4 bit …. } Таким образом, если у нас есть 64 битное число all_piece, то добавить фигуру на поле А1 можно следующим образом: all_piece = all_piece | 1 | - or операция логического «или» работает следующим образом - если хоть одна единица, то результат единица. в программе это будет: all_piece = all_piece | move_masks[0] (очевидно что | move_masks[0] = 1) Стереть фигуру с позиции можно следующим образом: all_piece = all_piece ^ 1 ^ - xor операция исключающего или работает следующим образом, если хоть одна единица, то результат единица, но если обе единицы то результат ноль. В программе это будет: all_piece = all_piece ^ move_masks[0] Всевозможные ходы фигуры Следуя соглашению об отображении доски на одномерный массив и используя move_masks[], можно рассчитать массив ходов фигуры от ее расположения. Например, для короля на А1 это будет: Доска выглядит так: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 Или если ее развернуть то так: 0000000000000000000000000000000000000000000000000000000110000001 это будет число 770 Массив всевозможных расположений и ходов для них короля в программе const unsigned __int64 king_moves_masks[] ={ // в примечании пишем, где находится король, например from0 - король в A1(0) //====================== 770, // from0 //====================== 1797, // from1 … } Аналогично для всех фигур. Массивы возможных ходов это все ходы, которые может сделать фигура, если она находится одна на доске. Следует понимать, что отображение доски и массивы возможных ходов фигуры завязаны друг на друга. Поэтому о массивах всевозможных ходов было сказано в главе о структуре доски. |