Генератор возможных ходов

Главная › Форумы › Шашечные программы › Шашечные программы › Генератор возможных ходов

Просмотр 15 сообщений - с 16 по 30 (из 58 всего)
1 2 3 4
  • Автор
    Сообщения
  • 16.01.2006 в 20:58 #360407
    alex
    Участник

    Небольшое уточнение к последнему посту. Я играл небольшой матч с Тундрой (с 6-фигурной ЭБ) и с полсотни партий с Каллисто (5-фигурная ЭБ). Все это с довольно коротким котролем 5-10 минут на партию. Первый матч я выиграл с небольшим перевесом, что-то около 8-6. Во втором был разбит на голову: выиграл партий 10-15, кажется сделал одну ничью и проиграл остальные. Каллисто как мне кажется играла более «по-человечески». Про силу Тундры с 8-ми фигуркой ничего сказать не могу.

    17.01.2006 в 05:27 #360408
    Jury
    Участник

    Современные сильнейшие проги используют оба подхода.
    Каллисто — массив.
    Тундра — битовые поля.

    Если кому-нибудь интересно могу рассказать об этих подходах более подробно.

    C большим интересом почитал бы.

    17.01.2006 в 06:55 #360409
    Kallisto
    Участник

    Начнем с более простого метода использования массивов.

    Доска представляется простым массивом:

    int Board[45];

    Соответствия полей доски индексам в массиве


    
5   6   7   8
    
9  10  11  12
    
14  15  16  17
    
18  19  20  21
    
23  24  25  26
    
27  28  29  30
    
32  33  34  35
    
36  37  38  39

    Т.е. «b8» — индекс 5, «d8» — 6, …, «e1» — 38, «g1» — 39
    На всякий случай напомню индексация массива начинается с нуля.

    Важно обратить внимание на то, что индексы 13, 22, 31, первые и последние пять не отображаются ни на какое поле доски. В них записываем спец. константу-сторож, означающую выход за пределы доски.
    Если это понять, то больше идеалогических затруднений быть не должно.

    Ходы будут представляться такой структурой:


    
struct Move {
    
int from; // индекс поля откуда ходим
    
int to; // индекс поля куда ходим
    
bool promotion; // флаг превращения в дамку
    
int cap_sq[12]; // список индексов полей сбитых шашек оканчивающийся нулем, вся надежда, что нельзя одним ходом сбить более 11 шашек :)
    
int cap_type[12]; // типы сбитых шашек
    
};

    Вроде все просто…

    Вначале пытаемся генерировать взятия.


    
void GenerateCaptures()
    
{
    
for (int sq = 5; sq < 40; ++sq) { // ищем шашки по всей доске
    
if (Board[sq] & stm) { // нашли шашку нужного цвета
    
if (Board[sq] & KING) {
    
// пробуем взятия дамкой на все 4 стороны (по диагоналям, т.е. -4, -5, 4, 5)
    
TryKingCapture(sq, -4);
    
TryKingCapture(sq, -5);
    
TryKingCapture(sq, 4);
    
TryKingCapture(sq, 5);
    
}
    
else {
    
// пробуем взятия простой по 4 направлениям
    
TryManCapture(sq, -4);
    
TryManCapture(sq, -5);
    
TryManCapture(sq, 4);
    
TryManCapture(sq, 5);
    
}
    
}
    
}
    
}

    Если взятий нет, то генерируем остальные ходы.


    
void GenerateSilentMoves()
    
{
    
for (int sq = 5; sq < 40; ++sq) {
    
if (Board[sq] & stm) {
    
if (Board[sq] & KING) {
    
AddKingMoves(sq, -4);
    
AddKingMoves(sq, -5);
    
AddKingMoves(sq, 4);
    
AddKingMoves(sq, 5);
    
}
    
else {
    
// направления хода простых зависит от того кто сейчас ходит
    
// stm == 1   -   белые
    
// stm == 2   -   черные
    
static const ForwardDirections[2][2] = {{-4, -5}, {4, 5}};
    
AddManMove(sq, ForwardDirections[stm - 1][0]);
    
AddManMove(sq, ForwardDirections[stm - 1][1]);
    
}
    
}
    
}
    
}

    Функция генерирующая ход простой шашки с поля с индексом sq, в направлении dir:


    
