Здравствуйте, CiViLiS, Вы писали:

Осталось понять, как все, что написали в этом топике, связано с классом NP.

Здравствуйте, ., Вы писали:

>> D>Нахождение лучшего хода в шахматах не является NP полной задачей, хотя
>> это трудно строго доказать.
>> Да чего там трудного. Количесво позиций конечно => сложность — O(1).
.>Интересно, а кто-нибудь уже пробовал считать это количество? Что получилось?

Расставить 32 шахматные фигуры можно таким количеством способов:

Если учитывать возможность взятия фигур, будет больше, если учитывать правила шахмат — меньше… главное, что много.

Roman Odaisky wrote:

> Если учитывать возможность взятия фигур, будет больше, если учитывать
> правила шахмат — меньше… главное, что много.
Нет, именно кол-во партий. Т.е. цепочек позиций от начала игры и до мата/пата. И с учётом того, что игра с повторённой
трижды позицией является ничьей. Интуитивно кажется, что их конечное число... но вот сколько?..

Здравствуйте, CiViLiS, Вы писали:

CVL>Здравствуйте, 0000xF, Вы писали:

CVL>>>Всего ходов примерно 10^40.
F>>После этого я отказываюсь вести диалог далше, только имейте в ввыду что всего ходов примерно 2^192>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>10^40
CVL>Ну я сам не считал -- где то увидел и запомнил, правда я имел ввиду не число возможных ходов, а число возможных комбинаций фигур на доске, то есть размер гипотетического графа.

Может туплю, но у меня верхняя граница возможных комбинаций фигур на доске — 10^19...

[ksh 8] % python
Python 2.4.3 (#2, Mar 21 2007, 11:28:15)
[GCC 3.2.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> def fact(n):
...     return reduce(lambda x, y: x*y, range(1, n))
>>> def comb(k, n):
...     return fact(n)/(fact(k)*fact(n-k))
>>> math.log10(sum(comb(i, 64) for i in range(2, 33)))
19.006024425156866

N>Может туплю, но у меня верхняя граница возможных комбинаций фигур на доске — 10^19...

Ступил, вот тут

Автор: Roman Odaisky
Дата: 15.06.07

правильно.

ИЗВИНЯЮСЬ.

ТОЛЬКО ЧТО УВИДЕЛЬ ЧТО НАПИСАЛЬ 10^40 ЛЕГКО ДОСИГАЕМА, АПЕЧАТОЧКА ВИШЛА !ДОЛЖЕН БЫЛЬ НАПИСАТЬ 2^40