Navigation » Immortal Chess - Chess without Frontiers! > Шахматный раздел > Шахматное программирование » Вопросы к шахматным программистам

Шахматное программирование Chess Programming. Вы уже написали свою шахматную программу? Или только-только приступили к её разработке? Добро пожаловать в данный раздел! Делимся советами, помогаем новичкам в шахматном программировании

Ответ
Опции темы
Непрочитано 15.12.2017, 02:49   #1681
sovaz1997
 
Регистрация: 08.11.2016
Возраст: 21
Сообщений: 578
Сказал(а) спасибо: 596
Поблагодарили 891 раз(а) в 362 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

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

После: нулевой ход, позволяющий быстро избавиться от неперспективных ветвей, форсированный перебор (чтобы оценивать позиции без взятий),
Потом... LMR, Futility pruning, razoring, PVS и ещё много всего, поднимающего силу игры с 1600 (примерно столько в обычной альфа-бета с форсированным вариантом и нулевым ходом) до 3000 и выше.

P. S. Современные движки очень хорошо отсекают варианты. Полный перебор использовался в движках 50-х, думаю, а после уже появилось альфа-бета отсечение.

Последний раз редактировалось sovaz1997; 15.12.2017 в 02:51.
sovaz1997 вне форума   Ответить с цитированием
Непрочитано 15.12.2017, 04:28   #1682
Guardian
 
Аватар для Guardian
 
Регистрация: 11.03.2010
Адрес: Russia
Сообщений: 603
Сказал(а) спасибо: 645
Поблагодарили 1,044 раз(а) в 401 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Скрытый текст:
Не знаю как именно работают алгоритмы, но может кто изменить движок для эксперимента?
Из заданной позиции определяются все возможные ходы, штук 20-30 в среднем. И каждая из вновь полученных позиций отправляется на обычный анализ уже со стороны противника. И сильнейший ход принимается тот, у которого оценка за соперника ниже. То есть глубина расчёта ply будет увеличиваться намного медленнее, но зато будут рассмотрены все варианты, в том числе с жертвами и тихими ходами.


Это совсем бесполезный подход, так как если перебирать абсолютно все имеющиеся позиции, без каких либо отсечений, то глубина перебора будет от силы полу-ходов 12-14 (depth), что означает, что такой движок будет пропускать элементарные комбинации, так как не будет видеть их окончания (допустим форсированный мат на 8-ом ходу после жертвы коня или позиция с лишним ферзем).

Если вы имеете ввиду что вместо одного движка могут анализировать сразу 20-30 движков, по обычной методике с отсечениями, но только со следующего полухода, то да, возможно, но так как движок 1 получите снижение производительности в те же 20-30 раз, так как придётся выполнять в 20 раз больше работы по обычной методике. Это не говорит о том что движки отсекают какие-то ветви сразу после первого полухода, но тем не менее.

Обычно движки начинают отсечения с 3-7 го полухода, при условии, что не заметен положительный эффект (например, позиция без 2-ух 3-ёх фигур, а шахов или атаки нет), такие ходы отсекаются почти сразу.

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

Последний раз редактировалось Guardian; 15.12.2017 в 13:31.
Guardian вне форума   Ответить с цитированием
Непрочитано 15.12.2017, 15:21   #1683
Remes_
 
Регистрация: 05.02.2011
Сообщений: 540
Сказал(а) спасибо: 52
Поблагодарили 1,183 раз(а) в 406 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Вот я и прошу именно комбинацию этого. Полный перебор первого хода белых (без отсечений, анализируются все ходы). И уже со второго хода использовать альфабета, форсирование, отсечения как обычно. Сейчас вот движок поработал минуту, написал что досчитал до глубины 20. А мне интереснее чтоб он досчитал например до 6, но по всем ходам.
Remes_ вне форума   Ответить с цитированием
Непрочитано 15.12.2017, 15:36   #1684
Guardian
 
Аватар для Guardian
 
Регистрация: 11.03.2010
Адрес: Russia
Сообщений: 603
Сказал(а) спасибо: 645
Поблагодарили 1,044 раз(а) в 401 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Цитата:
Вот я и прошу именно комбинацию этого. Полный перебор первого хода белых (без отсечений, анализируются все ходы). И уже со второго хода использовать альфабета, форсирование, отсечения как обычно. Сейчас вот движок поработал минуту, написал что досчитал до глубины 20. А мне интереснее чтоб он досчитал например до 6, но по всем ходам.
Всё-таки не совсем ясна цель вашей задумки - если вам действительно нужен движок, которые пересчитывает абсолютно все позиции из исходной без отсечений - то он будет играть в районе 1400 так как не сможет углубиться (возможно что такие даже существуют где-нибудь в архивах)

Если вы имеете ввиду полный перебор первой линии, а остальные ходы (линии) по стандарту, то эффекта не будет

