Поставить мат рандомными ходами

[pptfhcs]

Гугль заявил что его программа освоила шахматы за 4 часа зная только как ходят фигуры и что надо поставить мат.
Даже имея две ладьи против короля делая рандомные ходы вероятность мата крайне низка. Раньше случится ничья по правилу 50 ходов или вражеский король съест ладьи. Ладно,пусть правило 50 ходов отменили.
Но никаких эвристик по их заявлению не вводилось. По началу только рандомные ходы, а оптимизация только по достижению мата.
Сколько ж это партий надо сыграть чтоб хоть раз случился мат?
Что-то кажется что если все компы на Земле будут играть, до мата они так и не доиграют.

[ozheredov]

pptfhcs

Можно два вопроса к вам? 1. Какова конфигурация самого мощного из ваших домашних компьютеров? 2. Программируете ли вы? Если да, то на каких языках ?

-- 21.12.2017, 19:25 --

Поверьте мне, это вопросы по теме

[Mihaylo]

Необязательно партию изучать, начиная со стартовой позиции.

[mihaild]

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

-- 21.12.2017, 20:06 --

Mihaylo в сообщении #1277348 писал(а):

Необязательно партию изучать, начиная со стартовой позиции.

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

[Mihaylo]

Трудно сказать, как поставлена задача, если до нас дошло лишь пару слов. Неужели машина 4 часа учится в том числе понимать, что фигуры можно не только двигать на свободное место, но и рубить ходами фигуры соперника? А остальные правила тоже приходится "осознавать" самостоятельно?

[grizzly]

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

[mihaild]

На всякий случай, статьи: ALphaGo Zero, AlphaZero (шахматы).
AlphaGo Zero просто выдавала распределение на позициях, куда ставить камень. AlphaZero выдает распределение на ходах (непонятно, учитываются ли запрещенные ходы в кодировании, или просто считаются ведущими к проигрышу). Плюс они обе выдают вероятность того, что они выиграют из данной позиции.

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

Например, мы предсказываем что из текущей позиции сделаем ход ладьей с вероятностью $x = \frac{2}{3}$, сделаем ход лошадью с вероятностью $y = \frac{1}{3}$, и что выиграем с вероятностью $z = \frac{3}{4}$. Перебором на несколько ходов вглубь мы присвоили ходу лошадью вероятность $a = \frac{4}{5}$, а ходу ладьей $b = \frac{1}{5}$. Как-то пошли, партию проиграли. В результате мы шагаем по градиенту в сторону уменьшения $(z - 0)^2 - x\log a - y\log b$ (формула 1 из статьи).

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

[pptfhcs]

ozheredov в сообщении #1277333 писал(а):

pptfhcs

Можно два вопроса к вам? 1. Какова конфигурация самого мощного из ваших домашних компьютеров? 2. Программируете ли вы? Если да, то на каких языках ?

-- 21.12.2017, 19:25 --

Поверьте мне, это вопросы по теме

Программирую. Просто писать шахматы для проверки своих предположений мне лень.
Если вероятность мата $10^{-100}$ то о каком обучении может идти речь независимо от мощности компьютера?

[Sender]

mihaild в сообщении #1277349 писал(а):

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

Из начальной позиции за 2 хода получается дурацкий мат, за 4 хода - детский мат, ну и далее по нарастающей и в разных вариациях.

[mihaild]

pptfhcs, а вы спросили у гугла, когда возникли сомнения? На stackoverflow есть код, считающий вероятность исходов при случайной игре, и получается что вероятность ничьи $84.4\%$. Так что выигрыши / проигрыши даже в самом начале будут случаться достаточно часто, что позволит начать играть минимально осмысленно. А дальше уже стандартная тренировка против всё более сильного оппонента.

[Pphantom]

atlakatl, ozheredov, пожалуйста, выясняйте личные отношения в ЛС. Безобразие удалено.

[urod]

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

Имея короля и двух ладей против короля, перебором с запоминанием позиций найти мат легко. Позиций-то не так уж много для компьютера.

Более того, вполне возможно, что программе оставили эндшпильный справочник, чтобы не плакала. Он ведь тоже основан на переборе.