Головоломка

 
1 2 3 4
US Сергей-4030 #09.02.2008 01:43  @GOGI#09.02.2008 00:22
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
СергейGOGI> Так ты и не понял, о чем я спорил :-) Я не о том, что есть задачи, на которых человек побьет компьютер (хотя и таких полно осталось даже после того как шахматы посчитали), а про то, что человек эти задачи считает не так как компьютер, поэтому оценивать сложность задачи для человека по тому, сколько машиновремени для этого понадобится нельзя.

Понял, понял. Еще раз, Андрей - есть задачи, для которых ДОКАЗАНО отсутствие любого - алгоритмизируемого ли, неалгоритмизируемого ли решения, лучшего (более эффективного) чем такой-то. Если человек будет считать "не так", как компьютер, то он будет считать еще дольше, чем "по-компьютерному". :) Если и нельзя оценивать сложность таких задач для человека, то только в теме "еще хуже".
 
DE dercoolman #07.07.2008 23:37
+
-
edit
 

dercoolman

опытный

Читал гдето про шахматы и бруте форце, так вот это не возможно в принципе ни один комп ни все они в месте ни сегодня ни в далёком будущем не способны просчитать все ходы, даже если собрать все атомы во вселенной и на каждый записывать один ход их не хватит. Учёные даже примерно не знают сколько возможных ходов в шахматах. имхо
 
+
-
edit
 

john5r

аксакал
★★
Дерево позиций – дерево перебора.

Несмотря на то, что мы не можем точно описать дерево до уровня, который включает большинство человеческих партий (160 уровень – 80 ходов), в виду его колоссальных размеров, все же, пользуясь простыми логическими методами, мы можем установить некоторые присущие дереву свойства:

Свойство № 1 - в дереве встречаются одинаковые позиции. Действительно, уже на третьем уровне среди 8902 позиций встречаются несколько начальных позиций. (Одна из начальных позиций может возникнуть на третьем уровне дерева после следующих ходов 1. ¤f3 ¤f6. 2. ¤g1 ¤g8). Аналогично рассуждая, легко прийти к выводу, что в дереве встречаются и различные множества одинаковых «неначальных» позиций.

Свойство № 2 – дерево бесконечно – это прямо вытекает из Свойства №1 и принятого нами условия, что мы игнорируем шахматные правила «троекратного повторения позиции» и «пятидесяти ходов». Действительно, из любой начальной позиции третьего уровня можно построить точно такое же дерево, как из начальной позиции первого уровня. Таким образом, на уровнях 0, 3, 7, 11, 15 и далее до бесконечности встречаются начальные позиции.

Свойство № 3 – В дереве существуют тупиковые ветви. Действительно, из тех позиций дерева, где зафиксирован мат или пат, ветви не растут. (Пользуясь принятой терминологией, можно сказать, что подвижность в таких позициях равна нулю).


I don't hit women! I would never hit a woman, Chloe! I'd hit a woman who was trying to hit me with a bottle. That's different. That's self-defense, isn't it? Or a woman who could do karate. I'd never hit a woman generally, Chloe. Don't think that. (с) In Bruges  
US Сергей-4030 #08.07.2008 00:45  @дровосек3d#07.07.2008 23:37
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
 
Это сообщение редактировалось 08.07.2008 в 00:50
US Сергей-4030 #08.07.2008 00:47  @john5r#07.07.2008 23:50
+
-
edit
 
US Сергей-4030 #08.07.2008 00:52  @john5r#07.07.2008 23:50
+
-
edit
 
LT Bredonosec #08.07.2008 01:13
+
-
edit
 
US Сергей-4030 #08.07.2008 01:44  @Bredonosec#08.07.2008 01:13
+
-
edit
 
LT Bredonosec #08.07.2008 02:05
+
-
edit
 
US Mishka #08.07.2008 04:46  @Сергей-4030#08.07.2008 00:47
+
-
edit
 
+
-
edit
 

Mishka

модератор
★★☆
Ну, оценка сверху очень проста. Количество позиций 32 фигур на 64 клетках не превосходит плюс 31 фигуры на 64 клетках и т.д. Понятно, что последние должны остаться два короля. Понятно, что пешки взаимозаменяемы и там не , а , но мы оцениваем сверху. Вот сумма таких комбинаций и будет оценка сверху. Это будут вершины графа. А ребрами (граф может быть даже не направленный) будут ходы — если из этой позиции можно перейти в другую по законам шахмат. Очевидно, что один ход — одно ребро. Очевидно, что число рёбер тоже конечно и не превосходит число вершин. Всё, граф конечный. А вот ходить по нему можно бесконечно. Правило трёх повторений означает, что одну и ту же вершину мы посетили 3 раза.
 
US Сергей-4030 #08.07.2008 06:00  @Mishka#08.07.2008 04:57
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Mishka> А вот ходить по нему можно бесконечно.

Exactly. При этом решение задачи будет вполне конечно.
 
DE dercoolman #08.07.2008 17:55  @Mishka#08.07.2008 04:57
+
-
edit
 

dercoolman

опытный

Mishka> Ну, оценка сверху очень проста.

Ну так сколько возможных ходов?
 
US Сергей-4030 #08.07.2008 18:55  @Mishka#08.07.2008 04:57
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
>Ну так сколько возможных ходов?

Количество возможных позиций, как посчитал Мишка, можно оценить сверху как


