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

Тема в разделе "Машинное отделение", создана пользователем Везде цуцванг, 19 янв 2009.

  1. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.390
    Симпатии:
    2.885
    Репутация:
    91
    Адрес:
    Москва
    Оффлайн
    "И не в лотерею, а в преферанс, и не выиграл, а проиграл, и не Волгу, а сто рублей" © :)
  2. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Не помню, чтобы в этой ветке кто-то утверждал что гроссы будут хранить в памяти терабайты таблиц. Речь, конечно, о компах. Насчёт "негде хранить" и "долго искать", я не зря написал в прогнозе "через 50 лет". :)

    (Это такой приём полемики - постить под видом возражения очевидные истины?)
  3. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Имел в виду, конечно, "решили один из вариантов шашек". Видимо нужно было точнее выражаться.
  4. Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Если речь о Chinook, то решение как раз нечёткое, и поэтому доказательство - нестрогое.
  5. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Когда речь идёт об очень (экспоненциально) больших и принципиально неустранимых объёмах вычислений (скажем, проблемы т.н. NP типа), любые количественные оценки ненадёжны. Такие проблемы считают практически недоступными при любом обозримом развитии компьютерных технологий, так как речь идёт о вычислениях на протяжении тысяч или миллионов лет. Tрудно прикинуть сколько времени отнимет уделать (строго) позиций порядка 10^45 - 10^50 в шахматах (в шашках, которые решили, позиций порядка 10^18).

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Это не просто не решение, это ничего общего с решением не имеет.
    Допустим некий человек не проигрывает программам в ГО - он что, "вроде решил" ГО?
  7. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Да, речь о 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.
  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    По заявлениям авторов решение не строгое, поэтому на то что написано в wiki можно положить.
    Нет никаких гарантий что у Чинука нельзя выиграть из классической начальной позиции.
  9. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Может "отсекали", но, по-видимому, уже знали наверняка исход того, что отсекают. Скорее всего "отсечённое" принадлежало к уже обследованным и доказанным классам позиций.

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

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Ссылку можно?
  11. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Это скорее к ув. Kirr:) : когда можно объявить, что практическое решение поймано и ... с рук долой? :D
  12. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Долго искать. Отсекали они по материалу, считая что с лишним материалом (не помню конкретно сколько - вроде 3 шашки) не может быть проигранно...
    Надеюсь поверите мне, что и без 5 шашек может быть выиграно? :)
    И где полученное ими дерево перебора?
  13. Александрович Учаcтник

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Очень трудно прогнозировать развитие компьютерных возможностей. Кто мог представить лет 20 назад, что объёмы памяти в гигабайты и терабайты будут реальностью в обозримом будущем?
  14. Vladimirovich Консультант

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Есть предположение, что вторая производная этого роста скоро будет отрицательной ;)
    Есть же физические пределы, и они уже рядом.
  15. Александрович Учаcтник

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Если говорить о существующей кремниевой полупроводниковой элементной базе, то более-менее да, хотя ещё порядок-другой из нёё выжмут, я думаю.
    Но на подходе есть и другие технологии. Так что я не знаю, во что оно выльется.
    И то не считая возможности развития математики и перехода от тупого счёта к более продвинутым методам. :)
  16. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Деталей не знаю, но не думаю, что могли так тривиально ошибиться.

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

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    :)
    Повтори. ©
  18. Vladimirovich Консультант

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Обещают, да.
    http://lenta.ru/news/2008/12/12/graphene/
    "Графеновый транзистор разогнали до 26 гигагерц"
    "Показатели графенового транзистора не рекордные. Так, частота транзисторов на основе фосфида индия составляет 1000 гигагерц. "
  19. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Недавно в журнале "В Мире Науки" была статья об ограничениях квантовых компьютеров. По мнению автора их архитектура подходит узкому классу задач, а большинство не сможет выграть существенно в производительности.

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

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    А интересно, ведутся ли чисто математические исследования шахмат? Или все ограничилось книгой Гика?) Не применение минимакса в прогах, а чистая математика шахмат.... Что-то не встречал такого....

    2 Хайдук

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

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Мастер Шашин, насколько мне известно развивает
    (На e3e5 статьи были)
  22. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    Vladimirovich

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

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
  24. Vladimirovich Консультант

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    dan77790

    Мне все это кажется баловством.
    Исключения забьют любую теорию такого рода, хотя определенный смысл можно в них найти.
    Алгоритмы рулят до определенного уровня сложности модели.
    Дальше перебор.
  25. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Скажем, имеются базы Налимова, а более сложные позиции классифицируют и решают, сводя сложные классы к решению более простых, а те к базам Налимова, которые решают незамысловатым исчерпывающим перебором.
  26. Vladimirovich Консультант

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Например, игра в спички. Детская такая.

    Выкладывается N рядов c произвольным количеством спичек ( разным)
    Можно взять любое количество, но только из одного ряда.
    Кто возьмет последнюю, тот и победил.

    Вот это полностью алгоритмизируется.
  27. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Не кажется :) - хаос есть хаос.
  28. Vladimirovich Консультант

    • Ветеран
    Рег.:
    27.09.2006
    Сообщения:
    5.693
    Симпатии:
    301
    Репутация:
    19
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Есть метрика - энтропия.
  29. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    Первобытному человеку современный Нью-Йорк тоже казался бы хаосом)
  30. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    +64
    Как раз исключения случайны - любая шахматная стратегия чревата множеством случайных пробоин, которые могут разрушить и заменить ее совершенно другой, непохожей стратегией. Значит сама шахматная упорядоченность возникает случайно/спонтанно и также рассасывается и тает.
  31. Александрович Учаcтник

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Ну, если честно, на квантовые компьютеры я как-то и не расчитывал. :)
    Скорее какие-нибудь графеновые транзисторы, как Владимирович процитировал.
  32. Александрович Учаcтник

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Статейка интереная кстати. Только не надо её понимать слишком буквально, это скорее фантазии на темы квантовой механики и жизни. :)
  33. Хайдук Учаcтник

    • Участник
    Рег.:
    02.12.2007
    Сообщения:
    4.490
    Симпатии:
    9
    Репутация:
    0
    Оффлайн
    Тёплая вода еще цветочек, по крайней мере у нее глобальные статистические параметры как температура. Турбулентность (и шахматы) хуже, ибо хаос и структуры перемешаны невообразимо. Опять "В Мире Науки" должна быть недавняя статья испанского физика о спонтанном возникновении порядка из хаоса и возврате обратно в хаос и т.д. Жесть :D :/
  34. dan77790 Учаcтник

    • Участник
    Рег.:
    06.03.2008
    Сообщения:
    3.792
    Симпатии:
    16
    Репутация:
    0
    Оффлайн
    В каждой сказке есть доля сказки)
  35. Александрович Учаcтник

    • Участник
    Рег.:
    17.02.2009
    Сообщения:
    220
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    В любом хаосе скрыт порядок. Надо только суметь его увидеть. ©

Поделиться этой страницей