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

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

Ответ
Опции темы
Непрочитано 15.12.2017, 02:49   #1681
sovaz1997
 
Регистрация: 08.11.2016
Возраст: 21
Сообщений: 580
Сказал(а) спасибо: 597
Поблагодарили 897 раз(а) в 364 сообщениях
Страна:
По умолчанию 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,184 раз(а) в 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,184 раз(а) в 406 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Может кто-нибудь создать парсер для извлечения из базы игр с определенными позициями? Все программы позволяют фильтровать игры по индексу дебюта. Но мне охота глубже изучать какой нибудь вариант. Можно ли сделать так, чтоб я вводил fen строчку, программа проверяла первые ходы каждой игры, и если позиция после n хода совпадает с заданной, то партия записывается в файл. Тут проблема в том, что порядок ходов может отличаться друг от друга, поэтому придётся сравнивать не сами начальные ходы, а итоговую fen после этих ходов.
Remes_ вне форума   Ответить с цитированием
Непрочитано 30.12.2017, 03:31   #1688
Viktor
 
Аватар для Viktor
 
Регистрация: 15.03.2010
Адрес: Россия
Возраст: 63
Сообщений: 6,397
Сказал(а) спасибо: 40,714
Поблагодарили 29,178 раз(а) в 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,895
Поблагодарили 11,326 раз(а) в 1,868 сообщениях
Страна:

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

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

Мне нужно, чтобы Stockfish посылал интерфейсу не всю лучшую линию, а только первый ход. Может ли кто-нибудь показать, как изменить код, чтобы он делал так?
Discoverer вне форума   Ответить с цитированием
Непрочитано 26.07.2018, 13:51   #1690
chessking8
 
Регистрация: 31.01.2018
Сообщений: 20
Сказал(а) спасибо: 4
Поблагодарили 17 раз(а) в 8 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

видно нет тут программистов, ладно..
Discoverer там сложно, uci это протокол стандартный, он передаёт gui, что писать в вывод, наверное нужно обвеску свою писать, перегружать операторы класса, я больше ассемблерщик и c-шник, с классами не работал..посмотрел 20 минут код и понял, что мне это неинтересно просто так, sorry может когда плотнее разберусь с кодом, то помогу, но пока, извините..

Последний раз редактировалось chessking8; 26.07.2018 в 17:31.
chessking8 вне форума   Ответить с цитированием
2 пользователя(ей) сказали cпасибо:
Chess762 (27.07.2018), Discoverer (27.07.2018)
Непрочитано 28.07.2018, 18:41   #1691
chessking8
 
Регистрация: 31.01.2018
Сообщений: 20
Сказал(а) спасибо: 4
Поблагодарили 17 раз(а) в 8 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Discoverer
нашел я место в коде,где нужно изменить вывод для одного хода..файл search.cpp функция string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) возвращает строку в конце которой будет pv e2e4 e7e5 и так целая линия ходов, нужно её проверить на наличие второго вхождения pv(первое multipv) и сохранить следующий ход(от 4 до 6 или 7 символов), а потом всё остальное удалить и передать дальше на выход функции, это банальная работа со строками, но выносящая мозги, я сделал такой костыль
Код:
  char ssnull[10000];
  string sspv;
  int pvinsertion;
