Иван Мельников
11 августа 12:49.
129

Пр-сть шахматного движка прямо пропорциональна кол-ву физических ядер процессора? Если я заменю 4-ядерник на 8-ядерник, то кол-во оцениваемых позиций удвоится?

Ответить
Ответить
Комментировать
3
Подписаться
0
1 ответ
Поделиться

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

В общем, моя гипотеза, что если и улучшится, то максимум раза в полтора, а скорее почти не улучшится. Скорее, я бы обратил внимание на параметры, как сам тип процессора и размер, тип операционной памяти.

Антон Климовотвечает на ваши вопросы в своейПрямой линии
2

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

0
Ответить

Я не говорю, что нет распараллеливание, я говорю, что я не удивлюсь, если его нет, и на мой взгляд, это не самая оптимальная задача для распараллеливания.

Твои потоки не могут работать абсолютно независимо, иначе, как твой поток примет решение, останавливаться ему или нет, и не рассматриваем ли он позицию уже рассмотренную другим потоком. Грубо говоря, берем самый тупой пример - начальная позиция, 1-й процесс начинает ветку 1.е4, 2-й - ветку 1. a4. Пока твой 2-й процесс не получит информацию об оценках, полученных первым процессом, он не сможет отбросить ход 1.a4, и будет вынужден рассматривать эту бесперспективную ветвь. Соответственно данное сравнение нужно делать как-то на каждом спуске, иначе будет слишком много затратных вычислений. Подозреваю, что такая синхронизация занимает не меньше времени, чем этап извлечения Features и оценка позиции машинным обучением, поэтому мне и кажется, что потоки не дадут здесь выигрыша. 

К слову, я смотрел исходный код Стокфиш, не помню, чтоб они использовали параллельные методы

+2
Ответить

Хм. Ну если вы целенаправленно интересовались шахматными движками, то вам виднее.

Я напишу, почему я так предположил. Я не знаю, как конкретно устроен алгоритм, который оценивает позицию. Я считаю, что оценку бессмысленно делать на ранних узлах дерева. То есть, по моему представлению, движок должен сперва формировать массив потенциально хороших вариантов, которых будут тысячи, затем он будет оценивать все эти тысячи позиций по очереди - и в этот момент распараллеливание подойдёт идеально. Синхронизировать их не очень-то надо: писать в общую память не надо, читается всё по очереди, обновляется только коэффициент "выигрышности" (это либо одно число, либо пара-тройка чисел), который меняется не так уж часто - не думаю, что это будет заметно задерживать потоки. Какие-то вычисления не получится отсечь рано, да. Ну и что? 8 параллельных потоков всё равно (по моим представлениям) будут работать значительно быстрее, чем без параллелизации.

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

P. S. Я исходный код Стокфиша не смотрел, но я знаю, что его исходный код оптимизирован под многопроцессорные системы (поддерживается то ли до 16, то ли до 32 процессоров).

0
Ответить
Ещё 9 комментариев

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

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

0
Ответить

> не рассматриваем ли он позицию уже рассмотренную другим потоком

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

0
Ответить

> Как ты отберешь 1000 "потенциально хороших" без выполнения оценивания?

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

В общем, мы в любом случае имеем дело сразу с тысячами (или даже десятками или сотнями тысяч) вариантов.

После того, как анализ завершается, мы теперь знаем перспективные ("потенциально хорошие") ходы. Теперь для выбранных вариантов дерево нужно углубить на 2-3 хода - это новые тысячи вариантов.

И так далее. И так далее. Насколько позволяют настройки сложности и имеющееся шахматное время.

0
Ответить

>Я исхожу из  того, что само построение всех позиций

Если ты будешь запоминать все позиции, у тебя никакой памяти до более-менее приличной глубины расчета не хватит

0
Ответить

> Если ты будешь запоминать все позиции

Естественно, что не все возможные позиции. А все позиции в подготовленном дереве - то есть это изначально все позиции на 2-3 хода вперёд, плюс дальнейшие поддеревья на 2-3 хода вперёд, плюс дальнейшие поддеревья и т. д.

В общем, аргументация про "памяти не хватит" не выглядит убедительно. Если ты собираешься что-то считать и не хочешь, чтобы что-то считалось заново напрасно - тебе в любом случае нужно хранить информацию о сделанных рассчётах. Тут совершенно неважно, считаешь ты параллельно или последовательно. Если последовательно у тебя хватает памяти, то и параллельно хватит.

0
Ответить

>В общем, аргументация про "памяти не хватит" не выглядит убедительно. Если ты собираешься что-то считать и не хочешь, чтобы что-то считалось заново напрасно - тебе в любом случае нужно хранить информацию о сделанных рассчётах

Просто в моем понимании нет проблем с повторением позиций в последовательном случае. Если 1-2% посчитается повторно, это может и не так страшно. Гораздо обиднее было бы, если бы отдельному потоку выдали целую ветвь, которая посчиталась в другом потоке. Но в целом, видимо, все же лучше запоминать на пару ходов вперед

0
Ответить

>После того, как анализ завершается, мы теперь знаем перспективные ("потенциально хорошие") ходы. Теперь для выбранных вариантов дерево нужно углубить на 2-3 хода - это новые тысячи вариантов.

В таком концепте непонятно, как ты можешь гарантировать, что ты не получишь через 3 хода мат, если ты посмотрел только на 2-3 хода вместо 5-6. То есть в таком случае, либо основной поток должен все равно проверять все ветки ( слишком большая нагрузка на него будет ), либо отдельные потоки будут ходить по всем веткам вглубь и оценивать ( опять будет нужна синхронизация ) 

0
Ответить

Я не понимаю суть твоих контр-аргументов. Возможно, это потому, что ты лучше знаешь, как в действительности устроен шахматный движок.

