комбинаторный анализ партий

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



го - игра поколений,
спорт великих атлетов.
кто играет - тот гений.
я объелся котлетов.

Решена для доски 5х5 и меньших, если не ошибаюсь... Может быть и 7х7, но вот 9х9 - уже точно нет, иначе бы компьютеры смогли сносно играть хотя бы на такой доске, но пока "терминатор" не в силах справиться с такой задачей =о)



<По техническим вопросам форума и портала weiqi.ru можно обращаться ко мне td#weiqi#ru.>
Qui parcit nocentibus, innocentes punit - Кто щадит виновных, тот наказывает невинных.
Бортовой журнал: [dimdimka.weiqi.ru]

Исходя из тех математических функций, используемых для вычисления всевозможных комбинаций, для игр, то для игры ГО - такая задача для современного компьютера, будет составлять по времени решения около 150 000 лет, что вполне является нереальным.



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Если бы 150000 лет! Найти 150 тысяч компьютеров по всему миру - элементарно. За год они бы решили игру? Нет, там (к счастью) совсем другие порядки.

Я тут как-то оживлял университетские знания и заинтересовался тем, что же физически могут означать порядка цифры 10^100. А в го (19х19)порядка 10 в 750 вариантов.

Получилось, что если ПЛОТНО упаковать весь видимый объем Вселенной (есть такая величина в астрофизике) ПРОТОНАМИ, то их наберется 10 в 90 приблизительно штук.

Как это могут компьютерщики прокомментировать?

Поправьте, если я не прав, кому не лень подсчитать.

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



Отправка отредактированного (28/02/07 01:05)

Задача решается и, скорее всего, будет решена.

Я был на докладе Джона Тромпа из Голландии, который работает над этой проблемой уже много лет. В настоящее время задача точно решена для всех досок до 17х17, и приближенно - для 18x18 и 19x19

Для тех, кто любит точность, вот точное количество легальных го-позиций на доске 17x17:
19079388919628199204605726181850465220151058338147922243967269231944059187214767997105992341735209230667288462179090073659712583262087437

Для доски 19x19 они расчитали достаточно хорошее приближение:
2.081681994 * 10^170

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