Какие структуры данных вы использовали бы для представления шахматной доски для компьютерной шахматной программы?
Как смоделировать шахматную доску при программировании компьютера для игры в шахматы?
Ответ 1
Изначально используйте массив 8 * 8 целых чисел для представления шахматной доски.
Вы можете начать программирование с использованием этой нотации. Дайте значения точек для кусков. Например:
**White**
9 = white queen
5 = white rook
3 = bishop
3 = knight
1 = pawn
**black**
-9 = white queen
-5 = white rook
-3 = bishop
-3 = knight
-1 = pawn
White King: very large positive number
Black King: very large negative number
и т.д.. (Обратите внимание, что приведенные выше точки являются приблизительными значениями торговой силы каждой шахматной фигуры)
После того, как вы разработаете базовые основные черты вашего приложения и четко понимаете работу используемых алгоритмов, попробуйте повысить производительность с помощью досок.
В битовых платах вы используете восемь 8-битных слов для представления плат. Это представление требует доски для каждой шахматной фигуры. В одной доске вы будете хранить положение ладьи, а в другом вы будете хранить положение рыцаря... и т.д.
Бит-доски могут значительно повысить производительность вашего приложения, потому что манипулирование кусками с долотами очень просто и быстро.
Как вы указали,
Большинство шахматных программ сегодня, особенно те, которые работают на 64-битном процессоре, используют растровый подход для представления шахматной доске и генерировать ходы. x88 - альтернативная модель платы для машин без 64-битных процессоров.
Ответ 2
Для серьезного шахматного движка использование битов - эффективный способ представления шахматной доски в памяти. Битрейты быстрее, чем любое представление на основе массива, особенно в 64-битных архитектурах, где битовая плата может вписываться в один регистр CPU.
Bitboards
Основная идея битов состоит в том, чтобы представить каждый тип шахматной фигуры в 64 бита. В С++/С# это будет ulong/UInt64. Таким образом, вы будете поддерживать 12 UInt64 переменных для представления вашей шахматной доски: два (один черный и один белый) для каждого типа предметов, а именно: пешка, ладья, рыцарь, епископ, королева и король. Каждый бит в UInt64 будет соответствовать квадрату на шахматной доске. Как правило, младшим значащим битом будет квадрат a1, следующий b1, затем c1 и т.д. В строчном порядке. Бит, соответствующий расположению фигуры на шахматной доске, будет установлен в 1, все остальные будут установлены в 0. Например, если у вас есть две белые ладьи на a2 и h1, тогда белая грабежа будет выглядеть так:
0000000000000000000000000000000000000000000000000000000110000000
Теперь, например, если вы хотите перенести свою ладью с a2 на g2 в приведенном выше примере, все, что вам нужно сделать, это XOR, с которой вы используете:
0000000000000000000000000000000000000000000000000100000100000000
Битрейты имеют преимущество в производительности, когда дело доходит до поколения поколений. Существуют и другие преимущества в производительности, что spring, естественно, из представления битов. Например, вы можете использовать заблокированные хеш-таблицы, которые являются огромным преимуществом при параллелизации вашего алгоритма поиска.
Дополнительная литература
Конечным ресурсом для развития шахматного движка является Chess Programming Wiki. Недавно я написал этот шахматный движок, который реализует биты в С#. Еще лучший шахматный движок с открытым исходным кодом - StockFish, который также реализует биты, но на С++.
Ответ 3
Простым подходом является использование целочисленного массива 8x8. Используйте 0 для пустых квадратов и присвойте значения для кусков:
1 white pawns
2 white knights
3 white bishops
4 white rooks
5 white queens
6 white king
Black pieces use negative values
-1 black pawn
-2 black knight
etc
8| -4 -2 -3 -5 -6 -3 -2 -4
7| -1 -1 -1 -1 -1 -1 -1 -1
6| 0 0 0 0 0 0 0 0
5| 0 0 0 0 0 0 0 0
4| 0 0 0 0 0 0 0 0
3| 0 0 0 0 0 0 0 0
2| 1 1 1 1 1 1 1 1
1| 4 2 3 5 6 3 2 4
-------------------------
1 2 3 4 5 6 7 8
Перемещение частей может быть рассчитано с использованием индексов массива. Например, белые пешки перемещаются, увеличивая индекс строки на 1 или на 2, если сначала пешка движется. Таким образом, белая пешка на [2] [1] могла перейти к [3] [1] или [4] [1].
Однако в этом простом представлении массива 8x8 есть шахматная доска с несколькими проблемами. Прежде всего, когда вы перемещаете "скользящие" фигуры, такие как ладьи, епископы и королевы, вам нужно постоянно проверять индексы, чтобы увидеть, удалилась ли часть с доски.
Большинство шахматных программ сегодня, особенно тех, которые работают на 64-битном процессоре, используют растровый подход для представления шахматной доски и создания ходов. x88 - альтернативная модель платы для машин без 64-битных процессоров.
Ответ 4
Конечно, существует несколько различных способов представления шахматной доски, и лучший способ будет зависеть от того, что для вас наиболее важно.
Два основных варианта: скорость и четкость кода.
Если скорость - ваш приоритет, вы должны использовать 64-битный тип данных для каждого набора штук на доске (например, белые пешки, черные фермы, en passant pawns). Затем вы можете использовать собственные побитовые операции при генерации ходов и тестировании, перемещающих законность.
Если ясность кода является приоритетной, забудьте перетасовать бит и пойдите для красиво абстрагированных типов данных, как это уже было предложено другими. Просто помните, что если вы пойдете так, вы, скорее всего, ударите потолок производительности раньше.
Чтобы начать, просмотрите код Crafty (C) и SharpChess (С#).
Ответ 5
При создании моего шахматного движка я изначально пошел с подходом [8] [8], однако недавно я изменил свой код, чтобы представить шахматную доску, используя массив из 64 элементов. Я обнаружил, что эта реализация была примерно на 1/3 более эффективной, по крайней мере, в моем случае.
Одна из вещей, которые вы хотите рассмотреть при использовании подхода [8] [8], описывает позиции. Например, если вы хотите описать действительный ход для шахматной фигуры, для этого вам понадобится 2 байта. В то время как с массивом элементов [64] вы можете сделать это с помощью одного байта.
Для преобразования из позиции на плате [64] товара на плате [8] [8] вы можете просто использовать следующие вычисления:
Row = (байт) (индекс/8)
Col = (байт) (индекс% 8)
Хотя я обнаружил, что вам никогда не придется это делать во время рекурсивного поиска, который чувствителен к производительности.
Для получения дополнительной информации о создании шахматного движка, не стесняйтесь посещать мой блог, который описывает процесс с нуля: www.chessbin.com
Адам Берент
Ответ 6
Массив из 120 байт.
Это шахматная доска размером 8x8, окруженная дозорными квадратами (например, 255, чтобы указать, что кусок не может перейти на этот квадрат). Часовые имеют глубину в два, чтобы рыцарь не мог перепрыгнуть.
Для перемещения справа добавьте 1. Для перемещения влево добавьте -1. Up 10, down -10, вверх и справа диагональ 11 и т.д. Квадрат A1 - индекс 21. H1 - индекс 29. H8 - индекс 99.
Все предназначено для простоты. Но это никогда не будет так быстро, как биты.
Ответ 7
Ну, не уверен, что это помогает, но Deep Blue использовал единственное 6-битное число, чтобы представить конкретную позицию на доске. Это помогло ему сохранить след на чипе по сравнению с конкурентом, который использовал 64-битную битовую плату.
Это может быть не актуально, поскольку, скорее всего, у вас могут быть 64-разрядные регистры на вашем целевом оборудовании.
Ответ 8
Альтернативой стандартной плате 8x8 является 10x12 mailbox (так называемый, потому что, я думаю, это похоже на почтовый ящик). Это одномерный массив, который включает часовые вокруг своих "границ" , чтобы помочь с генерацией движения. Это выглядит так:
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, "a8", "b8", "c8", "d8", "e8", "f8", "g8", "h8", -1,
-1, "a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7", -1,
-1, "a6", "b6", "c6", "d6", "e6", "f6", "g6", "h6", -1,
-1, "a5", "b5", "c5", "d5", "e5", "f5", "g5", "h5", -1,
-1, "a4", "b4", "c4", "d4", "e4", "f4", "g4", "h4", -1,
-1, "a3", "b3", "c3", "d3", "e3", "f3", "g3", "h3", -1,
-1, "a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2", -1,
-1, "a1", "b1", "c1", "d1", "e1", "f1", "g1", "h1", -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1
Вы можете создать такой массив, как это (в JavaScript):
function generateEmptyBoard() {
var row = [];
for(var i = 0; i < 120; i++) {
row.push((i < 20 || i > 100 || !(i % 10) || i % 10 == 9)
? -1
: i2an(i));
}
return row;
}
// converts an index in the mailbox into its corresponding value in algebraic notation
function i2an(i) {
return "abcdefgh"[(i % 10) - 1] + (10 - Math.floor(i / 10));
}
Конечно, в реальной реализации вы бы поставили фактические кусочные объекты, где находятся метки на доске. Но вы сохраните отрицательные (или что-то подобное). Эти места делают движение поколений намного менее болезненным, потому что вы можете легко сказать, когда вы сбежали с борта, проверив для этого особое значение.
Давайте сначала посмотрим на создание законных движений для рыцаря (не скользит кусок):
function knightMoves(square, board) {
var i = an2i(square);
var moves = [];
[8, 12, 19, 21].forEach(function(offset) {
[i + offset, i - offset].forEach(function(pos) {
// make sure we're on the board
if (board[pos] != -1) {
// in a real implementation you'd also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
});
});
return moves;
}
// converts a position in algebraic notation into its location in the mailbox
function an2i(square) {
return "abcdefgh".indexOf(square[0]) + 1 + (10 - square[1]) * 10;
}
Мы знаем, что действительные перемещения Рыцаря являются фиксированным расстоянием от начальной точки куска, поэтому нам нужно только проверить, что эти местоположения действительны (т.е. не дозорные квадраты).
Скользящие части не намного сложнее. Посмотрите на епископа:
function bishopMoves(square, board) {
var oSlide = function(direction) {
return slide(square, direction, board);
}
return [].concat(oSlide(11), oSlide(-11), oSlide(9), oSlide(-9));
}
function slide(square, direction, board) {
var moves = [];
for(var pos = direction + an2i(square); board[pos] != -1; pos += direction) {
// in a real implementation you'd also check whether
// the squares you encounter are occupied
moves.push(board[pos]);
}
return moves;
}
Вот несколько примеров:
knightMoves("h1", generateEmptyBoard()) => ["f2", "g3"]
bishopMoves("a4", generateEmptyBoard()) => ["b3", "c2", "d1", "b5", "c6", "d7", "e8"]
Обратите внимание, что функция slide является общей реализацией. Вы должны иметь возможность легко моделировать правовые движения других скользящих элементов.
Ответ 9
Использование битовой доски было бы эффективным способом представления состояния шахматной доски. Основная идея заключается в том, что вы используете 64-битные биты для представления каждого из квадратов на доске, где первый бит обычно представляет A1 (нижний левый квадрат), а 64-й бит представляет H8 (диагонально противоположный квадрат). Каждый тип предмета (пешка, король и т.д.) Каждого игрока (черный, белый) получает свою собственную доску, и все 12 из этих досок составляют состояние игры. Для получения дополнительной информации ознакомьтесь с этой статьей .
Ответ 10
Я бы использовал многомерный массив, чтобы каждый элемент в массиве был ссылкой на квадрат на доске.
Таким образом,
board = arrary(A = array (1,2,3,4,5,5,6,7,8),
B = array (12,3,.... etc...
etc...
)
Затем доска [A] [1] является квадратом платы A1.
В действительности вы должны использовать числа, не содержащие буквы, чтобы помочь логике математики, где части разрешены для перехода к простым.
Ответ 11
int[8][8]
0=no piece
1=king
2=queen
3=rook
4=knight
5=bishop
6=pawn
использовать положительные ints для белых и отрицательных int для черного
Ответ 12
Я бы не смоделировал шахматную доску, я бы только смоделировал положение фигур. Тогда у вас могут быть границы для шахматной доски.
Piece.x= x position of piece
Piece.y= y position of piece
Ответ 13
Я знаю, что это очень старое сообщение, которое я наткнулся на несколько раз, когда программирование по шахматам в googling, но я чувствую, что я должен упомянуть, что вполне возможно смоделировать шахматную доску с 1D массивом, например. шахматная доска [64];
Я бы сказал, что это самый простой подход к представлению шахматной доски... но, конечно, это базовый подход.
Является ли структура массива 1D более эффективной, чем 2D-массив (для которого необходим вложенный цикл для доступа и управления индексами)?
Также возможно использовать 1D-массив с более чем 64 квадратами для представления квадратов OffBoard, например, шахматная доска [120]; (с правильной инициализацией массива дозорных и игровых квадратов).
Наконец, для полноты этого сообщения, я чувствую, что должен упомянуть представление массива 0x88. Это довольно популярный способ представить шахматную доску, которая также учитывает внешние квадраты.
Ответ 14
Массив, вероятно, будет в порядке. Если вам нужны более удобные средства "перемещения" доски, вы можете легко создавать методы для абстрагирования деталей реализации структуры данных.