inline void AddManMove(int sq, int dir)
    
{
    
if (Board[sq + dir] == 0) { // если поле пустое, то можно ходить
    
MP->from = sq;
    
MP->to = sq + dir;
    
MP->cap_sq[0] = 0; // нет взятий
    
MP->promotion = MP->to < 9 || MP->to > 35; // превращение если ходим на первую или последнюю линию
    
++MP;
    
}
    
}

    MP — это указатель на массив в котором храниться список ходов.

    Функция генерирующая ходы дамки с поля с индексом sq, в направлении dir:


    
inline void AddKingMoves(int sq, int dir)
    
{
    
for (int to = sq + dir; Board[to] == 0; to += dir) {
    
MP->from = sq;
    
MP->to = to;
    
MP->cap_sq[0] = 0;
    
MP->promotion = false;
    
++MP;
    
}
    
}

    Для ускорения этой генерации можно добавить списки белых и черных шашек. Тогда шашки не надо будет искать по всей доске, а просто пройти по списку.

    Как именно генерировать ходы со взятиями это уже техническая сторона вопроса. Причем, технически шашечный генератор сложнее шахматного.
    Интересно это кому-нибудь :?:

    Если кого-нибудь интересуют битборды, то могу рассказать. Только без исходников.

    Все исходники, что здесь приведены от движка SiDra (Simple Draughts). Планирую выложить их для скачивания в ближайшем будущем.

    17.01.2006 в 09:00 #360410
    Jury
    Участник

    Спасибо, очень интересно почитать, однако то, что написано можно реализовать и гораздо более тупым и прямолинейным образом, и для этого достаточно иметь небольшой опыт программирования на Бейсике. Мысль веду к тому, что самую сложность как раз составляет TryKingCapture, т.к. реализовать правило «дамка должна рубить все стоящие на пути шашки» самая сложная задача в генераторе ходов. Чтобы не пользоваться умными словесами приведу пример для тех, кто, возможно не вполне понимает задачу (мне ее проще понять). Имеем белую дамку на a1 и черные фигуры на b2 и с7. Единственый разрешенный правилами ход — a1:e5:c7, однако TryKingCapture() нагенерит сначала a1:c3, a1:d4, a1:e5, a1:f6, a1:g7, a1:h8. Но т.к. с поля e5 есть возможность срубить, то остальные взятия надо отбрасывать. Собственно эта сложность и является отличием от генерилки шахматных ходов. Помнится где-то видел интересную задачку, где есть одна белая дамка (на b8 вроде) и куча черных решетчато расположенных, и надо было найти правильный ударный ход. Оных там было ну очень много.
    Да, кстати, типы срубленных шашек (cap_type[12] в struct Move) возможно в программировании русских шашек и не понадобятся, но очень будут нужны при выборе взятия в итальянском чекерсе.

    Про BitBoard тоже интересно, думаю что не только мне, но видимо смелости у меня только и хватило попросить :). Может уважаемый booot присоединится?

    17.01.2006 в 10:07 #360411
    booot
    Участник

    Мысль веду к тому, что самую сложность как раз составляет TryKingCapture, т.к. реализовать правило «дамка должна рубить все стоящие на пути шашки» самая сложная задача в генераторе ходов.

    Процедуры TryKingCaptrure и TryManCapture удобнее всего делать рекурсивными. У меня, к примеру, один экземпляр процедуры TryKingCapture при обнаружени возможности взятий вызывает следующих экземпляр процедуры TryKingCapture, передавая ему в качестве параметров список побитых шашек противника (чтоб по нескольку раз не бить одну и ту же). Запись легальных ходов в массивы, таким образом осуществляется на самом нижнем уровне рекурсии, когда текущих взятий в очередной раз уже не найдется.

    Про BitBoard тоже интересно, думаю что не только мне, но видимо смелости у меня только и хватило попросить

    В двух словах расскажу тут, если нужны будут материалы — могу по почте кинуть. Представление доски с помощью битбордов означает, что каждому полю шашечной доски (их 32) назначается в соответствие 1 бит 32-разрядного целочисленного числа. К примеру полу а1 соответствует 0-й бит, c1 — 1-й бит…h8 — 31-й бит. Если шашка стоит на этом поле — бит устанавливается в «1», если поле пустое — в «0». К примеру передача в процедуру TryKingCapture всех побитых шашек противника означает передачу простого целочисленного 32-разрядного числа с установленными битами, соответствующими положению побитых шашек противника на доске. Установка/снятие бита производится логическими командами Or и AND. Для корректного представления доски достаточно 3 битбордов (12 байт памяти) — whitepieses (белые фигуры), blackpieses (черные фигуры) и kings (дамки обоих цветов). С помощью этих битбордов простейшими логическими операциями мы можем получать любую интересующую нас информацию. К примеру: найти положение всех белых дамок (whitepieses and kings), всех белых простых: (whitepieses and (not kings)). Для генерирования ходов я использую предвычисляемые массивы битбордов, индексируемые по полю шашечной доски, и содержащие битбоды полей, на которые может пойти шашка. Пример: чтоб найти все ходы шашки b2 я использую: WhiteSimpleMoves[b2] and (not (whitepieses or blackpieses)). В результате получаю битборд, содержащий ходы белой шашки b2 на свободные поля.
    Удобство битбордов состоит в том, что можно работать со структурами шашек параллельно, используя нужные логические команды процессора.

    17.01.2006 в 12:01 #360412
    Kallisto
    Участник

    Да, кстати, типы срубленных шашек (cap_type[12] в struct Move) возможно в программировании русских шашек и не понадобятся, но очень будут нужны при выборе взятия в итальянском чекерсе.

    cap_type[12] нужен для отката ходов. В процессе перебора вариантов надо уметь возвращать ходы назад.
    Хотя, может быть эффективнее просто запоминать старую позицию, а потом ее восстанавливать простым копированием. Особенно это выгодно, если позиция занимает всего 3 целых числа, как у booot.

    Пример: чтоб найти все ходы шашки b2 я использую: WhiteSimpleMoves[b2] and (not (whitepieses or blackpieses)). В результате получаю битборд, содержащий ходы белой шашки b2 на свободные поля.

    Тут не используется иделогия параллельной обработки. Лучше найти сразу все возможные конечные поля для ходов влево, а потом их генерить, доставая по одному биту из битборда. Затем то же для всех ходов вправо.
    Первые поля для взятий тоже можно получить сразу все (для одного направления) за несколько логических операций. Потом, каждое взятие придется генерить рекурсивно.
    Для этого удобнее использовать битборд из 64 бит.
    Если использовать 32 бита, то приходится сначала генерить:
    — все ходы влево с четных горизонталей
    — все ходы влево с нечетных горизонталей
    — все ходы вправо с четных горизонталей
    — все ходы вправо с нечетных горизонталей

    Это из-за ассиметрии шашечной доски.

    А если брать шашки одну за другой и просто генерить ходы, то непонятно зачем вообще тогда использовать битборды.
    Правда, выигрыш в скорости, я думаю, здесь все равно будет незначительным. Т.к. он достигается только когда на доске есть заблокированные шашки. Массивы вынуждены все-равно такие шашки просматривать, а битборды их просто не замечают (значит экономится время).

    Основной выигрыш битбордов при генерации это возможность быстро проверить есть ли взятия в данной позиции при помощи нескольких логических операций.
    Если использовать массивы, то для этого нужно просматреть все шашки и проверить все 4 диагонали на возможность взятия.
    Т.к. проверка возможности взятия достаточно критичное место для шашечного алгоритма, то здесь можно получить достаточно неплохой выигрыш в скорости.

    Я даже может как-нибудь попробую реализовать это и сравнит с тем что у меня есть.

    реализовать правило «дамка должна рубить все стоящие на пути шашки» самая сложная задача в генераторе ходов
    Приведу просто код (но с комментариями), т.к. booot все более менее объяснил.


    

    