Стандартный движок в основном и перебирает все позиции из всех возможных ходов до 5-7 полухода (ресурсы позволяют) - но дальше без каких-либо отсечений он сильно не заиграет. Движок не отсекает какие-либо позиции на первых ходах вообще, но методика отсечений позволяет перебирать далее наиболее перспективные линии с точки зрения альфа-бета и глубже и шире. Если вы пользуетесь движком, то вы должны замечать, что в большинстве случаев на первые, наиболее перспективные линии тратится значительно больше ресурсов по времени чем на остальные.

Последний раз редактировалось Guardian; 15.12.2017 в 18:32.
Guardian вне форума   Ответить с цитированием
Непрочитано 17.12.2017, 11:43   #1685
Sasha_
 
Регистрация: 30.09.2011
Возраст: 35
Сообщений: 28
Сказал(а) спасибо: 7
Поблагодарили 15 раз(а) в 14 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Ребята, подскажите плиз, как извлекать PV из альфа-бета? Желательно на паскале и желательно пошагово. Пять статей прочитал, но не понял, где собирать PV.
Sasha_ вне форума   Ответить с цитированием
Непрочитано 17.12.2017, 13:53   #1686
Guardian
 
Аватар для Guardian
 
Регистрация: 11.03.2010
Адрес: Russia
Сообщений: 603
Сказал(а) спасибо: 645
Поблагодарили 1,044 раз(а) в 401 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Есть много видео уроков от Bluefever Software

Там например, пересматривается с нуля как создавалась программа Vice на языке "С"
(95 видео уроков на английском - если хватит терпения - можно ознакомиться как в целом работают стандартные шахматные программы с уровнем 2100 - т.е. базовый пакет с нуля)

Что-такое Alpha-Beta там рассказывается здесь.

Скрытый текст:

вступление здесь
Скрытый текст:


Техническую часть можно глянуть в самом коде в search.h
так как open source
http://www.computerchess.org.uk/ccrl...ice_1_0_64-bit

Последний раз редактировалось Guardian; 17.12.2017 в 14:28.
Guardian вне форума   Ответить с цитированием
2 пользователя(ей) сказали cпасибо:
Slavik (30.12.2017), velmarin (09.03.2018)
Непрочитано 30.12.2017, 02:03   #1687
Remes_
 
Регистрация: 05.02.2011
Сообщений: 540
Сказал(а) спасибо: 52
Поблагодарили 1,183 раз(а) в 406 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Может кто-нибудь создать парсер для извлечения из базы игр с определенными позициями? Все программы позволяют фильтровать игры по индексу дебюта. Но мне охота глубже изучать какой нибудь вариант. Можно ли сделать так, чтоб я вводил fen строчку, программа проверяла первые ходы каждой игры, и если позиция после n хода совпадает с заданной, то партия записывается в файл. Тут проблема в том, что порядок ходов может отличаться друг от друга, поэтому придётся сравнивать не сами начальные ходы, а итоговую fen после этих ходов.
Remes_ вне форума   Ответить с цитированием
Непрочитано 30.12.2017, 03:31   #1688
Viktor
 
Аватар для Viktor
 
Регистрация: 15.03.2010
Адрес: Россия
Возраст: 63
Сообщений: 6,397
Сказал(а) спасибо: 40,714
Поблагодарили 29,158 раз(а) в 5,946 сообщениях
Страна:

Награды пользователя:
5000 posts Гуру форума 1000 reputation За заслуги Медаль 13 
Всего наград: 5

По умолчанию Re: Вопросы к шахматным программистам

Цитата:
Сообщение от Remes_ Посмотреть сообщение
Может кто-нибудь создать парсер для извлечения из базы игр с определенными позициями? Все программы позволяют фильтровать игры по индексу дебюта. Но мне охота глубже изучать какой нибудь вариант. Можно ли сделать так, чтоб я вводил fen строчку, программа проверяла первые ходы каждой игры, и если позиция после n хода совпадает с заданной, то партия записывается в файл. Тут проблема в том, что порядок ходов может отличаться друг от друга, поэтому придётся сравнивать не сами начальные ходы, а итоговую fen после этих ходов.
В программе ChessAssistant имеется поиск по позиции. Найденные партии можно записать в отдельную базу партий.
Viktor вне форума   Ответить с цитированием
2 пользователя(ей) сказали cпасибо:
Alex_Lk (09.01.2018), Slavik (30.12.2017)
Непрочитано 08.07.2018, 00:37   #1689
Discoverer
 
Регистрация: 07.04.2010
Сообщений: 2,188
Сказал(а) спасибо: 15,893
Поблагодарили 11,324 раз(а) в 1,868 сообщениях
Страна:

Награды пользователя:

По умолчанию Re: Вопросы к шахматным программистам

Мне нужно, чтобы Stockfish посылал интерфейсу не всю лучшую линию, а только первый ход. Может ли кто-нибудь показать, как изменить код, чтобы он делал так?
Discoverer вне форума   Ответить с цитированием
Ответ

Социальные закладки


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
шахматное программирование Vladimir50 Шахматное программирование 8 07.01.2014 19:09
Память VS Программа Overman Флейм 5 18.06.2010 19:53