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

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

  1. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Это не возможно.
    В 1958 году когда сделали первый транзистор, с каждым годом его число на разных схемах, платах удваивалось,
    еще тогда по подсчетах ученого Мора(закон его не помню) квантовые компы должны появиться в 2020 году и которые по
    мощности привысят современные в n-раз. Только тогда и то не верится.
    В наше время это не возможно, хотя б потому что шашки намного проще чем шахматы и там даже не смогли придумать нечто подобное.
  2. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Если кто то напишет, что уже появились квантовые компы, можно смело утверджать что им ещё далеко до совершенства.

    Квантовый компьютер — гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как квантовый параллелизм и квантовая запутанность.
  3. Блаженный_Поэт Поэт

    • Команда форума
    Рег.:
    19.10.2008
    Сообщения:
    3.294
    Симпатии:
    115
    Репутация:
    4
    Адрес:
    Россия
    Оффлайн
    Смыслов как то сказал, что число возможных ходов.. 10в^120 степени!!! Это больше чем Атомов во вселенной! О чем вы говорите? Пойди первым ходом подругому(1. Б3, Ж4, и тп) , и уже будут другие Шахматы, я уж не говорю о том, что в каждой позиции на 6-10 ходу можно сыграть по разному..............
  4. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.397
    Симпатии:
    2.915
    Репутация:
    91
    Адрес:
    Москва
    Оффлайн
    Подойдёт интерпретатор почти любого функционального языка.
    Хаскеля, например.
    http://ru.wikipedia.org/wiki/HUGS
  5. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Значит, Смыслов был настолько же наивен, как и вы, если ему верите.

    Только число ПАРТИЙ больше чем атомов во Вселенной. Но никак не число ходов, позиций и т.д. В этом чудовищном числе партий все ходы будут встречаться много и очень много раз. И каждая позиция - тоже много раз.
  6. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Число ходов и позиций - не больше 10 в 50-й степени, как я уже писал. А если отсечь все нелегальные позиции - то может и 10 в 40-й степени получится. Человечеству вполне под силу лет через 1000 посчитать и изучить всю шахматную игру.
  7. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Ну да будет встречаться, особенно в партиях мастеров или гроссов.
    И то будут только Те дебюты, позиции до хода 15-30 в которых можно на что то надеяться обеимы сторонами.
    Представться себе начальную позицию.
    Сначала есть 18 ходов белыми, столько же черными.
    И если не менятся до хода 20 будет если столько веток, что сумарное количество вариантов будет где то 1.000.000.000.000.000.000.000(если есть конечно такое число) если не больше.

    Даже если 1000 процессоров вместе подключили, они не смогли бы верно подсчитать.
  8. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    В начальной позиции есть 20 ходов, а не 18.
    А найбольше в миры число (нашел в нети):

    Оперируя большими числами, ученые пользуются степенями 10 для того, чтобы избавиться от огромного количества нулей. Например, 19 160 000 000 000 миль можно записать как 1,916·1013 миль.
  9. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.486
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Значиться так. Харош фуфло толкать. :)
    Считаем.
    Начинаем с 32 фигур и игнорируем взаимное расположение, то есть плюем на легальность позиции.
    Первую фигуру можно поставить на 1 из 64 клеток. Вторую уже только на одну из 63 клеток и так далее. Получаем максимальное количество возможных расположений (позиций), при наличии на доске всех 32 фигур, равным : 64*63*62*61*... 35*34*33 = 4,8221992399111497884345907291989e+53
    +
    ТЕПЕРЬ ПЛЮС КОЛИЧЕСТВО ПОЗИЦИЙ ПРИ 31 ФИГУРЕ
    64*63*62*61*... 35*34
    +
    ПЛЮС КОЛИЧЕСТВО ПОЗИЦИЙ ПРИ 30 ФИГУРАХ
    64*63*62*61*... 35
    +
    ...
    +
    ПРИ ГОЛЫХ КОРОЛЯХ
    64*63

    Кто возмется посчитать?

    У меня вышло 4,972750651577952297214065254525e+53
  10. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    ProstoTak

    Если мы хотим посчитать до порядка (т.е. - узнать что ближе - 10 в 50-й степени или 10 в 49-й), то ваши плюсы вообще не нужны, т.к. они все вместе взятые сравнимы с первым слагаемым - 64*63*62*61*... 35*34*33 . А это не что иное, как 64 факториал разделить на 32 факториал. Т.е. около 10 в 53-й степени. Но если выбросить все нелегальные позиции, каких очень много, то будет меньше чем 10 в 50-й степени точно. Может, и 10 в 40-й. С большой точностью вы все равно не посчитаете. С другой стороны, пешки могут превращаться в фигуры, что увеличивает число позиций. Поэтому я придерживаюсь того мнения, что около 10 в 50-й. И массы Луны, как самого плотного носителя информации - хватит чтобы это все записать. Подробнее - читайте мой пост выше.
  11. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    При голых королях 64*56(если не так, то точно не 64*63), король белый и король черный вместе не могут стоят)))))
    Король может также стоять на a1,a8,h1,h8
    Значит все ети математические подсчеты не верные.
  12. Блаженный_Поэт Поэт

    • Команда форума
    Рег.:
    19.10.2008
    Сообщения:
    3.294
    Симпатии:
    115
    Репутация:
    4
    Адрес:
    Россия
    Оффлайн
    я вас в вел в заблуждение, Число возможных ПАРТИЙ 10 в 120 степени, а это больше чем атомов во вселенной!

    Прошу прощения, писал по памяти.................:(
  13. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Угу, а еще пешки могут стоять только на 48 полях. А еще они могут быть превращены в фигуры. А еще короли под шахом стоять не могут если ихний ход. Можно продолжить.
  14. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.486
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Нет наврал я с алгоритмом. Ведь наборов, например, по 31 фигуре может быть 10, а по 30 фигур уже целая куча не говоря уже по 16 фигур. Короче, считайте сами :)
    Любитель_ нравится это.
  15. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    1 - лично я в заблуждение не впал.
    2 - вопрос - а зачем нам нужно ваше число партий?
    Или вы считаете, что для того чтобы посчитать шахматы - нам нужно все партии прогнать?
  16. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.486
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Ну как верхний предел, я соглашусь с числом 10^54

    Теперь давайте попробуем определить нижний предел количества ЛЕГАЛЬНЫХ позиций.

    Есть предложения?
  17. Programmierungchess Учаcтник

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

    P.S. Уже начал считать, до 40 до считал)))))))))
  18. Programmierungchess Учаcтник

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

    P.S. Уже начал считать, до 40 до считал)))))))))
  19. Programmierungchess Учаcтник

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    А какие позиции легальные?
  20. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.486
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    Легальные - это позиции которые могут возникнуть в ходе партии начавшейся с классической расстановки фигур ходом белых по современным правилам шахмат.
  21. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    396
    Симпатии:
    466
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Блин, ну кто так считает!
    Еще более 30 лет назад был предложен способ отображения любой шахматной позиции, умещающийся в 150 бит. Отсюда следует простой вывод - число разных позиций равно 2^150. Или 1024^15. Или примерно 10^45.
    Читайте классику!
  22. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Посты Хайдука хаотичны, а потому бессмысленны.

    зы Ж)
  23. drowsy Учаcтник

    • Участник
    Рег.:
    07.09.2006
    Сообщения:
    1.282
    Симпатии:
    1
    Репутация:
    0
    Адрес:
    Toronto, Canada
    Оффлайн
    Простой вывод не верен.

    Число разных позиций не превышает 2^150.
  24. Осипов Юрий Учаcтник

    • Участник
    Рег.:
    18.06.2007
    Сообщения:
    396
    Симпатии:
    466
    Репутация:
    11
    Адрес:
    Правда
    Оффлайн
    Согласен. Попробуйте уменьшить.
  25. Хайдук Учаcтник

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

    • Участник
    Рег.:
    20.01.2009
    Сообщения:
    22
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Короче число всех позиций безконечность.
    Доказательство простое:
    Если белые и черные почнут скакать лошадями 45 ходов, потом последует размен одной пешки, потом еще 45 ходов лошадями, дальше последует еще один размен пешкой...........А еще они могут скакать по разному, так что и тут назбираеться еще несколько
    мильярдов(наверное намного больше) варинтов.......

    Я считаю, что число шахматных позиций, даже через 1000 лет, будут считать как безконечность.
  27. ProstoTak Ветеран

    • Ветеран
    Рег.:
    11.02.2006
    Сообщения:
    5.486
    Симпатии:
    123
    Репутация:
    1
    Оффлайн
    В общем верно. Но только я не знал этого способа про 150 бит. А хватит ли? Хотя Осипову можно поверить на слово :)

    Итак верхний придел пока упал до 10^45. Кто меньше? :) И нижний, народ, не забывайте про нижний! Какие мысли?
  28. dan77790 Учаcтник

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

    С чего вы взяли, что игру можно решить лишь исчерпывающим перебором?
  29. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Меня вот интересует - вы не читаете посты которые здесь пишут, или просто не способны понять? Все пишут и доказывают, что позиций не больше чем 10 в 45 степени - а вы все равно про какую-то бесконечность... Между прочим 10 в 45 степени человечеству, уверен, под силу посчитать лет через 1000.
  30. Edwards Ветеран

    • Ветеран
    Рег.:
    10.02.2006
    Сообщения:
    6.330
    Симпатии:
    320
    Репутация:
    20
    Адрес:
    CПб
    Оффлайн
    А, может, мозги у решающих плохо структурированы? :)
    Вообще, меня это действительно удивляет - неужели нет возможности решить игру мат. алгоритмами, позволяющими экономить ресурсы, не перебирать всё грубо?
    Ведь очевидно, что какие-то закономерности в игру заложены. Собственно, мы, люди оцениваем позиции исходя из представлений об этих закономерностях. Да и компьютеры тоже...
    Просто пока всё это неточные очень формулировки.
    Возможно ли именно математическое, экономичное решение шахмат?
    Интуитивно думается, что да.
  31. Edwards Ветеран

    • Ветеран
    Рег.:
    10.02.2006
    Сообщения:
    6.330
    Симпатии:
    320
    Репутация:
    20
    Адрес:
    CПб
    Оффлайн
    Можно переформулировать мой вопрос так.

    Возможно ли создание формулы, по которой можно будет точно оценить любую позицию (1, 1/2, 0), исходя лишь из данных, заложенных в саму эту позицию?
    Т.е., исходя из знания о материале на доске, его расположении, очереди хода...
    Не прибегая к перебору вариантов дальнейшего развития событий...
  32. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Не знаю насчет 150 бит, а я в своем шахматном движке использую хэш-таблицы, и для минимизации используемой оперитивной памяти - смог упаковать инфу о позиции в 192 бита. Но, верю что можно и в 150 бит упаковать. Поэтому очень рад! Это доказательство что позиций - точно не меньше 10 в 45-й степени. Но и в них много нелегальных, поэтому это только верхняя граница.

    Уже почти уверен, что реальное количество позиций где-то около 10 в 40-й степени. А значит, не нужна масса Луны как самого плотного носителя информации, чтобы записать всю информацию о шахматах. Нужна масса всего 10 миллиардов тонн. Такую массу имеет кубик металла размером в 1 км.
  33. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.397
    Симпатии:
    2.915
    Репутация:
    91
    Адрес:
    Москва
    Оффлайн
    А как вы в 150 бит историю повторений запаковать собираетесь?
    Начальная позиция и позиция после 1. Nf3 Nc6 2. Ng1 Nb8 - это разные позиции!
  34. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    Конечно, возможно, только формула эта будет настолько огромной, что вычислять по ней (1, 1/2, 0), будет не намного быстрее, чем просто все перебрать.
  35. Skipper_NORTON Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    512
    Симпатии:
    2
    Репутация:
    0
    Оффлайн
    А нам не нужно записывать историю повторений. Когда создаются шахматные базы путем ретроанализа - то приведенные вами позиции - одинаковые а не разные. Если какая-то сторона может сделать ничью путем повторения ходов, то они останутся непомеченными, следовательно - ничейными. Поэтому для программы использующей базы - первая позиция - уже будет ничейной, хотя люди это увидят, только когда 3 раза произойдет повтор.

    У движков тоже так - если играет по базам - сразу показывает - здесь ничья. А если не по базам - то показывает сначала отличающуюся от ничьи оценку, и только увидев повторы которые произошли в игре - показывает ничью.

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