string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) {

  std::stringstream ss;
  int elapsed = Time.elapsed() + 1;
  const RootMoves& rootMoves = pos.this_thread()->rootMoves;
  size_t PVIdx = pos.this_thread()->PVIdx;
  size_t multiPV = std::min((size_t)Options["MultiPV"], rootMoves.size());
  uint64_t nodesSearched = Threads.nodes_searched();
  uint64_t tbHits = Threads.tb_hits() + (TB::RootInTB ? rootMoves.size() : 0);

  for (size_t i = 0; i < multiPV; ++i)
  {
      bool updated = (i <= PVIdx && rootMoves[i].score != -VALUE_INFINITE);

      if (depth == ONE_PLY && !updated)
          continue;

      Depth d = updated ? depth : depth - ONE_PLY;
      Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore;

      bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY;
      v = tb ? TB::Score : v;

      if (ss.rdbuf()->in_avail()) // Not at first line
          ss << "\n";

      ss << "info"
         << " depth "    << d / ONE_PLY
         << " seldepth " << rootMoves[i].selDepth
         << " multipv "  << i + 1
         << " score "    << UCI::value(v);

      if (!tb && i == PVIdx)
          ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : "");

      ss << " nodes "    << nodesSearched
         << " nps "      << nodesSearched * 1000 / elapsed;

      if (elapsed > 1000) // Earlier makes little sense
          ss << " hashfull " << TT.hashfull();

      ss << " tbhits "   << tbHits
         << " time "     << elapsed
         << " pv";

      for (Move m : rootMoves[i].pv)
          ss << " " << UCI::move(m, pos.is_chess960());
  }
  pvinsertion = 0;
  pvinsertion=ss.str().find("pv");
  if (pvinsertion != 0) {
	  pvinsertion += 90;

	  for (int j = 0;j < 10000;j++) ssnull[j] = 0;
	  ss.str().copy(ssnull, pvinsertion);
	  ssnull[pvinsertion] = '\n';
	  sspv.assign(ssnull);
	  return sspv;
  }
  else return ss.str();
}
в фрице 13 он отлично обрезает вывод до 1-3 ходов, там осталось самая малость, мне тупо неинтересно доделывать

Последний раз редактировалось chessking8; 28.07.2018 в 21:38.
chessking8 вне форума   Ответить с цитированием
2 пользователя(ей) сказали cпасибо:
Chess762 (30.07.2018), Discoverer (10.08.2018)
Непрочитано 09.08.2018, 04:32   #1692
chessking8
 
Регистрация: 31.01.2018
Сообщений: 20
Сказал(а) спасибо: 4
Поблагодарили 17 раз(а) в 8 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Discoverer
простите, я последний раз программировал много на ассемблере, работа со строками на современном c++ слишком мудрена для меня, задачу вашу почти решил, осталось найти грамотного программиста для работы со строками и попросить его закончить под ваше тз, я же умываю руки, мне не интересны простые повседневные рутинные задачи, я лучше картофана начищу и поджарю

Последний раз редактировалось chessking8; 09.08.2018 в 11:28.
chessking8 вне форума   Ответить с цитированием
Непрочитано 13.08.2018, 23:02   #1693
Rimidalv
 
Регистрация: 28.04.2010
Сообщений: 50
Сказал(а) спасибо: 13
Поблагодарили 53 раз(а) в 35 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

Το Discoverer
Попробуйте изменить немного это место:
Код:
for (Move m : rootMoves[i].pv) ss << " " << UCI::move(m, pos.is_chess960());
в методе string UCI::pv(....
Код:
for (Move m : rootMoves[i].pv)  {
    ss << " " << UCI::move(m, pos.is_chess960());
    break; // сразу выскочит из цикла после первого хода
}

Последний раз редактировалось Rimidalv; 13.08.2018 в 23:08.
Rimidalv вне форума   Ответить с цитированием
Пользователь сказал cпасибо:
chessking8 (14.08.2018)
Непрочитано 14.08.2018, 09:33   #1694
chessking8
 
Регистрация: 31.01.2018
Сообщений: 20
Сказал(а) спасибо: 4
Поблагодарили 17 раз(а) в 8 сообщениях
Страна:
По умолчанию Re: Вопросы к шахматным программистам

to Rimidalv
и ваше работает..разные подходы, разные решения для оценки наших кунг-фу нужно что-то типа http://www.hugi.scene.org/compo/compoold.htm , я там учавствовал, но весомых результатов не добился но в приниципе незаменимых людей нет, всему можно научиться

Последний раз редактировалось chessking8; 14.08.2018 в 23:45.
chessking8 вне форума   Ответить с цитированием
Ответ

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


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

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

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

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

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