Съедание коня

[Cash]

Здесь, конечно же, ненулевая вероятность бесконечного значения. Хотя бы потому, что когда черный король имеет возможность съесть коня, то у него еще как минимум пара вариантов уклониться есть.
А вот если бы черный король двигался, соблюдая некоторые правила, например, всегда навстречу коню (минимизируя расстояние до коня), то возможно у задачи и был бы некоторый смысл.

[provincialka]

Ну, тогда всю задачу надо снимать.

[gris]

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

[Cash]

Угу, к тому же есть также правило пятидесяти ходов. И всё было бы хорошо, если спрашивали бы матожидание длины "партии".
И ещё. Вариантов исхода только два - конь короля скушать не может. По правилам, король не может подставиться под битое поле.

[gris]

Ну да. Впрочем, я это даже оговорил словом "допустимых" . И пусть нет правил, ограничивающих время игры, кроме съедания конём короля.
Итак, есть конечная доска. Правилами или ещё как мы определяем варианты расположения трёх фигур (с учётом очерёдности хода). Из них варианты с нахождением коня и короля в одной клетке назовём терминальными. Всего вариантов конечное число. Ход это просто переход от одного варианта к другому. Вероятности переходов строго определены. Наша цель найти вероятность того, что переход из некоторой начальной позиции в любую терминальную осуществится за $n$ шагов, а потом просто просуммировать ряд.
И Вы хотите сказать, что существуют начальные позиции, для которых ряд не сходится к единице? То есть существует положительная вероятность бесконечной игры?
Я чего-то не могу этого представить.
Задача же эквивалентна по сути простейшему одномерному блужданию. Вправо-влево по половинке. Начинаем в нуле. И существует положительная вероятность того, что блуждей не покинет конечный интервал? Не помню
Или я ошибаюсь?
Лучше так: вправо-влево по четвертушке, на месте половинка. Вероятность, что рано или поздно попадёт в конкретную точку не равна 1?
(+++ Учитывая следующее сообщение, мне следовало бы написать в любой из концов конкретного отрезка, содержащего начальную точку).

[Cash]

gris в сообщении #815055 писал(а):

Задача же эквивалентна по сути простейшему одномерному блужданию. Вправо-влево по половинке. Начинаем в нуле

Если представлять одномерным блужданием, то примерно так. Начало в нуле. Длина шага -1. Вправо - вероятность $\frac15$, влево, соответственно $\frac45$. За сколько ходов мы достигнем $8$?

-- Чт янв 16, 2014 10:46:13 --

Пусть даже дальше $-8$ мы не можем уйти, то всё равно - вероятность случайно "скушать" слишком низка. Без минимизации черным королём расстояния до коня задача бессмысленна.

[gris]

Ага. То есть и там точно так же: У короля кроме обеда есть ещё от двух до семи равновероятных варианта продолжить прогулку. То есть в любой позиции вероятность закончить игру в несколько раз меньше вероятности её продолжить. Вот немного стало доходить

Но тем не менее. Если в предложенной Вами задаче в положении $- 8$ вероятность "вправо" равна 1, то всё равно вероятность достижения $+8$ за конечное число ходов меньше 1? Я чего-то запутался

Кстати, почему $-8$, но $, хотя $

[math]$-8$[/math], но [math]$"-8"$[/math], хотя [math]$"+8"$[/math]

[Cash]

Именно. Можно посмотреть также вариант с таким правилом: если король может побить коня - он его бьёт. Это уже поинтереснее, но навскидку - всё равно недостаточно. Хотя можно и посчитать.

-- Чт янв 16, 2014 11:16:14 --

А вообще, все эти рассуждения на глазок весьма обманчивы. Возможно, что я сильно ошибаюсь и матожидание конечно?

[Лукомор]

Cash в сообщении #815050 писал(а):

Угу, к тому же есть также правило пятидесяти ходов.

Согласно правил ФИДЕ:

Цитата:

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

А вот правило трехкратного повторения позиции действительно накладывпает ограничения на максимальную длину партии:

gris в сообщении #815047 писал(а):

И есть одно важное правило: при трёхкратном повторении позиции наступает ничья.

Впрочем, опять же по правилам ФИДЕ, из исходной позиции не будет сделано вообще ни одного хода, поскольку будет зафиксирована ничейная позиция, и игра должна быть остановлена.

Цитата:

Ничья фиксируется в следующих случаях:...
Ни у одной из сторон нет минимально необходимого для мата количества фигур (например, на доске остались только короли или кроме них имеется лишь одна лёгкая фигура).

[gris]

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

А вот с точки формального следования правилам Лукомор поставил жирную точку.

[Cash]

Да gris, похоже правы были Вы, а я ошибался. 30-ю ходами там конечно не пахнет, но похоже, что оно конечно.

[provincialka]

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

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

Ну, вообще-то у программ не бывает проблем. Проблемы бывают у программистов.

[Лукомор]

gris в сообщении #815073 писал(а):

Мне кажется, что дело в том, что число позиций (с учётом очерёдности хода) конечно.

С учетом того, что не все позиции допустимы с точки зрения шахматных правил, число возможных позиций для трех фигур будет меньше некоторого не очень большого числа:
$N<C_{64}^3<64\cdot63\cdot62<249984$

[gris]

Лукомор, надо бы на $2$ умножить. В матрице переходов позиции с одинаковым расположением фигур отличаются очерёдностью хода. А то, что короли не могут рядом стоять не даёт уполовинивания Вашего произведения.
Но мне казалось не конечность числа позиций, а то, что дело в конечности.

[Лукомор]

gris в сообщении #815109 писал(а):

Лукомор, надо бы на $2$ умножить

Каюсь, забыл!

-- Чт янв 16, 2014 11:15:20 --

gris в сообщении #815109 писал(а):

Но мне казалось не конечность числа позиций, а то, что дело в конечности.

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