2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 12:44 


10/04/12
704
Не все же окончания нужно смотреть за один раз? Вообще, в основном цикле надо работать только с данными для окончаний одного типа. И только на первом проходе смотреть младшие эндшпиля. Например, при первом проходе вы генерируете все хода, и ставите оценку в тех случаях, когда есть переход в младший выигрывающий эндшпиль или уничтожаются все шашки противника или запирание. Потом у вас уже будет проставлены ходы до выигрыша в случае, если ход приводит к моментальному выигрышу ($n=1$), или позиции, для которых есть переход в младшее окончание (тут мы знаем, что позиция выигрывается не более чем за $N_0$ ходов, но в реале оптимальное $N^{*}$ может быть меньше..

Дальше мы в младшие окончания не заглядываем. Берем $n=2$ (до выигрыша два полухода), и смотрим, можем ли мы улучшить проставленные ранее результаты, где $N>2$, а также прописываем оценку для окончаний, у которых нет оценки.

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

Кстати, для задачи идеально подходит OpenCL.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 13:10 
Аватара пользователя


10/11/12
121
Бобруйск
Не, я не ставлю вопрос о генерации базы. Там всё более-менее понятно.
Мне интересен вопрос об эффективном применении в практической игре - как достичь максимальной скорости доступа к оценкам

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 13:15 


10/04/12
704
Это у авторов Shredder надо спрашивать. Там таблицы хорошо укапоканы - меньше места, больше в память поместится. Навскидку, базу надо бы как-то упаковать, но в целом судя по анализу, движок не часто обращается к таблицам Налимова, большей частью проверяет только оптимальную ветку при альфа-бете. Число обращений к таблице Налимова растет не очень быстро.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 13:23 
Аватара пользователя


10/11/12
121
Бобруйск
mustitz в сообщении #806825 писал(а):
Число обращений к таблице Налимова растет не очень быстро.

Ясно, вот это я и хотел услышать. Значит можно просто делать кучу файлов и считывать то, что надо, надеясь, что число обращений к жесткому диску не будет большим. Претендовать на самую лучшую организации базы я не собираюсь. :wink:

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 13:36 


10/04/12
704
Как минимум для начала это нормальный вариант.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 14:11 
Аватара пользователя


10/11/12
121
Бобруйск
mustitz в сообщении #805415 писал(а):
Три простые можно расположить $ 28 \choose 3 $ различными способами (комбинаторная система для перечисления).
для сочетания 860 получаем номер
$$ { 8 \choose 3 } + { 6 \choose 2 } + { 0 \choose 1} = 56 + 15 + 0 = 71 $$

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

(Оффтоп)

mustitz, просто интересно, вы занимались программированием шашек? Много нового узнал от вас.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение27.12.2013, 19:48 
Аватара пользователя


10/11/12
121
Бобруйск
Хмм...
У нас ведь есть замечательный массив choose[][].
Есть идея!
Проще показать на примере:

Пусть у нас 3 шашки на 28 полях, сочетание {860}, номер 71. Определим сочетание по его номеру:
$${27 \choose 3}=2925>71 \rightarrow {26 \choose 3}=2600>71 \rightarrow \cdots \rightarrow {9 \choose 3}=84>71 \rightarrow {8 \choose 3}=56 \leqslant 71 \Rightarrow c_3=8$$
$$71-56=15 \qquad {7 \choose 2}=21>15 \rightarrow {6 \choose 4}=15 \leqslant 15 \Rightarrow c_2=6$$
$$15-15=0 \Rightarrow c_1=0$$
{c3,c2,c1}={860}.
Готово!

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

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение10.05.2018, 17:17 


10/04/12
704
Vovka17,
Немного вспомнил эту тему. У меня генерация всех 6-фигурных окончаний в русских шашках в DTC метрике заняло 2 часа, 16G оперативной памяти и 2.7G места на жёстком диске. Сильно дотошно не проверял, треугольник Петрова построила и ладно.
Пощупать можно на github.com/mustitz/checkers
Уже сгенерированные бинарники лежат в ветке github.com/mustitz/checkers/tree/etb-bin
Разрабатывал под Linux, проверял там же. В принципе, там ничего военного не используется, поэтому если есть C99 компилятор, то не думаю что будет сложно пересобрать.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение30.07.2018, 21:39 


10/04/12
704
Немного продолжая шашечную тему, можно потестировать алгоритм MCTS для русский шашек (alpha).
Шашки http://35.204.55.174/
Надо нажать “New Game White” или “New Game Black” и играть

Сервер слабый (Google Cloud, 1 CPU), так что если тормозит лучше играть медленнее :)
Уровень игры не очень, надо усиливать. Писал для себя, не тестировал сильно. Работает под Chrome для Linux, под Edge 100% не должен работать. Под Android тоже не работает.

Параметры алгоритма: 250 000 симуляций (поэтому в конце игры немного ускоряется), случайное доигрывание, используются шестифигурные таблицы окончаний.

Исходники чуть подправлю и выложу, если будет кому интересно.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение30.07.2018, 22:30 


21/05/16
4292
Аделаида
mustitz в сообщении #1329627 писал(а):
под Edge 100% не должен работать

Работает.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение31.07.2018, 12:02 


10/04/12
704
Обещанные исходники https://gitlab.com/mustitz/rus-checkers (или https://github.com/mustitz/checkers).

Значит Microsoft делают свой браузер более совместимым :) Просто раньше у меня не работал в IE, а сейчас и протестировать негде :)

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение31.07.2018, 13:35 


15/11/15
916
А почему нельзя сделать "в лоб": создать в таблице поля:

a1 a3 a5 a7 b2 b4 b6 b8 c1 c3 ...

перечисляемого типа со значениями: П (пусто), б, Б, ч, Ч (большая буква значит дамка соотв. цвета).
Или это превратить в одно ключевое поле a1П-a3б-a5П-a7ч-b2П-b4б-b6П-b8Б-c1Ч-c3ч... . Но обычно не есть гуд так.

Плюс дополнительные поля:

- Легальная позиция да/нет
- кто победил ч/б/ничья
- прочее...

Поиск в субд обычно быстр сегодня...
Потом написать скрипты и забивать базу известными комбинациями.

 Профиль  
                  
 
 Re: Программирование баз окончаний русских шашек
Сообщение31.07.2018, 15:41 


10/04/12
704
gevaraweb в сообщении #1329741 писал(а):
Поиск в субд обычно быстр сегодня...
Потом написать скрипты и забивать базу известными комбинациями.


Поиск, конечно, быстрый, но это $O(\ln N)$. Поиск по индексу это $O(1)$.

Моя программа строит шестифигурные таблицы примерно за несколько часов, а это $2.6 \cdot 10^9$ различных позиций, и если каждую из них хранить строкой из $10$ байт, что мы уже получаем 26G без учёта индексов для быстрого доступа и служебной информации. А построение такой таблицы это не только $2.6 \cdot 10^9$ транзакций по вставке, но и большое количество чтений (например, 30 проходов). Не говоря о том, что при построении желательно хранить для каждой позиции список возможных ходов (при построении шестифигурных таблиц расход памяти был в районе 20G, при расчёте семифигурных в районе 400G RAM).

Если брать восьмифигурные, то четыре на четыре простые это примерно $400 \cdot 10^6$ позиций, дамки это $18 \cdot 10^9$ позиций.

Так что СУБД врял ли могут помочь тут хоть как-то из-за больших объёмов и низкой скорости.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 43 ]  На страницу Пред.  1, 2, 3

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group