Анализ начальной позиции

Когда речь идёт об очень (экспоненциально) больших и принципиально неустранимых объёмах вычислений (скажем, проблемы т.н. NP типа), любые количественные оценки ненадёжны. Такие проблемы считают практически недоступными при любом обозримом развитии компьютерных технологий, так как речь идёт о вычислениях на протяжении тысяч или миллионов лет. Tрудно прикинуть сколько времени отнимет уделать (строго) позиций порядка 10^45 - 10^50 в шахматах (в шашках, которые решили, позиций порядка 10^18).

Если говорить о нечётком, но практически удовлетворительном решении, то такое нелегко фиксировать. Скажем, даже сегодня можно считать, что нечто вроде решения уже имеем в смысле, что комп почти не проигрывает гроссам. Видимо, однако, партии между компами еще очень долго останутся непредсказуемыми и значит столь же долго практического решения не будет. Когда можно будет надёжно пренебречь остававшимися необсчитанными, но якобы "тупыми" и несущественными позициями тоже неясно.

Это не просто не решение, это ничего общего с решением не имеет.
Допустим некий человек не проигрывает программам в ГО - он что, "вроде решил" ГО?

Да, речь о Chinook и согласно http://en.wikipedia.org/wiki/Checkers решение вроде строгое:

On July 2007, in an article published in Science Magazine, Chinook's developers announced that the program had been improved to the point where it could not lose a game. If no mistakes were made by either player, the game would always end in a draw. After eighteen years, they have mathematically proven a weak solution to the game of Checkers. Using between 200 desktop computers at the peak of the project down to around 50 later on, the team made just 1014 calculations to search from the initial position to a database of positions with at most 10 pieces.

Что такое слабое решение (weak solution) для некоторой игры (http://en.wikipedia.org/wiki/Solved_board_games)?

... solving a game means providing an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game.

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

Может "отсекали", но, по-видимому, уже знали наверняка исход того, что отсекают. Скорее всего "отсечённое" принадлежало к уже обследованным и доказанным классам позиций.

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

Ссылку можно?

Это скорее к ув. Kirr-у : когда можно объявить, что практическое решение поймано и ... с рук долой?

Долго искать. Отсекали они по материалу, считая что с лишним материалом (не помню конкретно сколько - вроде 3 шашки) не может быть проигранно...
Надеюсь поверите мне, что и без 5 шашек может быть выиграно?
И где полученное ими дерево перебора?

Очень трудно прогнозировать развитие компьютерных возможностей. Кто мог представить лет 20 назад, что объёмы памяти в гигабайты и терабайты будут реальностью в обозримом будущем?

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

Деталей не знаю, но не думаю, что могли так тривиально ошибиться.

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

Повтори. ©

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

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

А интересно, ведутся ли чисто математические исследования шахмат? Или все ограничилось книгой Гика?) Не применение минимакса в прогах, а чистая математика шахмат.... Что-то не встречал такого....

2 Хайдук

А не кажется ли вас, что хаос - это непонятый нами порядок?

Vladimirovich

Я его статьи все прочел по несколько раз на этом сайте) Интересно, но все же.... это только первый шаг)

А вы читали допустим вот это?

http://www.abitura.com/modern_physics/computer.html

Скажем, имеются базы Налимова, а более сложные позиции классифицируют и решают, сводя сложные классы к решению более простых, а те к базам Налимова, которые решают незамысловатым исчерпывающим перебором.

Не кажется - хаос есть хаос.

Первобытному человеку современный Нью-Йорк тоже казался бы хаосом)

+64
Как раз исключения случайны - любая шахматная стратегия чревата множеством случайных пробоин, которые могут разрушить и заменить ее совершенно другой, непохожей стратегией. Значит сама шахматная упорядоченность возникает случайно/спонтанно и также рассасывается и тает.

Ну, если честно, на квантовые компьютеры я как-то и не расчитывал.
Скорее какие-нибудь графеновые транзисторы, как Владимирович процитировал.

Статейка интереная кстати. Только не надо её понимать слишком буквально, это скорее фантазии на темы квантовой механики и жизни.

Тёплая вода еще цветочек, по крайней мере у нее глобальные статистические параметры как температура. Турбулентность (и шахматы) хуже, ибо хаос и структуры перемешаны невообразимо. Опять "В Мире Науки" должна быть недавняя статья испанского физика о спонтанном возникновении порядка из хаоса и возврате обратно в хаос и т.д. Жесть :/

В каждой сказке есть доля сказки)

В любом хаосе скрыт порядок. Надо только суметь его увидеть. ©