Ответы в темах
-
Сообщения
-
Уж намекал как мог…
Ну, ладно если для Вас это так важно, извольте 😉
int PST_man[45] = { 0,0,0,0,0,
0, 0, 0, 0,
-30, 10, 10, 10, 0,
10, 10, 10, -30,
-10, 10, 10, 10, 0,
10, 10, 10, -10,
-10, 10, 10, 10, 0,
10, 10, 10, -10,
-10, 20, 20, 10, 0,0,0,0,0
};
То, что хорошо работает в одной программе, может работать очень плохо в другой.
Мне Ваш научный подход нравится, :clap: но всё-таки … на скольких партиях Вы делаете прогон эксперимента: 5, 50, 2000 ? И кто играет — разные версии программы (старая и новая) ?
АЛЕМОИграют старая новая около 1000 партий (или пока не станет ясен результат). Маленькая проблема в том, что стартовые позиции берутся из летающих шашек. Нигде не смог найти для поддавков 😥
Меня интересует КОНКРЕТНЫЙ случай!
Какие цифры у вас в поддавочной программе на спутнике Юпитера? (Если я еще что-то помню из школьной программы — Каллисто).
Невежливо задавать такие интимные вопросы на форуме 😳
Каллисто — это богиня в честь которой назвали спутник Юпитера ❗
сколько же у Вас партий (позиций) в базе данных, на основе которой вы делаете статистику ?
Ценность полей определяется исходя из экспериментов. Никакой базы данных для этого не нужно.Ставим h6 — +3 и прога начинает сливать все подряд. Значит оценка неправильная.
Пробуем h6 — -3 и прога играет заметно лучше. Значит это значение и оставляем.
Например,
a1 — -1
c1 — +1
e1 — +1
g1 — +1
b2 — +1
d2 — +1
f2 — +1
h2 — 0… и т.д.
Конкретные числа нужно подбирать экспериментально.
Не совсем согласен с предыдушим сообщением. Поля b4,d4,b6 и т.д.
бывают невыгодны для белых так как черные могут зачастую построить конструкцию (то есть создать угрозу отдачи всех шашек) под эти поля и белым придется отдавать материал и компьютер при достаточной глубине перебора не пойдет на этот вариант. Если же конструкцию построить не удается то, как правило, эти поля можно и нужно занимать. Впрочем в этой теме это, скорее всего, оффтопикЕсли здесь это оффтопик, то как-нибудь открою отдельный топик для этой темы. Когда будет время в этом серьезно разбираться.
У меня не все бортовые плохи скопом. a7 и h6 особенно.
c1, e1 и g1 даже хорошие.Это необязательно. Вполне достаточно создать два дополнительных битборда, где будут указаны невозможные поля для хода влево и вправо и перед тем как производить соответствующие сдвиги просто сделать AND с расположением простых. Тогда, к примеру, простые a1 a3 a5 a7 будут замаскированы и в дальнейшем не будут принимать участие в «ходе влево».
Это понятноЯ имел ввиду другое.
Чтобы получить ходы налево начинающиеся на нечетных горизонталях нужно сдвигать на 3.
Чтобы получить ходы налево начинающиеся на четных горизонталях нужно сдвигать на 4.
Чтобы получить ходы направо начинающиеся на нечетных горизонталях нужно сдвигать на 4.
Чтобы получить ходы направо начинающиеся на четных горизонталях нужно сдвигать на 5.Как это все красиво совместить я не придумал. Поэтому и отказался от битбордов.
Даже одна из лучших чекерсных прог Cake использует битборды с генерацией в 4 этапа.
Я как-то говорил с Виталием Камыниным об этом. Насколько я его понял Тундра тоже генерит ходы так.booot! Может ты придумал что-то революционно новое?
Максимум до чего я могу додуматься это генерить в три этапа:
1. поля, которые можно сдвигать на 3.
2. поля, которые можно сдвигать на 4. Здесь будут объединены ходы направо и налево.
3. поля, которые можно сдвигать на 5.А можно взглянуть, что это за зверь такой — ценность полей в поддавках?
Ну это совсем просто. Бортовые — плохо. Центральные хорошо.
На самом деле у меня материальный баланс совмещен с ценностью полей. Только дамки оцениваются вне зависимости от положения на доске. Для поддавков эта совмещенность оправдана с логической точки зрения, т.к. важно не просто кол-во шашек, а кол-во хороших шашек. А плохие шашки только ухудшают позицию.
Да, кстати, типы срубленных шашек (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;
}
Названия функций несколько неудачные. Надо будет переделать.
Когда это все писал в голове еще не было ясной и полной картины того, что должно получиться в итоге.Начнем с более простого метода использования массивов.
Доска представляется простым массивом:
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). Планирую выложить их для скачивания в ближайшем будущем.
В CheckerBoard совсем отсутствует юзабилити.
Даже нельзя установить контроль времени на партию.
Нет возможности запустить матч двух программ (не говорю уже о турнире нескольких).У меня есть оболочка с открытым интерфейсом. Но это никому из программистов не надо.
Все равно ее выложу через пару недель. Может хоть начинающие програмеры будут писать движки для нее.Я и не говорил, что безранговые базы помогают выиграть все позиции.
Все дело в том, что такие позиции в реальных партиях случаются очень редко.И если гросс может выиграть такую позу, то можно научить и программу. Было бы желание.
19 — 1. Это я имел ввиду только результативные партии (без ничьих).
Вот вам подобный пример из шахмат: ферзь против ладьи. 98% позиций выиграно, но написать оценочную, чтоб выиграть только по безранговой базе по крайней мере у меня не получилось (правило 50 ходов мучает). А эндшпиль — вполне игровой.Для этого случая в теории шахмат есть специальные правила (т.е. общие не подходят). Все легко решается с помощью оценочной функции, если знать теорию.
В шашках то же самое. Нужно просто теорию про исключительные позиции знать.
Например, треугольник Петрова не явл. исключением, т.к. строится из общих соображений.
Вот вам подобный пример из шахмат: ферзь против ладьи. 98% позиций выиграно, но написать оценочную, чтоб выиграть только по безранговой базе по крайней мере у меня не получилось (правило 50 ходов мучает). А эндшпиль — вполне игровой.Для этого случая в теории шахмат есть специальные правила (т.е. общие не подходят). Все легко решается с помощью оценочной функции, если знать теорию.
В шашках то же самое. Нужно просто теорию про исключительные позиции знать.
Например, треугольник Петрова не явл. исключением, т.к. строится из общих соображений.
Вот вам подобный пример из шахмат: ферзь против ладьи. 98% позиций выиграно, но написать оценочную, чтоб выиграть только по безранговой базе по крайней мере у меня не получилось (правило 50 ходов мучает). А эндшпиль — вполне игровой.Для этого случая в теории шахмат есть специальные правила (т.е. общие не подходят). Все легко решается с помощью оценочной функции, если знать теорию.
В шашках то же самое. Нужно просто теорию про исключительные позиции знать.
Например, треугольник Петрова не явл. исключением, т.к. строится из общих соображений.Интересно, а на чем должна основываться оценочная функция в поддавках???
Моя прога в поддавки играет очень сильно. По оценкам Левита и нескольких человек сранивавших с Тундрой.
Моя оценочная функция состоит из баланса материала + ценность полей.
Для поддавков придумать что-то большее очень тяжело. Некоторые даже баланс правильно подсчитать не могут
