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

D>>А если я решаю задачу нахождения оптимального хода не минимаксом, а другим способом ?
D>>Рендзю — игра тоже кажется NP, но найден выигрыш за начинающую сторону.

T>В математике Нет слово кажется

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

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

D>Нахождение лучшего хода в шахматах не является NP полной задачей, хотя это трудно строго доказать.

Это Не Возможно доказать

D>В качестве косвенного довода к этому утверждению является решение игры Рендзю.

D>(в Рендзю количество ходов в позиции больше чем шахматах, и значит она сложнее (правда только с формальной точки зрения))

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

Если нас читают математики на вас сейчас обрушитса шквал сообшении типа этого — "для начала прочитай учебник по дискретной математике", ну держитес

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

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

D>>Нахождение лучшего хода в шахматах не является NP полной задачей, хотя это трудно строго доказать.

T> Это Не Возможно доказать

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

T>Могу на палцах дать математическое доказательство что задача Нахождение лучшего хода в шахматах НП полная, но не буду судя по всему вы нечего не поймете.

T>Если нас читают математики на вас сейчас обрушитса шквал сообшении типа этого — "для начала прочитай учебник по дискретной математике", ну держитес

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

D>Давайте доказательство, если я его не пойму, то наверное найдутся люди, которые его смогут понять, им наверное тоже интересно.

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

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

T>Могу на палцах дать математическое доказательство что задача Нахождение лучшего хода в шахматах НП полная, но не буду судя по всему вы нечего не поймете.

Давайте сначала определимся с тем что же такое размер входа шахматной задачи и сколько всего наборов входных данных
Хинт: если задача с конечным множеством входных данных NP-полна, то P=NP

Здравствуйте, Иванков Дмитрий, Вы писали:

ИД>Здравствуйте, tzragravorox, Вы писали:

T>>Могу на палцах дать математическое доказательство что задача Нахождение лучшего хода в шахматах НП полная, но не буду судя по всему вы нечего не поймете.

ИД>Давайте сначала определимся с тем что же такое размер входа шахматной задачи и сколько всего наборов входных данных
ИД>Хинт: если задача с конечным множеством входных данных NP-полна, то P=NP

Постановка: есть алгоритм сопоставляющий любой позиции число, есть позиция в которой нужно выбрать ход, гарантированно приводящий к максимальной возможной оценки через заданное число ходов (т.е входные данные: глубина перебора). Размер дерева, которое нужно просмотреть для выполнения задачи растет с ростом глубины экспоненциально. (допустим правило 50 ходов не учитывается). Есть предположение, что начальная позиция выиграна или все варианты кончаются тем, что одна из сторон вынуждена форсировать ничью троекратным повторением позиции. В таком случае функции размера дерева, которое нужно просмотреть, чтобы сделать правильный ход с некоторой глубины станет константой, это и имелось в виду в начальном сообщении.

Это я, меня забанили.

D>Постановка: есть алгоритм сопоставляющий любой позиции число, есть позиция в которой нужно выбрать ход, гарантированно приводящий к максимальной возможной оценки через заданное число ходов (т.е входные данные: глубина перебора). Размер дерева, которое нужно просмотреть для выполнения задачи растет с ростом глубины экспоненциально. (допустим правило 50 ходов не учитывается). Есть предположение, что начальная позиция выиграна или все варианты кончаются тем, что одна из сторон вынуждена форсировать ничью троекратным повторением позиции. В таком случае функции размера дерева, которое нужно просмотреть, чтобы сделать правильный ход с некоторой глубины станет константой, это и имелось в виду в начальном сообщении.

А кто тебе сказал, что ход оцененный таким способом действительно лучши?

Здравствуйте, Аноним, Вы писали:

А>Это я, меня забанили.

D>>Постановка: есть алгоритм сопоставляющий любой позиции число, есть позиция в которой нужно выбрать ход, гарантированно приводящий к максимальной возможной оценки через заданное число ходов (т.е входные данные: глубина перебора). Размер дерева, которое нужно просмотреть для выполнения задачи растет с ростом глубины экспоненциально. (допустим правило 50 ходов не учитывается). Есть предположение, что начальная позиция выиграна или все варианты кончаются тем, что одна из сторон вынуждена форсировать ничью троекратным повторением позиции. В таком случае функции размера дерева, которое нужно просмотреть, чтобы сделать правильный ход с некоторой глубины станет константой, это и имелось в виду в начальном сообщении.

А> А кто тебе сказал, что ход оцененный таким способом действительно лучши?

Я говорил, что этот ход лучший ?

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

