| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Шашки...
Vulko © (2003-04-11 17:08:00)
Люди, вот решил написать гаму "Шашки", но возник следующий вопрос:
как выбрать лучший ход, лучше в зависимости от выбранного уровня сложности?
nikkie (2003-04-15 18:22:00) [21]
>neuro
сегодня, извиняюсь, не могу. давай завтра, 16.04.2002 скажем, в 18:00 по Москве - можно и сдвинуть, если тебе удобней будет. мне больше всего нравится играть на http://www.playchess.com, но если тебе неохота ставить клиента, то можем сыграть на берегу http://www.bereg.ru/games/club/hall.shtml- там явовский клиент.
играем 4 партии с контролем 5 минут на партию, либо 5 минут плюс 2 секунды за ход. проигравший приносит побежденному публичное покаяние в этой ветке. :)
если что-то не устраивает, можно обсудить.
Mystic (2003-04-15 17:59:00) [22]> Нельзя их уменьшить неразбираясь в самой игре. В шахматах
> можно откидывать варианты, где жертвуется несколько фигур.
> В шашках можно пожертвовать все шашки, кроме последней,
> а последней съесть все шашки противника.
Правильно. Но тут есть один ньюанс. Если ты отдаешь две или больше шашек, а потом прекращается форсированный вариант (т. е. ты не вынуждаешь противника делать единственный ход, от силы два), то с большой вероятностью расчет можно прекратить.
В моей программе глубина перебора зависит от количества ходов. Там был такой алгоритм:
Рекурсивная функция оценки позиции
1. Буфер переполнен? Если да, то возвращаем оценку позиции по принципу у кого больше: простая 20, дамка 70. Плюс рандомное число от -10 до 10 (чтобы не повторяться).
2. Дописываем в буфер все возможные хода.
3. Если ходов нет, то возвращаем позиция проиграна (или выигрына, в зависимости от того, кто ходит)
4. Анализируем каждый ход по этой же процедуре.
5. Оценкой позиции будет ход с наименьшей (ходит противник) либо наибольшей (ходим мы) оценкой. (Минимакс).
6. Очищаем буфрер.
Преимущество такого подхода состоит в том, что в от количества ходов зависит глубина расчета. Для примера рассмотрим позицию
Белые: a3, b2, b4, c1, c3, d5, e1
Черный a5, дамка g1
Белые выигрывают.
1. b4-c5 (4) g1:b6 (2)
2. c3-d4 (5) b6:g1 (3)
3. d2-e3 (5) g1:d4:a1 (1)
4. a3-b4 (5) a5:c3 (1)
5. c1-b2 (4) c3-d2 ( 1)
> Нельзя их уменьшить неразбираясь в самой игре. В шахматах
> можно откидывать варианты, где жертвуется несколько фигур.
> В шашках можно пожертвовать все шашки, кроме последней,
> а последней съесть все шашки противника.
Правильно. Но тут есть один ньюанс. Если ты отдаешь две или больше шашек, а потом прекращается форсированный вариант (т. е. ты не вынуждаешь противника делать единственный ход, от силы два), то с большой вероятностью расчет можно прекратить.
В моей программе глубина перебора зависит от количества ходов. Там был такой алгоритм:
Рекурсивная функция оценки позиции
1. Буфер переполнен? Если да, то возвращаем оценку позиции по принципу у кого больше: простая 20, дамка 70. Плюс рандомное число от -10 до 10 (чтобы не повторяться).
2. Дописываем в буфер все возможные хода.
3. Если ходов нет, то возвращаем позиция проиграна (или выигрына, в зависимости от того, кто ходит)
4. Анализируем каждый ход по этой же процедуре.
5. Оценкой позиции будет ход с наименьшей (ходит противник) либо наибольшей (ходим мы) оценкой. (Минимакс).
6. Очищаем буфрер.
Преимущество такого подхода состоит в том, что в от количества ходов зависит глубина расчета. Для примера рассмотрим позицию
Белые: a3, b2, b4, c1, c3, d5, e1
Черный a5, дамка g1
Белые выигрывают.
1. b4-c5 (4) g1:b6 (2)
2. c3-d4 (5) b6:g1 (3)
3. d2-e3 (5) g1:d4:a1 (1)
4. a3-b4 (5) a5:c3 (1)
5. c1-b2 (4) c3-d2 (1)
6. e1:c3 (1) x
4 + 2 + 5 + 3 + 5 + 1 + 5 + 1 + 4 + 1 + 1 = 32
Таким образом, чтобы найти эту комбинацию, размер буфера должен превышать 32. Уровень 30 соответсвует самому слабому уровню игры, максимум соответсвует где-то 50-ти.
Недостатком этого алгоритма является то обстоятельство, что процесс вычисления хода строго детерминирован. Практически невозможно его адаптировать к игре на время. К тому же каждый новый ход обдумывается заново и не используется время, когда над ходом думает противник. Сейчас я робко подумываю на тему реализации такого движка, с хеш-таблицей на 4-16 Мб, ...
Сложностей с реализацией турецкого боя не возникало, задача скорее техническая.
Варианты с ИИ и нейросетями, имхо, бесперспективны.
>Кен ©
С вас набор шашечек. А если будет интерфейс, то совсем хорошо.
Повторю ссылку на алгоритм:
http://www.rsdn.ru/Forum/Message.aspx?mid=241401&only=1
neuro (2003-04-15 17:34:00) [23]
2nikkie: вообще пост был не конкретно тебе, но вызов твой я принимаю. =) Где и когда -- решать тебе.
По поводу позиции -- есть некоторые четкие критерии оценки -- базовые, вот их комп и знает, а остальное уже вариации на тему..
nikkie (2003-04-15 17:19:00) [24]
>neuro
>Видно вы все играть в шахматы не умеете =)
перчатка брошена. вызываю Вас, сэр, на дуэль (матч, то бишь), выбор оружия (кол-во партий и контроль времени - только так, чтобы за час, максимум два уложиться) за Вами. если Вы откажете в сатисфакции, то вы не джентельмен, сэр neuro.
>Arch-vile
>не только в шашки не умеешь играть, но и с шахматами проблемы...
будешь нарываться и тебя вызову.
господа, читайте пост внимательней, прежде чем накидываться. у меня не было слов про жертву ВСЕХ фигур.
>Кстати, к вопросу об оценке позиции -- ничего выдумывать не надо, она уже есть -- в любом классическом учебнике по шахматному делу =).
вот ля-ля не надо. оценка позиции - это самая сложная часть. если бы все было в книжке написано, то человек бы вообще ничего противопоставить не мог бы. а самые суперские шахматные программы до сих пор непонимают окончания с числом фигур более 5. и понятие "крепость" до них ну никак не доходит.
neuro (2003-04-15 17:00:00) [25]
Тогда извини, недопонял..Хотя есть возможность одним королем в пат уйти, поэтому все-таки нельзя недооценивать игру с жертвами. Вроде как если светит максимум пат, то на него и играть надо.
Кстати, к вопросу об оценке позиции -- ничего выдумывать не надо, она уже есть -- в любом классическом учебнике по шахматному делу =).
Arch-vile (2003-04-15 16:55:00) [26]
2neuro
Как раз об этом я и сказал :)
Ведь как шахматы выигрывают? Убивают короля, когда некуда смыться и нечем прикрыть :)
neuro (2003-04-15 16:52:00) [27]
Видно вы все играть в шахматы не умеете =)
Последняя фигура всегда король -- и им одним ну _никак_ мат поставить нельзя =)
Arch-vile (2003-04-15 16:44:00) [28]
> Нельзя в шахматах отбросить вариант с жертвой фигур по той же причине - последним ходом можно мат поставить.
Да? В смысле - а ты знаешь, что последнюю фигуру оччень легко просто УБИТЬ? Видно ты не только в шашки не умеешь играть, но и с шахматами проблемы...
nikkie (2003-04-15 15:42:00) [29]
>Кен
>Так может говорить только тот, кто никогда это не пробовал сделать и незнает всех ньюансов.
Уважаемый господин Кен хочет взять меня на слабо? Нет проблем. Напиши и опубликуй алгоритм перечисления перестановок чисел от 1 до N. Сделаешь - я напишу алгоритм перечисления ходов в шашках.
>Нельзя их уменьшить неразбираясь в самой игре. В шахматах можно откидывать варианты, где жертвуется несколько фигур. В шашках можно пожертвовать все шашки, кроме последней, а последней съесть все шашки противника.
Нельзя в шахматах отбросить вариант с жертвой фигур по той же причине - последним ходом можно мат поставить.
Чем бы спорить, лучше поискал бы описание минимакса и альфа-беты. Все это придумано в 70-х годах, стыдно 30 лет спустя рассуждать о переборных задачах, не зная и не желая узнать базовых алгоритмов.
Нету у нас такого исходника, чтобы корректно моделировал ходы
Никто не виноват, что тебе лень даже по ссылке сходить. Mystic опубликовал свой код.
Vulko (2003-04-15 14:51:00) [30]
> Хороший вопрос...
> Вот это и есть система оценки позиции.
> А как ты ее сконструируешь дело твое - программистское.
> Играй в игру - думай что в ней наиболее важно, читай теорию,
> создавай, экспериментируй. Наше дело было направить тебя,
Дык это и есть вопрос на который я хотел бы получить ответ (смотри первый пост)!!!!!
k-man (2003-04-15 12:32:00) [31]
2Кен
Честно говоря пллхо понимаю в чем сложность передвинуть на виртуальной доске шашку с одного поля на другое. Потом оценить получившуюся позицию и записать ход и его вес в структуру данных. Конечно - это будет сделано не за один день, но стоит поработать...
Кен (2003-04-15 02:30:00) [32]
nikkie ©
> правила игры - это уже алгоритм. вопрос как их запрограммировать
> - это вопрос реализации. согласен, что для шашек это будет
> сложнее, чем для шахмат. но написать рекурсивную процедуру
> за день можно.
Так может говорить только тот, кто никогда это не пробовал сделать и незнает всех ньюансов.
> мой пост собственно был на другую тему - существуют алгоритмы
> перебора вариантов, которые позволяют существенно уменьшить
> количество перебираемых вариантов. и эти алгоритмы одни
> и те же и для шахмат и для шашек.
Нельзя их уменьшить неразбираясь в самой игре. В шахматах можно откидывать варианты, где жертвуется несколько фигур. В шашках можно пожертвовать все шашки, кроме последней, а последней съесть все шашки противника.
> для шашек это, наверное, не очень актуально - слишком мало
> ходов
Зато рассчёты ведутся очень далеко. Часто до последней шашки.
В поддавках же вообще процентов 90 ходов обычно проигрышные. Но доказательство этого бывают слишком сложны.
k-man ©
> Предположим, у нас есть некая виртуальная доска на котрой
> мы в памяти моделируем ходы и пишем позиции.
Нету у нас такого исходника, чтобы корректно моделировал ходы и писал позиции после них. Нету. И пока его нету, говорить о том как эти ходы анализировать - рано.
k-man (2003-04-14 21:56:00) [33]
2Vulko
> А по каким параметрам тогда оценивать позицию?
Хороший вопрос...
Вот это и есть система оценки позиции.
А как ты ее сконструируешь дело твое - программистское.
Играй в игру - думай что в ней наиболее важно, читай теорию, создавай, экспериментируй. Наше дело было направить тебя,
а работу придется делать тебе.
nikkie (2003-04-14 16:52:00) [34]
>Дмитрий К.К.
>Нейросети приплетать необязательно
это точно. но я уверен - в шахматной программе алгоритм априорного выбора "разумных" ходов даст очень серьезный плюс. а нейросети это будут или что иное - я не знаю.
>Vulko
>прикол в том, что чем круче ИИ, тем быстрее он ходит
задача эта прежде всего расчетная. выбор хода без расчета - это из области мистики. такая программа хорошо играть не сможет. хотя для того же го ситуация возможно будет иная.
>all
в "потрепаться" Mystic выложил ссылку на свой код шашечной программы.
Vulko (2003-04-14 15:56:00) [35]
> Все алгоритмы уже давно написаны профи и принципы у них
> одинаковые. Сравни их исходники и поймешь, если разберешься
> :)
2GameBoy
Где бы их взять?
> Обыкновенная переборная задача.
2Дмитрий К.К.
прикол в том, что чем круче ИИ, тем быстрее он ходит, а на то чтобы перебрать все возможные ходы и комбинации уйдет много времени. Надо искать золотую середину.
> По разработанному тобой алгоритму оценивает каждую позицию
> и возвращает некое число в массив. В итоге у тебя должен
> получиться некий массив весов позиций
2k-man
А по каким параметрам тогда оценивать позицию?
Это очень похоже на мою идею, которая заключается в том, чтобы просчитать несколько ходов и посмотреть оставшееся кол-во шашек.
k-man (2003-04-14 15:53:00) [36]
2Дмитрий К.К.
мы гимеем ввиду что на основе нейросети можно построить ИИ целиком, а не только решить отдельно эту задачу.
Дмитрий К.К. (2003-04-14 14:08:00) [37]
Обыкновенная
переборнаязадача. Нейросети приплетать необязательно.
k-man (2003-04-14 13:59:00) [38]
2nikkie
> а для шахмат вопрос выбора "предположительно хороших" ходов
> очень важен. так что тут и нейронные сети могут пригодиться.
Вот об этом я здесь и разглагольствую...
k-man (2003-04-14 13:55:00) [39]
2Кен
Честно говоря плохо понял задачу...
Предположим, у нас есть некая виртуальная доска на котрой мы в памяти моделируем ходы и пишем позиции. Перемещаем шашку с одного места на другое, пишем позицию в некую структуру данных.
То есть делаем виртуальный ход - что-то пишем - возвращаем назад, делаем следующий ход... Но повторюсь у нас нет ресурсов что бы смотреть все позиции: нужен анализ что считать что нет.
...а у дамки просто больше возможностей хода.
nikkie (2003-04-14 13:28:00) [40]
>Кен
правила игры - это уже алгоритм. вопрос как их запрограммировать - это вопрос реализации. согласен, что для шашек это будет сложнее, чем для шахмат. но написать рекурсивную процедуру за день можно. если у Вас это вызывает проблемы, то вероятно стоит для начала учебные задачи по-писать. перестановки чисел 1..N перечислить, например.
мой пост собственно был на другую тему - существуют алгоритмы перебора вариантов, которые позволяют существенно уменьшить количество перебираемых вариантов. и эти алгоритмы одни и те же и для шахмат и для шашек.
на самом деле, тот же алгоритм альфа-бета отсечения будет давать разный эффект для разного порядка перебора ходов, возможных в конкретной позиции. для шашек это, наверное, не очень актуально - слишком мало ходов, а для шахмат вопрос выбора "предположительно хороших" ходов очень важен. так что тут и нейронные сети могут пригодиться.
| |
Страницы: 