Рендомные шахматы

[Александрович]

Александрович в сообщении #730657 писал(а):

Самая большая вероятность, почти 100%, для случая, когда король вынужден будет съесть защищённого слона.

1...; 2. Кр:а7.

[venco]

Случайные ходы можно выбирать из разрешённых.

-- Пт май 31, 2013 09:27:24 --

В принципе задача решабельна - количество состояний, с учётом симметрий, около $2^{15}$. С такой матрицей переходов вполне возможно оперировать. Возведение в квадрат, по моим прикидкам, займёт порядка часа на современных процессорах. Вроде бы, возвести матрицу надо где-то в степень $10^9$, на худой конец - $10^{12}$. Несколько суток рассчётов.

[Александрович]

venco в сообщении #730814 писал(а):

Несколько суток рассчётов.

Это для получения одного значения. А нужно среднее найти. Случайные блуждание короля могут длиться бесконечно. Боюсь что жизни индивида не хватит.

[venco]

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

[Александрович]

venco в сообщении #731138 писал(а):

Одно значение (одну партию?), по-моему, можно просчитать за доли секунды.

Основное время (99,9... %) уйдет на отсеивание невозможных ходов.

[Alexandre Lois]

Alexandre Lois в сообщении #730636 писал(а):

mustitz в сообщении #729939 писал(а):

Да, не люблю композицию и всякие ретроанализы.

Да, можно на h8 съесть слона при белом короле на f6. Но вопрос с патом остается актуальным. Например, с вероятностью 99% процентов будет пат. С вероятностью 1% будет съеден слон. Считать математическое ожидание только для одного этого одно процента???

я сразу не сообразил. задача оказалась гораздо интереснее, чем я думал. Дело в том, что речь идёт не о 99 процентах, а о бесконечности. Говоря другими словами. 100 % что будет дан пат, а мата не будет. То есть ответ задачи- что партия кончится патом, а не матом. Вот это номер!!!

я имел ввиду не мат , а съедение слона.

-- 02.06.2013, 07:38 --

Александрович в сообщении #730803 писал(а):

Александрович в сообщении #730657 писал(а):

Самая большая вероятность, почти 100%, для случая, когда король вынужден будет съесть защищённого слона.

1...; 2. Кр:а7.

что это ? Что король бъёт?

-- 02.06.2013, 07:41 --

venco в сообщении #730814 писал(а):

Случайные ходы можно выбирать из разрешённых.

-- Пт май 31, 2013 09:27:24 --

В принципе задача решабельна - количество состояний, с учётом симметрий, около $2^{15}$. С такой матрицей переходов вполне возможно оперировать. Возведение в квадрат, по моим прикидкам, займёт порядка часа на современных процессорах. Вроде бы, возвести матрицу надо где-то в степень $10^9$, на худой конец - $10^{12}$. Несколько суток рассчётов.

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

[DVN]

Alexandre Lois в сообщении #729848 писал(а):

Я так понимаю, что порядок где то 10 в 50 степени, а может и в сотой. Можно хоть примерно это оценить?
Я в этом плохо разбираюсь, можно ли придумать математическую формулу, которая сможет оценить порядок степени?

Тупо посчитайте вероятность самых коротких партий в 7 ходов, заканчивающихся взятием слона. Их будет несколько из-за вариантов в маршрутах королей и выбором времени для хода слоном. Вероятность каждой партии считается легко: прикаждом ходе белых у них не более восьми альтернатив, у черных не более четырех. Вероятность этих коротких партий практически и будет равна искомой вероятностью, остальным можно пренебречь. Примерно это будет 2 в 30 степени, а точно считайте сами, если охота.

[Александрович]

В случае пата можно откатить на ход назад.

[Alexandre Lois]

DVN в сообщении #731487 писал(а):

Alexandre Lois в сообщении #729848 писал(а):

Я так понимаю, что порядок где то 10 в 50 степени, а может и в сотой. Можно хоть примерно это оценить?
Я в этом плохо разбираюсь, можно ли придумать математическую формулу, которая сможет оценить порядок степени?

