Го и шахматы

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

1. Шахматы. Оценка сверху.
Предположения: на доске всегда максимальное число фигур. Ни одна фигура не мешает другой сделать ход. Края доски тоже не мешают. Число возможных ходов пешки не 4, а 28 (пешка может стать ферзем). Число ходов в партии 50.
Максимально возможное число вариантов во время хода, складывается из суммы возможных вариантов ходов каждой из фигур. Запрещенные (например, под шах) ходы не учитываются.
Король 1*8
Ферзь 1*28
Ладья 2*14
Слон 2*14
Конь 2*8
Пешка 8*28
Итого 332**50, или 2,5Е+125

2. Го. Оценка снизу.
Предположения: Число ходов в партии 250. В начале партии на доске 361 вариант ходов, к концу игры - 111. Игра на месте съеденных камней не рассматривается.
Симметрия доски Го: Поворотная (на 90, 180, 270) снимается первым ходом (при первом ходе в тенген - вторым ходом), и равна 1/4. Заркальная симметрия "право-лево" ("верх - низ"= "право-лево"*180, то же с диагональными поворотами) соответственно 1/2 , итого, симметрия Го добавляет коэффициент 1/8.
Кроме того, не учтен эффект запрещенности самоубийственных ходов, так как это алгоритмически - очень сложно, а влияние на число вариантов невелико и явно не выходит за пределы точности проводимой оценки.
Итого 1/8 * 361!/111!, или 1/8 * 1,4Е+768/1,7Е+180, или 1Е+587

Итого, вариантов в Го больше чем в шахматах в 10**462 раз.
Меня впечатлило.



Редактировано 1 раз(а). Последний раз 13/07/2005 18:42 пользователем waykim.

нет учета симметричных позиций и позиций, получаемых поворотом доски на угол кратный 90 град

Дамиру: это слёзы по сравнению с основной частью.

Ну да, скинется один порядок из 462.

Damir Написал:
-------------------------------------------------------
> нет учета симметричных позиций и позиций,
> получаемых поворотом доски на угол кратный 90
> град
>
>
Точно. Симметрия доски Го существует, Поворотная (на 90, 180, 270) снимается первым ходом (при первом ходе в тенген - вторым ходом), и равна 1/4. Заркальная симметрия (право-лево, верх - низ) соответственно 1/2 и 1/2, итого, в 16 раз ошибся.

Т.е. число вариантов больше "всего" в 10**461 раз.

Это меньше, но общее впечатление осталось

Где-то я слышал, что из всех возможных расстановок камней на доске 13х13 около 10% соответствуют правилам го. Всего один порядок отбрасывается.
Мелкие брызги.

На доске Го 8 преобразований (симметрия+повороты).
Так что это меньше одного порядка.

Kaban Написал:
-------------------------------------------------------
> Где-то я слышал, что из всех возможных расстановок
> камней на доске 13х13 около 10% соответствуют
> правилам го. Всего один порядок отбрасывается.
> Мелкие брызги.


Спасибо о напоминании о "запрещенных" ходах, вылетело из головы напрочь.

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

Для коннектности можно просто написать, что разница в числе вариантов более, чем 10**400.

waykim Написал:
-------------------------------------------------------
> >
> Точно. Симметрия доски Го существует, Поворотная
> (на 90, 180, 270) снимается первым ходом (при
> первом ходе в тенген - вторым ходом), и равна 1/4.
> Заркальная симметрия (право-лево, верх - низ)
> соответственно 1/2 и 1/2, итого, в 16 раз ошибся.

Да ((
Совсем математику подзабыл...
Ошибся, на самом деле не в 16, а всего в 8 раз, так как (право-лево) = (верх - низ) * 180, если опять ничего не путаю ))

Да, оценка сильная...
Вот поэто-му у меня и вызывает сомнение разные оценки Го-Бога, в частности силы его игры.