Это, конечно, число немаленькое, но надо учесть, что во-первых, это СИЛЬНО сверху. На практике, наверное, порядков 20-25 можно сбросить точно. А во-вторых, так или иначе, "ученые" в курсе. ;)
 
DE dercoolman #08.07.2008 19:01
+
-
edit
 

dercoolman

опытный

Да хрен с ними с учёными, главное что компы даже в будущем не потянут, а будут только "по деревьям" решать плюс огромная база данных с играми. Но всё равно люди уже не противники, хорошо что пока в шахматах.
 
US Сергей-4030 #08.07.2008 19:04  @дровосек3d#08.07.2008 19:01
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
dercoolman> Да хрен с ними с учёными, главное что компы даже в будущем не потянут, а будут только "по деревьям" решать плюс огромная база данных с играми. Но всё равно люди уже не противники, хорошо что пока в шахматах.

Откуда ж это известно, что не потянут? Уже и сейчас хорошо тянут, хотя и не полным перебором.

ЗЫ А как еще можно решать, кроме как "по деревьям"?
 
DE dercoolman #08.07.2008 19:13
+
-
edit
 

dercoolman

опытный

Я имел в виду за приемлемый отрезок времени.

Сейчас просматривается база данных находится подходящая игра или игры выбирается пара ходов оптимальных по мнению компа и прорешиваются деревья на 8-10 ходов вперёд , лучшее результат выбирается и делается ход и так каждый раз заново.
 
+
-
edit
 

Mishka

модератор
★★☆
На первых ходах уже давно ничего не "прорешивается вперёд". Существующая БД позволяет пошерстить по ней. Ну и окончания там есть, хотя с окончаниями всё намного проще. Вот серединка, тут да, решается.
 
+
-
edit
 

Mishka

модератор
★★☆
Деревья в этом случае довольно плохо для представления ходов, т.к. элементарный ход назад приведёт к бывшему состоянию, т.е. надо лес деревьев со ссылками друг на друга, что есть нормальный полноценный граф, а не граф без циклов, который есть дерево (если брать не орграфы). Там дерево решений, скорее всего. А вот сама игра — граф с циклами. Ну, или можно представить как циклы перестановок в алгебре. Хотя это будет то же самое.
 
US Сергей-4030 #08.07.2008 19:22  @дровосек3d#08.07.2008 19:13
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
dercoolman> Я имел в виду за приемлемый отрезок времени.
dercoolman> Сейчас просматривается база данных находится подходящая игра или игры выбирается пара ходов оптимальных по мнению компа и прорешиваются деревья на 8-10 ходов вперёд , лучшее результат выбирается и делается ход и так каждый раз заново.

Кто сказал, что на 8-10? Зависит от позиции. И что значит - "за примлемый"? Уже сейчас лучшие программы играют лучше лучших гроссов. Вполне себе находят не только "за приемлемое время", а просто-таки за нормальную партию ходы лучше, чем гроссмейстеры. Шахматы, по большому счету, помирают как творчество. Шахматы сейчас - гольный спорт весьма оригинального вида.
 
DE dercoolman #08.07.2008 20:31
+
-
edit
 

dercoolman

опытный

Ладно, ещё раз.

Я разделяю игру в шахматы компом на два типа бруте форце и по деревьям. Так вот первое нам, точнее компам не светит никогда. Второе хватает на 8-10 может не много больше ходов вперёд при этом комп не считает все возможные ходы а выбирает наиболее оптимальные ориентируясь на тактические приёмы из банка игр. Вот на сколько это дерево глубоко в игру зайдет, а также в ширь раздастся зависит напрямую от мощи компа. Как мишка сказал начало просто берут из банка, конец от 10 фигут и меньше считают до конца. всё имхо
 
US Сергей-4030 #08.07.2008 20:39  @дровосек3d#08.07.2008 20:31
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
dercoolman> Ладно, ещё раз.
dercoolman> Я разделяю игру в шахматы компом на два типа бруте форце и по деревьям.

И по какому же принципу вы разделяете? :) В чем кардинальное различие? "Brute force" - вам кажется, это "не по деревьям", что ли?

dercoolman>Так вот первое нам, точнее компам не светит никогда.

Никогда - слишком громкое слово. Не говоря уж о том, что это неверно. Вернее, не доказано. Ибо легко может быть, что уже при просчете всего-то в 10 (сто, тысячу) раз большего количества вариантов, чем сейчас, шахматы будут решены. Ваше впечатление, что из того, что партия может длиться бесконечно, следует то, что шахматы не могут быть решены попросту неверно, оно проистекает из незнания теории.
 
US Сергей-4030 #08.07.2008 20:40  @дровосек3d#08.07.2008 20:31
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
dercoolman> Ладно, ещё раз.
dercoolman> Как мишка сказал начало просто берут из банка, конец от 10 фигут и меньше считают до конца. всё имхо

И чем же отличается от вашего "brute force"? Таблица дебютов и окончаний - она, по-вашему, господом богом выдана? ;)
 
US Сергей-4030 #08.07.2008 20:41
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
В эндшпилях компьютерные программы могут и по 50 ходов вперед просчитывать, кстати.
 
US Сергей-4030 #08.07.2008 20:45
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Коротко схема такая: допустим, ход белых. И у них есть только 2 возможности. Первая приводит к выигрышу белых в 5 ходов. Вторая - непонятно, не просчитывается до конца. Вам кажется, что эта позиция не решена на том основании, что белые могут сделать не выигрывающий ход? ;)
 
1 2 3 4

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru