Шашки & алгоритм

← →
Феликс (2003-04-13 18:41) [0]

Хочу сделать шашки, однако, возникла проблема. Дело в том, что непосредственно сам код дело хоть и непростое, но думаю выполнимое, но прежде чем переходить к коду, надо понять принцип, философию, идею, фишку, смысл игры (это я пытался указать на одну вещь используя разные слова, думаю вы поняли, что я имел ввиду). Иначе говоря, нужно сформулировать словами алгоритм этих самых шашек. Я не знаю, как это точно должно выглядеть (знал бы сам сделал :), но видмо примерно так:
1.Просматриваем все возможные ходы моделируя каждый ход при этом смотря, может ли срубить противник мою шашку.
2. Среди тех ходов, которые возможны (т.е ход при котором шашку не срубят) выбираем лучший (и тут вот первый косяк, т.к не известно по какому принципу выбрать этот самый ход)
.....
и.т.д

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

← →
Феликс (2003-04-13 18:47) [1]

>В любом случае если выскажитесь по этой теме.

Пардон! Хотел сказать в любом случае буду благодарен если выскажитесь по этой теме.

← →
Giemgo (2003-04-13 18:56) [2]

1) тут есть конференция Игры

2) По теме логики игр написано немало материала. Зайти в любую поисковую систему

3) База - это присваивания каждому ходу очкнов.

То есть, просматриваются ходы на n вперед (от этого зависит сколько будет "думать" компьютер и уровень игры). И каждому ходу на основании его результата и возможного результата в дальнейшем присваивается определенное количество баллов.

Допустим, максимум - это 100 балов. Думаю, ты неправ говоря, что 100 балов - это ход, где твою шашку не едят. 100 балов - это ход, когда ты выигрываешь. Балов 90, допустим, это ход, когда твоя шашка становится дамкой (что наверное важнее того, съедят ли у тебя при этом другую шашку или нет).
И самое грамотное - это учитывать как можно больше факторов: продвижение в дамки, потеря шашки, потеря шашки на следующий ход, занятие выгодной позиции (?) и т.д. и т.д.
И, конечно, нужно присвоить каждому последствию свой бал, чтобы этот бал как можно лучше подходил. Ну а дальше тестирование,тестирование и еще раз тестирование

← →
uw (2003-04-13 18:59) [3]

http://www.yandex.ru/yandsearch?text=%F8%E0%F8%EA%E8+%EA%F0%E8%F2%E5%F0%E8%E9

← →
k-man (2003-04-13 19:00) [4]

Добро пожаловать на конференцию Игры.
Там такая же ветка есть. Обсуждается то что преподнес Giemgo
только подробнее.

← →
Феликс (2003-04-13 19:16) [5]

Ну, игры, так игры. Все равно спасибо :)

← →
Satirus (2003-04-13 20:45) [6]

А вообще, лучше запрограммируй игру Го.
По крайней мере, за лучший вариант предлагають лимон баксов.

← →
k-man (2003-04-13 20:46) [7]

А где предлагают?

← →
Дмитрий К.К. (2003-04-14 07:41) [8]

И не зря причем предлагают. Эта игрушка посложнее шахмат будет из-за огромного кол-ва возможных ходов из той или иной позиции.

← →
Mystic (2003-04-14 11:42) [9]

http://www.listsoft.ru/program.php?id=13904&allowunchecked=yes
--- вот шашечная программа, менее-более (~I разряд) приличного уровня, которая была написана за две недели. А вот эксперименты с алгоритмом для игры в шахматы оказались неудачны. Надо потратить гораздо больше времени.

Тот алгоритм потерпел неудачу --- он был убит за покушение на его автора. В принципе в мае прошлого года я его восстановил. Когда-то думал оформить как ShareWare...

Вот только непонятно, что ты хочешь. Ты в шашки играешь на каком уровне? Какая философия нужна?

← →
Satirus (2003-04-14 13:11) [10]

>А где предлагают?
http://www.reiss.demon.co.uk/misc/mick.htm

← →
Mystic (2003-04-14 13:42) [11]

http://www.rsdn.ru/Forum/Message.aspx?mid=241401&only=1

← →
Феликс (2003-04-14 21:01) [12]

Вот душевная ссылка! http://home.uic.tula.ru/~kv200874/rus/algo.htm
Как раз то, что я искал!

← →
Mystic (2003-04-14 23:24) [13]

> Феликс © (14.04.03 21:01)

Кстати, стравил я своб программу (уровень Максимум) с этой (уровень опытный). Думали программы над ходами примерно одинаково (~1-3 сек). в итоге верх одержала все-таки моя

Моя 1001 1==1 5 Та 0110 0==0 3

(Первые четыре моя играла черными, потом четыре белыми). Насколько я понял, моя считала быстрее и дальше, но позиционная оценка лучше у той программы (поскольку моя обходится без таковой).

← →
nikkie (2003-04-15 01:29) [14]

>Mystic
а ты возьми позиционную оценку из той программы - она вроде в хелпе описана, а весовые коэффициенты полей - в настройках открытым текстом. интересно будет узнать - лучше ли стала играть твоя программа :)

кстати, аргумент защитникам того, что и на дельфи можно писать хорошие программы - программа написана на билдере :). впечатление от нее достаточно приятное. вот только spy++ показывает, что формы называются Form1, Form4, Form10. не хорошо как-то...

← →
Феликс (2003-04-15 01:44) [15]

2 Mystic
>в итоге верх одержала все-таки моя

Ну, не зря же у вас модная, голубенькая (с) :)

← →
Феликс (2003-04-15 01:51) [16]

Интересно! А как переиграть компьютер? Что может противопоставить человек компьютеру, который собака может мало того, что построить кучу возможных продолжений, так и с математической точностью высчитать лучший ход?