inline void TryKingCapture(int sq, int dir)
    
{
    
int m = sq + dir;
    
while (!Board[m]) m += dir; // ищем первое препятствие на этом направлении
    
if (!OP_CHECKER(m)) return; // если это не шашка противника, то нет взятий
    
int to = m + dir; // перепрыгиваем ее
    
if (Board[to]) return; // если следующее поле не пусто, то бить нельзя
    
Move t; // сюда будем записывать текущее взятие
    
t.from = sq; // откуда бьем
    
t.promotion = false; // дамка не превращается
    
AddCaptured(m, &t, 0); // добавляем к списку сбитых шашку, которую только что перепрыгнули
    
AddKingCaptures(to, &t, 1, dir); // ищем возможные продолжения взятия
    
}
    

    
// поиск возможных продолжений взятия
    
void AddKingCaptures(int sq, Move *t, int caps, int dir)
    
{
    
int found = 0; // пока никаких новых взятий не нашли
    
int m = sq;
    
while (!Board[m]) { // просматриваем всю диагональ пока не наткнемся на препятствие
    
// и пытаемся найти взятия вбок
    
KingCapture(m, t, caps, -4, dir, found);
    
KingCapture(m, t, caps, -5, dir, found);
    
KingCapture(m, t, caps,  4, dir, found);
    
KingCapture(m, t, caps,  5, dir, found);
    
m += dir;
    
}
    
int to = m + dir;
    
if (OP_CHECKER(m) && !Board[to] && AddCaptured(m, t, caps)) {
    
// если препятствие окозалось вражеской шашкой, а за ней пустое поле и эту шашку мы еще не сбивали, значит нашли новое взятие
    
AddKingCaptures(to, t, caps + 1, dir);	// опять ищем возможные продолжения взятия
    
return;
    
}
    
if (!found) { // не нашли продолжение взятие, значит можно генерить очередной ход
    
do {
    
CopyMoveFromTemplate(t, caps); // берем ход из шаблона
    
MP->to = sq; // остается обновить только конечное поле
    
++MP;
    
sq += dir;
    
} while (!Board[sq]);
    
}
    
}
    

    
// поиск возможных продолжений взятия вбок
    