D>>>Постановка: есть алгоритм сопоставляющий любой позиции число, есть позиция в которой нужно выбрать ход, гарантированно приводящий к максимальной возможной оценки через заданное число ходов (т.е входные данные: глубина перебора). Размер дерева, которое нужно просмотреть для выполнения задачи растет с ростом глубины экспоненциально. (допустим правило 50 ходов не учитывается). Есть предположение, что начальная позиция выиграна или все варианты кончаются тем, что одна из сторон вынуждена форсировать ничью троекратным повторением позиции. В таком случае функции размера дерева, которое нужно просмотреть, чтобы сделать правильный ход с некоторой глубины станет константой, это и имелось в виду в начальном сообщении.

А>> А кто тебе сказал, что ход оцененный таким способом действительно лучши?

D>Я говорил, что этот ход лучший ?

Внымание-внымание. сейчас буду цитировать именно Ваши слова, можете убедитса в этом прочитав текст корня этой же темы.

dmchess — Нахождение лучшего хода в шахматах не является NP полной задачей, хотя это трудно строго доказать.
В качестве косвенного довода к этому утверждению является решение ...



Думаю в этом контексте не уместень ваш послдений вопрос, не так ли?

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

D>>>А если я решаю задачу нахождения оптимального хода не минимаксом, а другим способом ?
D>>>Рендзю — игра тоже кажется NP, но найден выигрыш за начинающую сторону.

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

Вы чего?!

В шахматах существует выигрышная стратегия! Нахождение очередного хода вообще имеет константную сложность, если оппонент играет оптимально :-)

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

Это я, tzragravorox просто меня забанили

RO>Вы чего?!

RO>В шахматах существует выигрышная стратегия ! Нахождение очередного хода вообще имеет константную сложность, если оппонент играет оптимально

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

Мне очень интерестно, как собыраютса обосновывать свой ответ авторы этих мессаг, если конечно собыраютса

P.S. Книжки нужно больше читать

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

F>Мне очень интерестно, как собыраютса обосновывать свой ответ авторы этих мессаг, если конечно собыраютса
F>P.S. Книжки нужно больше читать
Советую все же вам прочитать чуть подробнее теорию и чуть задуматься. У шахмат, как и остальные детерминированных игр (может с названием что то путаю, универ уже давно закончил) есть выигрышная стратегия, только проблема в том, что ее никто не знает (или во всяком случае никто про это не говорит ).

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

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

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

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

CVL>Советую все же вам прочитать чуть подробнее теорию и чуть задуматься. У шахмат, как и остальные детерминированных игр (может с названием что то путаю, универ уже давно закончил) есть выигрышная стратегия, только проблема в том, что ее никто не знает (или во всяком случае никто про это не говорит ).


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

По этому и називаетса NP полная.

Нет Вы безнадежни

Трурль wrote:

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

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

Во первых, научись писать на этом форуме, а во вторых научись читать что тебе пишут.

F>Нелзя тупо перебрать, не перебыреш за 1000 лет
Всего ходов примерно 10^40. За сколько перебрать можно я не знаю, но я и не говорю что это кто то сделал. Факт в том что стратегия существует, а не в том, что кто то ее знает.

F>Теореми и доказательства в студию.
Гугл в помощь. Ключевые слова: теория игр, игры с полной информацией. Для начала можешь почитать тута: http://journal.issep.rssi.ru/articles/pdf/9610_120.pdf

F>По этому и називаетса NP полная.
Я про это не говорил...

F>Нет Вы безнадежни
Ты студент первокурсник чтоли?

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

CVL>Во первых, научись писать на этом форуме, а во вторых научись читать что тебе пишут.

Спасибо за совет.

F>>Нелзя тупо перебрать, не перебыреш за 1000 лет
CVL>Всего ходов примерно 10^40.

После этого я отказываюсь вести диалог далше, только имейте в ввыду что всего ходов примерно 2^192>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>10^40

А 10^40 легко дасигаема современними компютерами.

F>А 10^40 легко дасигаема современними компютерами.
Товарищ 0000xF, он же tzragravorox, ты несешь просто несусветный бред. Может хватит людям голову морочить?

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

F>>А 10^40 легко дасигаема современними компютерами.
PG>Товарищ 0000xF, он же tzragravorox, ты несешь просто несусветный бред. Может хватит людям голову морочить?

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

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

F>А 10^40 легко дасигаема современними компютерами.
а если подумать? пусть операция построения дерева требует 3 такта. Итого получает на современном компе (3 ГГц) дерево размеров 10^9 за секунду. Пусть у нас будет кластер из миллиона таких компов. Итого он сможет за секунду 10^15 узлов посчитать. В году примерно 31*10^6 секунд. То есть за год супер кластер создаст дерево размером 3*10^22.
То есть наш кластер будет работать примерно 10^40/(3*10^22) = 3 * 10^(40-1-22) = 3*10^17 лет.
Вопрос, покажи пожалуйста мне современный компутер, который сумеет это посчитать за разумное время (хотя бы за век).

PS Слив не засчитан.
PPS Может откроешь название своей альмаматер, которую ты так усердно позоришь?

Здравствуйте, 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