Итак. Как я это понимаю.

Очевидно, что перебрать все варианты невозможно. Поэтому перед шахматным движком стоит 2 задачи.

1. Уметь оценивать любую позицию с точки зрения её "полезности". Для этого используется шахматная теория, которая подсчитывает для данной позиции ключевые параметры (вроде "материальная выгода/убыток", "позиционная выгода/убыток", "гибкость стратегии"), которые все в конечном счёте сводятся к одному числу, которое показывает, насколько данная позиция "желаема" (выигрышна).

2. Уметь быстро и эффективно перебирать все эти позиции, уделяя больше внимания перспективным ходам и поскорее отсекая неперспективные ходы.

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

Ты говоришь "а тогда будет мат через 3 хода".

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

Алгоритм должен уметь перебирать не все ходы подряд, а выбирать наиболее перспективные ветки деревьев, это очевидно. Если он не будет этого делать, он не сможет хорошо играть. То есть, более перспективные ветки будут просчитываться и на 10 ходов вперёд, в то время как ветки, которые не выглядят перспективными ни для тебя, ни для оппонента, будут просчитываться на 3-5 ходов. Я так понимаю, что ты тоже хорошо понимаешь, что движок дожен уметь делать нечто подобное.

Возвращаемся к клавным пунктам, которые должен уметь движок (я их перечислил вначале).

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

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

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

Я исхожу из того, что весь алгоритм из пункта 2, по идее, занимает ничтожную долю вычислительных ресурсов, по сравнению с алгоритмом для пункта 1.

Ты говоришь "проблема с параллельностью в том, что изначально у нас нет дерева и мы не хотим его перебирать целиком, мы хотим отсекать бесперспективные позиции как можно раньше". То есть, как я понимаю, в твоём изложении сперва мы дожны проанализировать =все= позиции на 1 ход вперёд, затем... Затем что? Мы должны что-то отсекать уже сейчас или нет?

Если да - то я задаю тебе тот же вопрос: как ты определишь, что не будет мата через 3 хода?

Если нет - то твой алгоритм аналогичен моему алгоритму. А именно: нам нет смысла тратить время на анализ позиции, если мы знаем, что мы в любом случае не можем отсечь никакие позиции на этом ходу. Поэтому на данном этапе мы просто собираем все позиции, которые мы хотим проанализировать (это будет 2-5 ходов вперёд, я не знаю, насколько сейчас глубоко просчитывают). =Затем= мы все эти позиции начинаем анализировать и начинаем отсекать бесперспективные ветки только сейчас. Какой алгоритм, какую логику при этом использовать - это другой вопрос. Но параллелиться оно, по моим представлениям, должно хорошо. Да, могут быть некоторые издержки, но это будет гораздо выгоднее, чем исполнять всё последовательно. Как часто синхронизировать - это нужно выяснять из практики, но уверен, что оверхед на синхронизацию будет небольшой.

Теперь на данном этапе мы просчитали небольшое количество ходов вперёд и имеем представление, какие ходы нам нравятся больше, а какие - меньше. Для более перспективных листьев мы повторяем всю эту процедуру - опять сперва достраиваем дерево на несколько ходов вперёд, собираем все позиции которые получились, и =затем= анализируем.

Снова повторю: потому что я не вижу возможности делать хоть сколько-нибудь эффективное отсечение на основе позиции для n+1 хода, чем уже известная нам n-ная позиция. Что бы мы там не на-анализировали - анализ n+1 будет не намного правдоподобнее, чем n-най.

Но даже если я не прав. Даже если шахматный движок действительно анализирует все позиции и отсекает прямо на каждом ходу - всё равно дерево ветвится очень быстро. Мы говорим всего лишь о 8 потоках - это очень мало с учётом того, что всего алгоритму предстоит проанализировать, как минимум, сотни тысяч или даже миллионы позиций и вычисления в рамках каждой из этих позиций =полностью= независят от чего-либо другого, то есть это 100%-ная параллелизация с оверхедом только на чтение-запись пары чисел в дерево.

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

Ты говоришь, что придётся ждать, пока закончится анализ листа, чтобы принять решение, нужно ли достраивать поддерево. Но зачем ждать? У нас ещё сотни листов без анализа. Можно даже хотя бы просто раскидать их поровну по потокам и сидеть ждать, когда всё посчитается.

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

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

Ну, в общем, по моему мнению, всё должно работать.

0
Ответить

Окей, соглашусь с большей частью. Распараллеливание по позициям действительно должно быть более эффективно, чем по веткам. Я не знаю деталей устройства разных движков, но моя мысль была в том, что нельзя после 2 ходов откидывать ветки, даже если оценка получается очень низкая. Даже 10 лет назад, когда я пользовался движками, лучшей программе было непростительно не заметить мат в 6-7 ходов. Соответственно нужно как-то эти ветки оставлять, и по ним тоже ходить, возможно по вероятностной модели. Возможно, конечно, что современные нейронные сети для шахмат могут по одному виду позиции предсказать тот же мат, и дать высокий score rate, но тут я не знаю. В принципе этот обход низкоперспективных ветвей тоже может делать основной поток, и собирать позиции, которые потом дочерними потоками обсчитываются как ты писал, но мне это кажется слишком затратным, возможно есть какая-то эвристика ( например, основной поток проверяет только шахи или делает какое-то сравнение с позициями из других веток, которые позволяют ему доказать, что если в ветки B нет мата, то и в ветке A мата не будет, и можно смотреть только ветвь B). Такие эвристики увеличивают время работы самого основного потока, и уменьшают эффективность распараллеливания. Но это только одно из предположений, на практике вещи могут работать совершенно по-другому, деталей, повторяюсь, я не знаю.

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

0
Ответить
Прокомментировать
Ответить