- В этой теме 169 ответов, 7 участников, последнее обновление 17 лет, 11 месяцев назад сделано
.
-
Сообщения
-
Хоть и оффтопик, надеюсь не побьют
Ну во-первых, кто нас заставляет пользоваться тупым перебором и запоминанием. Есть игры, в которых был найден точный алгоритм выигрыша, несмотря на большое количество возможных позиций и разветвлений дерева.
Существуют в конце концов нейронные сети, хотя их прогрес не особо сильный, но все-таки до перворазрядника они быстро тренируются, имея только знания о ходах в начале. Возможно когда-нибудь они и дорастут до абсолютного уровня. Ведь когда человек научится отличать скажем кошку от бабочки он уже никогда не ошибется, так и тут — отличать выигрышные позиции от ничейных.Что касается скорости света, скорость ДВИЖЕНИЯ возможно и не бывает выше скорости света, но вот скорость ПЕРЕМЕЩЕНИЯ может быть и выше, что довольно просто доказывается.
Нейронные сети позволяют обучаться (обучать оценке, переборным алгоритмам) и т.д.
Но не ПОЗВОЛЯЮТ РЕШИТЬ ИГРУ!!!!
Не позволяют доказать предопределенность результата и показать способ его достижения…Существуют в конце концов нейронные сети, хотя их прогрес не особо сильный, но все-таки до перворазрядника они быстро тренируются, имея только знания о ходах в начале.
Вы наверно знаете что мной написаны шахматные программы.
То есть я занимаюсь этим вопросом.
Но я ни разу не слышал о шахматной программе построенной на нейронных сетях играющей в силу первого разряда
Можно ссылку?Насчет максимальной скорости передачи информации — всё-таки скорость света. Я уверяю что этой точки зрения придерживается большинство ученых (Это если вы имеете в виду скорость передачи информации о наблюдении парной частицы в квантовой теории — которая считается практически не доказанной, и неприменимой)
То шахматы невозможно решить за время жизни вселенной…
Современными алгоритмами на современных машинах. Кто сказал, что нет более эффективного алгоритма, который может все посчитать даже на современных компьютерах?
Что касается скорости света, скорость ДВИЖЕНИЯ возможно и не бывает выше скорости света, но вот скорость ПЕРЕМЕЩЕНИЯ может быть и выше, что довольно просто доказывается.
В физике ничего доказать нельзя. Можно только экспериментально проверить. Пока вроде считается, что скорость света это предел для любого взаимодействия.
То шахматы невозможно решить за время жизни вселенной…
Современными алгоритмами на современных машинах. Кто сказал, что нет более эффективного алгоритма, который может все посчитать даже на современных компьютерах?
То что предельная (наилучшая) сложность ретроспективного анализа — линейная зависимость от количества результативных позиций — доказано…
То что предельная (наилучшая) сложность ретроспективного анализа — линейная зависимость от количества результативных позиций — доказано…
Так ведь речь не о ретроспективном анализе. А о эвристическом алгоритме, который за пару минут выдает верную оценку позиции с вероятностью более 99,7% (или больше).
Доказать несуществование такого алгоритма невозможно.Но возможен ли алгоритм оценки со 100% достоверностью?
И каким образом можно доказать его 100%-ную достоверность?
Ретроспективным анализом?Возможен или нет — это науке неизвестно
И каким образом можно доказать его 100%-ную достоверность? Ретроспективным анализом?
Ведь для доказательства альфа-беты не нужен ретроспективный анализ. Для каждого алгоритма свой способ доказательства корректности.Тогда можно сказать по другому — поиск хороших ОФ идёт очень медленными Темпами, а в переборных алгоритмах вообще ничего нового практически нет.
Например в Шахматах современная оценочная функция не так уж и сильно продвинулась со времен Каиссы.
А переборные алгоритмы вообще те-же. Все изменения связаны с увеличением быстродействия и доступной памяти, а алгоритмы те-же.Действительно революционных алгоритмов так и не появилось.
+300 Пунктов на Null Move, + 100 на LMR, +50 на NegaScout (сам метод появился только в результате увеличения доступной памяти под хеш, и принципиального преимущества по сравнению с чистой Альфа-Бетой не дает)
и т.д.Теория построения ЭБ — такая-же как и была тогда, во времена Каиссы.
В результате оказалось что даже опираясь на знания пятнадцатилетней давности — можно весьма быстро можно написать достаточно сильную (в масштабах России) шахматную программу.
Ребята, эка вас занесло!…
Речь не шла о сиюминутном решении поставленной задачи .
Любую задачу (игру) с полной информацией можно решить двумя (а может и более, но двумя точно!) способами!
(1) – создать алгоритм полного решения (так сказать «в один присест» — с одной попытки),
(2) – создать алгоритм НАКОПЛЕНИЯ решения задачи – то есть решать задачу небольшими кусочками, суммируя результаты, и каждый раз проверяя по способу (1) – а не хватит ли копить и не решается ли УЖЕ задачи.Первый способ, конечно же, требует и программных ухищрений, и оглядки на быстродействие, и оглядки на накопление информации. ИДЕТ МОЗГОВОЙ ШТУРМ! Но и здесь я не уверен, что проблема так уж неразрешима!…
Второй способ – это скорее разновидность первого, где НАКОПЛЕНИЕ ИНФОРМАЦИИ идет постоянно (вспомните БАЗЫ ОКОНЧАНИЙ!). Но самое главное, что этот способ позволяет не оглядываться на «ограничение на размеры ячейки памяти», так как есть неограниченная память компьютера, которую можно наращивать.И еще. Слышал я, что 300000 – это скорость света только в вакууме, а в веществе она может быть больше…
Да. Еще. Не думаю, что этот разговор offtop…
Матч окончился!
Матч не вызвал интереса чисто шашечного, но породил этот разговор!
Так почему же его надо считать offtop???Скорость света в среде не больше, а меньше
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) —
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать — сразу запустим и будем ждать результата, или будем делать перерывы — не имеет никакого значения.Скорость света в среде не больше, а меньше
Методов решения (Для задач которые не имеют явного алгоритма выигрыша (либо тривиальную 100%-но достоверную ОФ), и которые не решаются специфическими методами (Гекс)) —
Перебор (До логического конца) и Ретроспективный анализ (построение ЭБ) и их комбинации.
А как мы будем их запускать — сразу запустим и будем ждать результата, или будем делать перерывы — не имеет никакого значения.Если бы была меньше, то моя память не оставила бы следов от такого сообщения! Мне говорили, что БОЛЬШЕ. И говорили вполне авторитетные в науке люди… Надо разобраться…
Как?
А как сегодня работают над решением задачи под названием РУССКИЕ ШАШКИ, «тундровцы» и Старцев? (Чуть не написал «плюсовцы», но он один…) Накапливают РЕШЕННЫЙ материал «снизу» (база окончаний — и здесь возможности памяти неограничены! — способ (2)), плюс улучшают алгоритм так сказать «пробивки» задачи (способ (1)) с учетом накопленной базы.
И плюс еще накопление миттельшпилей! Это как раз и есть те самые способы (цепочки) пробива задачи от дебюта к базе окончаний.Здесь нет единовременности решения задачи. Задача решается кусочками. И решение её растянуто во времени настолько, насколько это надо решателю.
Вы же предлагаете (и обсуждаете) решение задачи типа: задал алгоритм и пошел (спать, пить кофе, смотреть футбол…) по своим делам. Такой способ конечно же столкнется с массой затруднений…
Возможности памяти не ограничены?
Я вам напишу формулу необходимой памяти для несжатых безранговых N-шашечных баз, а вы попробуйте туда подставить 12-ть
4^N*32!/(32-N)!/N!/4 Байт
(Делим на четыре — Так как храним в байте четыре позиции)
Или формула для необходимой памяти для 12+12 простых…
32!/12!/12!/8!/4 БайтЧтоб не мучать — в первом случае 947000 Гбайт
Во втором — 7000 ГбайтNS давайте не будем заниматься фигней. Во-первых, завтра терабайтные диски поступят в массовую продажу, поделите на емкость дисков лет 15-20 назад и получите что требуемый вам объем будет в обычной настольной персоналке через пару-другую десятков лет.
Во-вторых, объем реальной ранговой 12-шашечной ЭБ не будет превышать 10 терабайт, что уже сейчас вполне реально, и проблема думается не в размере дисков а в скорости генерации. Если Вы можете написать алгоритм генерации на современных компьютерах за разумное время и не хватает емкости жестких дисков — я Вам их найду
И в третьих, если вы (я) не знаем алгоритма для написания абсолютной шашечной программы это не значит что его не существует в принципе.
- Для ответа в этой теме необходимо авторизоваться.