Тупо посчитайте вероятность самых коротких партий в 7 ходов, заканчивающихся взятием слона. Их будет несколько из-за вариантов в маршрутах королей и выбором времени для хода слоном. Вероятность каждой партии считается легко: прикаждом ходе белых у них не более восьми альтернатив, у черных не более четырех. Вероятность этих коротких партий практически и будет равна искомой вероятностью, остальным можно пренебречь. Примерно это будет 2 в 30 степени, а точно считайте сами, если охота.

1073741824

-- 02.06.2013, 17:29 --

Александрович в сообщении #731533 писал(а):

В случае пата можно откатить на ход назад.

это не серьёзно

-- 02.06.2013, 17:30 --

Новая задача

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

[DVN]

Прошу прощения, я тут дал маху с предыдущей задачей. Тема скатилась к обсуждению вероятности взятия слона и пата. А вопрос стоял о среднем количестве ходов до взятия.
Я прикинул вероятность взятия слона $2^{-30}$ исходя из того, что основную долю в вероятность внесут короткие партии, а для более длиных вероятность будет уменьшатся гораздо быстрее, чем расти число партий. (Это чисто интуитивно, может тут меня интуиция подвела.)
С вероятностью пата аналогичная ситуация. Получается, что сумма вероятности взятия слона и пата много меньше единицы, а остальная вероятность приходится на то, что партия никогда не кончится.
Это если интуиция меня не подводит.
В связи с этим меня интересует подход venco. Можно подробнее, о каких состояниях и о какой матрице идет речь?

[Alexandre Lois]

DVN в сообщении #731997 писал(а):

Прошу прощения, я тут дал маху с предыдущей задачей. Тема скатилась к обсуждению вероятности взятия слона и пата. А вопрос стоял о среднем количестве ходов до взятия.
Я прикинул вероятность взятия слона $2^{-30}$ исходя из того, что основную долю в вероятность внесут короткие партии, а для более длиных вероятность будет уменьшатся гораздо быстрее, чем расти число партий. (Это чисто интуитивно, может тут меня интуиция подвела.)
С вероятностью пата аналогичная ситуация. Получается, что сумма вероятности взятия слона и пата много меньше единицы, а остальная вероятность приходится на то, что партия никогда не кончится.
Это если интуиция меня не подводит.
В связи с этим меня интересует подход venco. Можно подробнее, о каких состояниях и о какой матрице идет речь?

С моей точки зрения взятия не может быть. А будет гарантировано пат. Другие варианты типа- бесконечное количество ходов из сферы фантастики, без всякой реальности.

[venco]

DVN в сообщении #731997 писал(а):

Можно подробнее, о каких состояниях и о какой матрице идет речь?

В игре ограниченное число позиций, их количество легко оценить, да и точно посчитать не очень сложно - около полумиллиона, а если объединить эквивалентные симметричные позиции, то около $2^{16}$ (тут я сначала ошибся в 2 раза). Из каждой позиции с некоторой вероятностью игра переходит в некоторое количество других позиций, а также в два конечных состояния - пат и взятие слона. Можно построить матрицу переходов состояний, $2^{16}\times 2^{16}$ по 8 байт, полный размер в памяти - 8 GB. Теперь вектор вероятностей разных позиций на k-том ходу можно посчитать, умножив вектор начальных вероятностей (одна единица, остальные нули) на матрицу в k-той степени. В пределе при $k\to\infty$ получим вероятности конечных состояний. Предел можно получить многократным возведением матрицы в квадрат. (На самом деле, вроде бы, достаточно определить собственный вектор матрицы с максимальным собственным значением, но тут я не уверен, надо почитать умные книжки).
Среднее время игры должно быть порядка количества состояний, т.к. после достаточно большого количества ходов все не-конечные состояния будут более-менее равновероятны, т.е. с некоторой вероятностью $p_f\approx {1\over N_{states}}$ игра будет переходить в одно из конечных состояний, и среднее время партии будет близко к $1\over p_f$.

[deep blue]

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

[Alexandre Lois]

venco в сообщении #732113 писал(а):

Можно построить матрицу переходов состояний, $2^{16}\times 2^{16}$ по 8 байт, полный размер в памяти - 8 GB

есть к этому какое-то отношение ?
http://dic.academic.ru/dic.nsf/ruwiki/1 ... 0.B5.D0.BC

[venco]

Да.