← →
Дмитрий К.К. (2003-04-15 06:55) [17]

> Феликс © (15.04.03 01:51)
> Интересно! А как переиграть компьютер? Что может противопоставить человек компьютеру

Более бредового вопроса не встречал. Ты сравниваешь человека с компьютером??? Компьютер ПЕРЕБИРАЕТ все варианты (пользуясь минимаксом, методом альфа-бета отсечения и проч.), а человек смотрит всего лишь 2-3 хода (которые отбирает сразу, а все остальное отсеивает СРАЗУ)

← →
Mystic (2003-04-15 10:54) [18]

> Ну, не зря же у вас модная, голубенькая (с) :)

Это был первый матч. Во втором моя убедительно влетела :)

> лишь 2-3 хода

2-3 хода мало будет :) На самом деле человек превосходит компьютер в оценке позиции и выборе плана игры.

> nikkie © (15.04.03 01:29)

Я думал над подобными вещами, но исходники той программы безвозвратно погибли, логику я восстановил, а интерфейс писать не сильно охота. К тому же если пойти чужим путем, то что-либо новое придумать будет очеь трудно --- нужна "своя колея". Нет ничего хуже, чем ограничиться рамками чужих мыслей.

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

← →
Дмитрий К.К. (2003-04-15 11:16) [19]

> Mystic © (15.04.03 10:54)
> 2-3 хода мало будет :) На самом деле человек превосходит
> компьютер в оценке позиции и выборе плана игры.

2-3 хода из той или иной позиции (потом дерево вариантов растет, конечно). А эти 2-3 хода он (хороший шахматист) отбирает именно на основе грамотной оценки позиции.

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

← →
Mystic (2003-04-15 13:23) [20]

Все равно 2-3 хода мало. Обычно я смотрю 5-6 ходов-кандидатов, исключая конечно случаи остро-тактических осложнений.

← →
Дмитрий К.К. (2003-04-15 13:32) [21]

И как далеко ты тогда смотришь?
Если на три хода вперед, то шесть в шестой степени = 46656 ходов?

:)))))

← →
Mystic (2003-04-15 13:43) [22]

Я хотел сказать, что обычно на первый ход претендуют 5-6 кандидатов. Как я их просматриваю --- сказать не могу. Думаю, что при выборе продолжения я мысленно выполняю порядка 1000 ходов (с учетом сохраненной информации на прошлых ходах). Короче дело темное...

← →
nikkie (2003-04-15 14:52) [23]

>Дмитрий К.К.
зря ерничаешь, все зависит от того, что понимать под "смотреть ход" :)

у меня сын (7 лет) сейчас решает задачки-одноходовки с диска "Шахматная тактика для начинающих". когда он сразу не находит решения - начинает перебирать все возможные шахи, а их обычно штук 6 бывает. если учесть, что еще, чтобы найти шахи он перебирает и другие ходы, то можно сказать, что он рассматривает штук 10 ходов, а то и больше. :)

мораль - дерево расчета реально построить глубоко, "рассматривая" 5-6 и даже более кандидатов в каждой позиции. только основная масса будет отсеиваться на глубине +1 полуход. а на большую глубину уходят только 2-3 варианта, тут я с тобой согласен.

но это наш с тобой уровень (благо я знаю твой, а ты знаешь мой :)), за гроссов я боюсь говорить. да и сам я так давно не играл ничего, кроме блица, что не могу сказать, как выглядит расчет в серьезной партии. про блиц точно могу сказать - чаще всего расчет минимален - проверка не зеваю ли простейших тактических ударов и выбор хода из общих соображений.

но что-то мы в оффтоп ушли. тема-то про шашки. а вот в них я ничего не понимаю (даже треугольник Петрова не знаю, но это мелочь...). пересчитать программу я не могу и не смогу, нечего и пытаться. это программка делает меня на уровне "младенец".

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

интересно было бы почитать какой учебник по шашкам, если кто знает ссылку в он-лайн, дайте плиз.

← →
Mystic (2003-04-15 15:10) [24]

Ну... 25 уроков шашечной игры, Хацкевич... Но online я не встечал ни шахматной, ни шашечной литературы :)

Основные соображения:

1. Центр. Централизация --- хорошо. Так шашка на c5 может дерржать сразу две шашки на a5 и a7. Но центр хорош, когда в распоряжении игрока имеются "запасные" хода. Бывает переразвитый центр, когда позицияя хорошая, но но ходить вперед... Соотетсвенно бывают планы, связанные с окружением центра.

2. Шашки должны быть более-менее монолитно расположены.
Если шгашки разнесены по флангам, это плохо.

3. Наличие поударных диагоналей позволяет создавать угрозы.

4. Желательно развивать шашки a1 и h2.

5. Шашка на e1 считается "золотой". Выводить ее не желательно, так как это создает доп. комбинационные угрозы.

6. Поле с5 - кол. Обладание этим полем выгодно.

7. В эндшпиле желательно занять поле f4.

8. В эндшпиле желательно знать несколько ключевых позиций, которые часто возникают в процессе игры. Они служат ориентирами.

Ну и более-менее приличная программа
http://www.listsoft.ru/?id=2066

← →
Феликс (2003-04-15 21:37) [25]

Дмитрий К.К. © (15.04.03 06:55)

>Более бредового вопроса не встречал. Ты сравниваешь человека с компьютером???

Ты сморти! А я более тупового и пустого ответа не видал! Смысл послания заключался в том, что компьютер куда круче человека. Тогда как Каспаров выигрывал у дип блю? Зря вы Дмитрий во взрослые разговоры лезите.

Вот для вас ссылка:
http://dishey.com

← →
Дмитрий К.К. (2003-04-16 06:17) [26]

Шашки & алгоритм Найти похожие ветки