inline void KingCapture(int sq, Move *t, int caps, int dir, int bad_dir, int &found)
    
{
    
if (dir == bad_dir || dir == -bad_dir) return; // здесь рассматриваются только продолжения взятия вбок
    
int m = sq + dir;
    
while (!Board[m]) m += dir;
    
if (!OP_CHECKER(m)) return;
    
int to = m + dir;
    
if (Board[to]) return;
    
if (!AddCaptured(m, t, caps)) return; // если мы эту шашку уже сбивали
    
found = 1; // нашли новое взятие
    
AddKingCaptures(to, t, caps + 1, dir); // ищем продолжения взятия
    
}
    

    
// добавить сбитую шашку к списку
    
inline bool AddCaptured(int sq, Move *m, int caps)
    
{
    
// проверяем не сбивали ли мы эту шашку раньше
    
for (int i = 0; i < caps - 3; ++i) {
    
if (sq == m->cap_sq)	return false;
    
}
    
// еще не сбивали, значит можно сбивать
    
m->cap_sq[caps] = sq;
    
m->cap_type[caps] = Board[sq];
    
return true;
    
}

    Названия функций несколько неудачные. Надо будет переделать.
    Когда это все писал в голове еще не было ясной и полной картины того, что должно получиться в итоге.

    17.01.2006 в 12:26 #360413
    booot
    Участник

    Тут не используется иделогия параллельной обработки. Лучше найти сразу все возможные конечные поля для ходов влево, а потом их генерить, доставая по одному биту из битборда. Затем то же для всех ходов вправо.

    Пример выше был для удобства приведен :-). Конечно использовать логический сдвиг всего битборда простых влево или вправо эффективнее.

    «Если использовать 32 бита, то приходится сначала генерить:
    — все ходы влево с четных горизонталей
    — все ходы влево с нечетных горизонталей
    — все ходы вправо с четных горизонталей
    — все ходы вправо с нечетных горизонталей»

    Это необязательно. Вполне достаточно создать два дополнительных битборда, где будут указаны невозможные поля для хода влево и вправо и перед тем как производить соответствующие сдвиги просто сделать AND с расположением простых. Тогда, к примеру, простые a1 a3 a5 a7 будут замаскированы и в дальнейшем не будут принимать участие в «ходе влево».

    17.01.2006 в 14:20 #360414
    Fenix
    Участник

    Моя оценочная функция состоит из баланса материала + ценность полей.
    Для поддавков придумать что-то большее очень тяжело. Некоторые даже баланс правильно подсчитать не могут :)

    А можно взглянуть, что это за зверь такой — ценность полей в поддавках?

    17.01.2006 в 15:14 #360415
    Kallisto
    Участник

    А можно взглянуть, что это за зверь такой — ценность полей в поддавках?

    Ну это совсем просто. Бортовые — плохо. Центральные хорошо.

    На самом деле у меня материальный баланс совмещен с ценностью полей. Только дамки оцениваются вне зависимости от положения на доске. Для поддавков эта совмещенность оправдана с логической точки зрения, т.к. важно не просто кол-во шашек, а кол-во хороших шашек. А плохие шашки только ухудшают позицию.

    17.01.2006 в 15:38 #360416
    Kallisto
    Участник

    Это необязательно. Вполне достаточно создать два дополнительных битборда, где будут указаны невозможные поля для хода влево и вправо и перед тем как производить соответствующие сдвиги просто сделать AND с расположением простых. Тогда, к примеру, простые a1 a3 a5 a7 будут замаскированы и в дальнейшем не будут принимать участие в «ходе влево».
    Это понятно

    Я имел ввиду другое.

    Чтобы получить ходы налево начинающиеся на нечетных горизонталях нужно сдвигать на 3.
    Чтобы получить ходы налево начинающиеся на четных горизонталях нужно сдвигать на 4.
    Чтобы получить ходы направо начинающиеся на нечетных горизонталях нужно сдвигать на 4.
    Чтобы получить ходы направо начинающиеся на четных горизонталях нужно сдвигать на 5.

    Как это все красиво совместить я не придумал. Поэтому и отказался от битбордов.

    Даже одна из лучших чекерсных прог Cake использует битборды с генерацией в 4 этапа.
    Я как-то говорил с Виталием Камыниным об этом. Насколько я его понял Тундра тоже генерит ходы так.

    booot! Может ты придумал что-то революционно новое?

    Максимум до чего я могу додуматься это генерить в три этапа:
    1. поля, которые можно сдвигать на 3.
    2. поля, которые можно сдвигать на 4. Здесь будут объединены ходы направо и налево.
    3. поля, которые можно сдвигать на 5.

    17.01.2006 в 16:25 #360417
    booot
    Участник

    booot! Может ты придумал что-то революционно новое?
    Максимум до чего я могу додуматься это генерить в три этапа:
    1. поля, которые можно сдвигать на 3.
    2. поля, которые можно сдвигать на 4. Здесь будут объединены ходы направо и налево.
    3. поля, которые можно сдвигать на 5.

    Тут сложно что-то революционное придумать :-). Те же 3 этапа. Просто я не считаю это потерей стройности: если с точки зрения скорости это оправдано, то компактность кода меня интересует уже во вторую очередь. Плюс ко всему надо ж не забывать, что генератор ходов это еще не вся шашечная программа, есть еще и оценочная функция. И лично мне работать в ней с битбордами будет комфортнее чем с массивами и списками. Но это лично мое мнение.

    Вообще-то какой формат для описания доски использовать — дело вкуса. Генератор ходов, конечно, влияет на общую производительность программы, но не слишком принципиально. Я это понял когда в своей шахматной програмее решил перейти со старой непроизводительной MailBox системы сразу на вращающиеся битборды. По perfomance тесту получил дикий прирост скорости генерирования. Но в целом программа не так уж и усилилась — все же есть более важные ее части для прироста силы игры чем генератор ходов.

    17.01.2006 в 21:17 #360418
    Fenix
    Участник

    А можно взглянуть, что это за зверь такой — ценность полей в поддавках?

    Ну это совсем просто. Бортовые — плохо. Центральные хорошо.

    На самом деле у меня материальный баланс совмещен с ценностью полей. Только дамки оцениваются вне зависимости от положения на доске. Для поддавков эта совмещенность оправдана с логической точки зрения, т.к. важно не просто кол-во шашек, а кол-во хороших шашек. А плохие шашки только ухудшают позицию.

    Дело в том, что для поддавков не все центральные поля (скопом) хороши. Впрочем как и не все бортовые плохи.

    Для белых: (без нюансов — в первом приближении)

    бортоые поля
    плохи а7 а5 h6
    менее плохи а3 и h4
    не так уж и плохи h2

    центральные поля
    хороши b2 d2 f2 c3 e3 g3 c5 e5 g5
    плохи b4 d4 f4 b6 d6 f6 c7 e7 g7

    17.01.2006 в 22:16 #360419
    alex
    Участник

    Не совсем согласен с предыдушим сообщением. Поля b4,d4,b6 и т.д.
    бывают невыгодны для белых так как черные могут зачастую построить конструкцию (то есть создать угрозу отдачи всех шашек) под эти поля и белым придется отдавать материал и компьютер при достаточной глубине перебора не пойдет на этот вариант. Если же конструкцию построить не удается то, как правило, эти поля можно и нужно занимать. Впрочем в этой теме это, скорее всего, оффтопик

    18.01.2006 в 05:44 #360420
    Kallisto
    Участник

    Не совсем согласен с предыдушим сообщением. Поля b4,d4,b6 и т.д.
    бывают невыгодны для белых так как черные могут зачастую построить конструкцию (то есть создать угрозу отдачи всех шашек) под эти поля и белым придется отдавать материал и компьютер при достаточной глубине перебора не пойдет на этот вариант. Если же конструкцию построить не удается то, как правило, эти поля можно и нужно занимать. Впрочем в этой теме это, скорее всего, оффтопик

    Если здесь это оффтопик, то как-нибудь открою отдельный топик для этой темы. Когда будет время в этом серьезно разбираться.

    У меня не все бортовые плохи скопом. a7 и h6 особенно.
    c1, e1 и g1 даже хорошие.

    18.01.2006 в 11:31 #360421
    Fenix
    Участник

    Не совсем согласен с предыдушим сообщением. Поля b4,d4,b6 и т.д.
    бывают невыгодны для белых так как черные могут зачастую построить конструкцию (то есть создать угрозу отдачи всех шашек) под эти поля и белым придется отдавать материал и компьютер при достаточной глубине перебора не пойдет на этот вариант. Если же конструкцию построить не удается то, как правило, эти поля можно и нужно занимать. Впрочем в этой теме это, скорее всего, оффтопик

    Если здесь это оффтопик, то как-нибудь открою отдельный топик для этой темы. Когда будет время в этом серьезно разбираться.

    У меня не все бортовые плохи скопом. a7 и h6 особенно.
    c1, e1 и g1 даже хорошие.

    Kallisto
    1) Об этом и спрашивал. Как всё же распределяется по доске «хорошесть» и «плохость» полей?

    alex
    2) В своем последнем письме так и написал: «без нюансов — в первом приближении»

  • Автор
    Сообщения
Просмотр 15 сообщений - с 16 по 30 (из 58 всего)
1 2 3 4
  • Для ответа в этой теме необходимо авторизоваться.