К>Не знаю, как устроены современные хорошие программы, но в свое время читал книгу М.Ботвинника о его программе "Каисса". К>Там в основу был поставлен алгоритм постановки целей (то есть рассматривается набор осмысленных задач и способы их достижения).
Ботвинник М. Алгоритм игры в шахматы. Тираж 25.000 экз. М. Наука 1968г. 96 с. Ботвинник М. М. О кибернетической цели игры. М.: Сов. радио. 1976г.
-- именно ее я и читал. Возможно, даже валяется где-то дома.
В инете книга не опубликована. (Я не обнаружил, во всяком случае).
Здравствуйте, Real 3L0, Вы писали:
R3>Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ...
Это где так, у тебя в компьютере?
Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
Здравствуйте, Vadim B, Вы писали:
VB>Это где так, у тебя в компьютере?
Нет, судил по всяким высказываниям из разных источников, например, "максимальный размер диска, доступный в 1998 году, был бы 25-45MB" (извините, за копирование)
VB>Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
Вполне возможно, не буду спорить. Мои данные касаются только российских (советских) пользователей.
Здравствуйте, Real 3L0, Вы писали:
VB>>Это где так, у тебя в компьютере?
R3>Нет, судил по всяким высказываниям из разных источников, например, "максимальный размер диска, доступный в 1998 году, был бы 25-45MB" (извините, за копирование)
VB>>Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
R3>Вполне возможно, не буду спорить. Мои данные касаются только российских (советских) пользователей.
Вот как раз у советских пользователей в 1988-89 году массово шли винты на 20-40 MB. Ну, скажем, в провинции было обычно 20, а 40 считалось барством, а в столицах уже 40 у многих было. Я, конечно, понимаю, что 1988 год сейчас уже выглядит как доисторическая эра, но тут есть люди, которые его еще хорошо помнят
Здравствуйте, Кодт, Вы писали:
R3>Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ... К>То есть на 3.5 десятичных порядка. А там их — 82. К>Такими темпами мы успеем за 5*82/3.5 ~ 110-120 лет. Если сумеем к тому времени вовлечь все электроны вселенной в это бестолковое занятие.
Ну, на счет бестолковости, посмотри какой ажиотаж, какие бабки крутятся вокруг соревнования машины и человека!
Здравствуйте, Real 3L0, Вы писали:
R3>Создаем базу, в которой собраны все возможные расстановки всех возможных фигур на доске.Создаем связи между расстановками, т.е. связь есть, если одну расстановку можно привести к другой с помошью одного шахматного хода, иначе связи нет.Делим связи на "ход черных" и "ход белых".
Ok. Возможно лучше очередность хода привешивать к позиции, тогда получаем просто ориентированный граф. R3>Проставляем очередность связей, приняв за первые связи все те, которые выходят из расстановки "начало шахматной партии" и удовлетворяют условию "ход белых".
Не совсем ясно, что значит очередность связи? Во первых, в одну и ту же позицию можно придти разными путями. Во вторых, в разных партиях могут возникать одинаковые позиции, но в разном порядке. R3>В результате, если пройти по всем связям, с учетом очередности, чередуя условия "ход черных" и "ход белых" и начиная с расстановки "начало шахматной партии", то получим все возможные "партии".
Опять таки, причем здесь какая-то очередность? Нужно ходить только по ребрам графа. Кстати при этом мы можем зациклиться и придется вовлекать дополнительные правила (троекратное повторение позиции/ходы без "съедений" и ходов пешками)... Вот теперь действительно все партии. R3>Удаляем все следующие связи после связей, приводящие к концу игры, например, если при ходе одного цвета, королю другого цвета получается единственный ход — "под сруб" и он сам находится "под ударом". Трудновато придется с обработкой ничьи.
(уточнение) Связь можно удалить
1. если ее начало непосредственно в финальной позиции (кому-то мат)
2. если в ее начало можно попасть только через уже удаленные связи.
3. возможно образовавшиеся связные куски, в которые уже нельзя попасть из исходной позиции (с учетом того, что какие-то связи удалили) R3>Начиная с конца партий, проставляем приорет на связи для черных и белых по принципу: если связь приводит к концу игры, то на неё ставится приоритет, равный 1, далее +1, на каждую предыдущую. Если проставляем приоритет на связь, на которой уже есть приоритет, то приоритеты суммируются. Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности. R3>
настоящая проблема это сам алгоритм — под него нужно строить СУПЕР-ЭВМ, да-да именно все буквы большие, в которой для хранения этого графа будут задействованы все электроны вселенной,... представляешь себе такую?
Здравствуйте, Apostate, Вы писали:
A> это доработки, корректировка багов по мелочи...
A>настоящая проблема это сам алгоритм — под него нужно строить СУПЕР-ЭВМ, да-да именно все буквы большие, в которой для хранения этого графа будут задействованы все электроны вселенной,... представляешь себе такую?
Согласен, что электронов может и не хватить.
Но мне кажется, что есть проблемы с распутыванием партий с конца на уровне самой идеи.
Поэтому не будет смысла строить эту СУПЕР-ПУПЕР-ЭВМ
Не совсем точная цитата, может кто поправит.
Механитис --- болезнь ...(не помню кого), считающих, что любую проблему, даже если они не могут ее формализовать, можно будет решить, если заполучить достаточно мощную ЭВМ.
«Механитис – профессиональное заболевание тех, кто верит, что ответ математической задачи, которую он не может ни решить, ни даже сформулировать, легко будет найти, если получить доступ к достаточно дорогой вычислительной машине».
KA>Механитис --- болезнь ...(не помню кого), считающих, что любую проблему, даже если они не могут ее формализовать, можно будет решить, если заполучить достаточно мощную ЭВМ.
Программистов?
Заказчиков?
ЗЫ. А название точное?, а то больно термин хороший —
"Э, товарищ, да у вас механитис. Вам нужен покой, а ТЗ мы без вас составим, вы не беспокойтесь ".
R3>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>Спасибо за внимание.
Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать). А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, KonstantinA, Вы писали:
KA> Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности.
Согласно современным шахматным правилам, такого быть не может, ибо полная информация о шахматной позиции кроме расположения фигур включает еще признаки для каждого короля и ладьи, о том, двигались они или нет, а также признак возможности взятия на проходе для пешек и счетчик количества повторений этой позиции в партии.
Здравствуйте, fAX, Вы писали:
R3>>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>>Спасибо за внимание.
fAX>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
"Антагонистическая игра с полной информацией"
fAX>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Нет.
Бывают такие игры вообще без ничьей, например то же Го или Ним.
Здравствуйте, Les, Вы писали:
Les>Здравствуйте, fAX, Вы писали:
R3>>>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>>>Спасибо за внимание.
fAX>>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
Les>"Антагонистическая игра с полной информацией"
Я нашёл также перевод: "игрa с нулевой суммой", но Ваше определение мне нравится больше.
fAX>>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Les>Нет. Les>Бывают такие игры вообще без ничьей, например то же Го или Ним.
Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
Les>>Бывают такие игры вообще без ничьей, например то же Го или Ним. fAX>Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
Не простой вопрос. Обычно первый ход дает преимущество. В Го это решается за счет "коми" — платы в 5.5 очков которую платит первый игрок. В ниме же, победа при идеальной игре определяется начальными условиями, причем чаще победа достается первому.
Рассмотрим упрощенный вариант нима из "форта Байар" — кучка палочек, из которой игроки вытаскивают поочередно две или одну палочки по своему усмотрению, надо забрать последнюю. Выигрышная стратегия — оставлять после себя 3к палочек. Это можно сделать только если вы не получили эти самые 3к на входе. Если же 3к получает ваш противник, вам достаточно вытянуть 3 минус х, где х — количество вытянутых противником.
Если игру начинаете вы, то в зависимости от начального количества палочек, ваши шансы выиграть в идеальной игре приблизительно 2 к 1.
Здравствуйте, Les, Вы писали:
Les>>>Бывают такие игры вообще без ничьей, например то же Го или Ним. fAX>>Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
Les>Не простой вопрос. Обычно первый ход дает преимущество. В Го это решается за счет "коми" — платы в 5.5 очков которую платит первый игрок.
Извините, в го я не силён, только в рамках некогда взятого курса по AI . Но ведь заключение о преимуществе первого хода чисто математическое, и даже в изначально неравных условиях можно ввести дополнительные условия, которые нивелируют это преимущество, как Вы продемонстрировали на примере го.
А шахматы... Шахматы хорошая игра !!! Даже если докажут, что у белых или чёрных есть то самое преимущество, то вряд ли его найдут завтра (если, конечно, его ещё нет у автора темы ). Ну... или введут новое правило...
В ниме же, победа при идеальной игре определяется начальными условиями, причем чаще победа достается первому.
Les>Рассмотрим упрощенный вариант нима из "форта Байар" — кучка палочек, из которой игроки вытаскивают поочередно две или одну палочки по своему усмотрению, надо забрать последнюю. Выигрышная стратегия — оставлять после себя 3к палочек. Это можно сделать только если вы не получили эти самые 3к на входе. Если же 3к получает ваш противник, вам достаточно вытянуть 3 минус х, где х — количество вытянутых противником.
Les>Если игру начинаете вы, то в зависимости от начального количества палочек, ваши шансы выиграть в идеальной игре приблизительно 2 к 1.
Да, это так, но каким образом тогда Ним относится к "антагонистичным играм"?!
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
fAX>А шахматы... Шахматы хорошая игра !!! Даже если докажут, что у белых или чёрных есть то самое преимущество, то вряд ли его найдут завтра (если, конечно, его ещё нет у автора темы ). Ну... или введут новое правило...
Здравствуйте, KonstantinA, Вы писали:
R3>Создаем базу... R3>Проставляем очередность связей, приняв за первые связи все те, которые выходят из расстановки "начало шахматной партии" и удовлетворяют условию "ход белых". KA>Не совсем ясно, что значит очередность связи? Во первых, в одну и ту же позицию можно придти разными путями. Во вторых, в разных партиях могут возникать одинаковые позиции, но в разном порядке.
Вы сами и ответили на сой вопрос. По простому "очередность связи" == "очередность хода". Это надо для выбора в какую сторону, какими фигурами идти, в зависимости от того, в какую сторону, какими фигурами были предыдущие ходы. Напомню, что (теоретически) мы имеем все расстановки шахматных фигур на доске => ситуации "в одну и ту же позицию можно придти разными путями" будут обязательно.
R3>В результате, если пройти по всем связям, с учетом очередности, чередуя условия "ход черных" и "ход белых" и начиная с расстановки "начало шахматной партии", то получим все возможные "партии". KA>Опять таки, причем здесь какая-то очередность? Нужно ходить только по ребрам графа. Кстати при этом мы можем зациклиться и придется вовлекать дополнительные правила (троекратное повторение позиции/ходы без "съедений" и ходов пешками)... Вот теперь действительно все партии.
В этом нам связи и помогут, а именно, одно из указанных мной свойств связей — очередность. В конечном варианте, на связи придется вешать очень много свойств, например, как писал m.a.g., "признаки для каждого короля и ладьи, о том, двигались они или нет, а также признак возможности взятия на проходе для пешек и счетчик количества повторений этой позиции в партии"
R3>Удаляем... R3>Начиная с конца партий, проставляем приорет на связи для черных и белых... KA> Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности.
Представить можно, но накрутить до бесконечности, согласно текущим шахматным правилам, не представляется возможным. Ещё раз: у нас в связях заложена вся информация о том, какую именно часть, какого именно множества партий мы сыграли, а для дальнейшего хода видим все будущие разветвления партий. R3>
Здравствуйте, fAX, Вы писали:
fAX>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
"Игра с нулевой суммой и полной информацией".
fAX>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Из одного другое не следует.
1) Игры, в которых ничья не предусмотрена.
Пример: игра Баши (кажется, так?) — имеется кучка из K камней, за один ход можно взять любое количество от 1 до N. Выигрывает(проигрывает) тот, кто возьмет последний камень.
. Выигрывает первый.
При желании можно выдумать игру, в которой выиграет второй. Например, зафиксировать начальную позицию в шахматах, из которой "белые начинают и получают мат в 2 хода".
---
Примечание: игра Ним — это расширение игры Баши на несколько кучек (за один ход можно тащить из одной кучки).
Перекуём баги на фичи!
это доработки, корректировка багов по мелочи...
). Ну... или введут новое правило... 
