- PVSM.RU - https://www.pvsm.ru -
Думаю, ни для кого не секрет, что "Дурак" (далее это слово будет написано с маленькой буквы и без кавычек) — это самая популярная карточная игра в России и странах бывшего СССР (хотя и почти неизвестная за его пределами). Несмотря на свое название и довольно несложные правила, выигрыш в ней все-таки зависит больше от мастерства игрока, чем от случайного расклада карт (в английской терминологии игры того и другого типов называются соответственно game of skill [1] и game of chance [2]. Так вот — дурак в большей степени game of skill).
Целью статьи является написание простого ИИ для игры. Под словом "простого" подразумевается следующее:
(Строго говоря, первый пункт уже не дает права такому ИИ называться искусственным интеллектом per se, а лишь псевдо-ИИ. Но такая терминология в разработке игр устоялась, поэтому ее мы менять не будем.)
Правила игры, думаю, известны всем, поэтому лишний раз их напоминать не буду. Тем, кто хочет свериться, советую обратиться в Википедию [3], там довольно хорошая статья на эту тему.
Итак, начнем. Очевидно, что в дураке чем старше карта, тем выгоднее иметь ее в руке. Поэтому, построим алгоритм на классической оценке силы руки и принятии решения (например, о подкидывании той или иной карты) на основе этой оценки. Припишем картам значения, например так:
(Используем числа, кратные 100 для того, чтобы избавиться в расчетах от floating-point и оперировать только целыми числами. Для чего нужны отрицательные оценки, увидим ниже в статье.)
Козырные карты ценнее любых простых (даже козырная двойка бьет "обычного" туза), а иерархия в козырной масти та же самая, поэтому для их оценки просто добавим 1300 к "базовой" величине — тогда, например, козырная двойка будет "стоить" -600+1300=700 очков (то есть, как раз чуть больше, чем некозырной туз).
В коде (все примеры кода в статье будут на Kotlin) это выглядит примерно так (функция relativaCardValue()
возвращает ту самую оценку, а RANK_MULTIPLIER
— это как раз коэффициент, равный 100):
for (c in hand) {
val r = c.rank
val s = c.suit
res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt()
if (s === trumpSuit)
res += 13 * RANK_MULTIPLIER
// еще не все, продолжение чуть ниже
}
Увы, это еще не все. Важно также учесть следующие правила оценки:
$$display$$clubsuit 2 spadesuit 2 diamondsuit Q heartsuit Q clubsuit Q spadesuit Q$$display$$ практически идеальна (конечно, если соперник не пойдет под вас королями или тузами): вы отобьетесь дамами, после чего повесите сопернику погоны вручите ему пару двоек.
а вот много карт одной (конечно же, некозырной) масти, наоборот, иметь невыгодно — они будут "мешать" друг другу. Например, рука
$$display$$spadesuit 5 spadesuit J spadesuit A diamondsuit 6 diamondsuit 9 diamondsuit K$$display$$ очень неудачна — даже если соперник не "выбьет" у вас первым ходом козыря и пойдет картой пиковой масти, то все прочие подкинутые карты будут других мастей, и на них придется отдавать козыри. Кроме того, с большой вероятностью останется невостребованной пятерка пик — все козыри у вас достоинством выше пятерки, поэтому ни при каких обстоятельствах (если, конечно же, изначально не зашли картой младше) вам не удастся покрыть ею какую-нибудь другую карту — вероятность взять очень высока. С другой стороны, заменим валета пик десяткой треф, а козырную шестерку — тройкой:
$$display$$spadesuit 5 clubsuit 10 spadesuit A diamondsuit 3 diamondsuit 9 diamondsuit K$$display$$ Несмотря на то, что мы заменили карты на более младшие, такая рука значительно лучше — во-первых, на трефовую масть не придется отдавать козыря (и можно будет с большей вероятностью использовать пикового туза), а во-вторых, если вы побьете какую-то карту вашей козырной тройкой, есть вероятность того, что кто-то кинет вам тройку пик (ибо особого смысла держать такую карту, как правило, нет), и вы "отоваритесь" пятеркой.
Для реализации этих стратегий модифицируем наш алгоритм: Здесь мы считаем количество карт каждой масти и достоинства...
/* бонусные коэффициенты в зависимости от количества карт одного достоинства - например, если нет ни оной карты какого-то достоинства или она только одна, бонусы не начисляются, а за все 4 карты коэффициент равен 1.25 */
val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25)
var res = 0
val countsByRank = IntArray(13)
val countsBySuit = IntArray(4)
for (c in hand) {
val r = c.rank
val s = c.suit
res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt()
if (s === trumpSuit)
res += 13 * RANK_MULTIPLIER
countsByRank[r.value - 1]++
countsBySuit[s.value]++
}
… здесь добавляем бонусы за них (вызов Math.max
нужен для того, чтобы не начислять отрицательные бонусы за младшие карты — потому что в данном случае это тоже выгодно)...
for (i in 1..13) {
res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt()
}
… а тут, наоборот, штрафуем за несбалансированную по мастям руку (значение UNBALANCED_HAND_PENALTY
опытным путем установлено как 200):
// считаем среднее количество карт некозырных мастей...
var avgSuit = 0.0
for (c in hand) {
if (c.suit !== trumpSuit)
avgSuit++
}
avgSuit /= 3.0
for (s in Suit.values()) {
if (s !== trumpSuit) {
// и вычитаем штрафы в зависимости от отклонения от этого среднего по каждой масти
val dev = Math.abs((countsBySuit[s.value] - avgSuit) / avgSuit)
res -= (UNBALANCED_HAND_PENALTY * dev).toInt()
}
}
Наконец, учтем еще такую банальную вещь, как количество карт в руке. В самом деле, иметь в начале игры 12 хороших карт очень даже неплохо (тем более, что кинуть все равно смогут не больше 6), а вот в конце игры, когда помимо вас остался только соперник с 2 картами, это совсем не так.
// считаем количество оставшихся в игре карт (в колоде и на руках у игроков)
var cardsInPlay = cardsRemaining
for (p in playerHands)
cardsInPlay += p
cardsInPlay -= hand.size
// вычисляем, какая доля из них у игрока, и определяем величину штрафа (здесь MANY_CARDS_PENALTY = 600)
val cardRatio = if (cardsInPlay != 0) (hand.size / cardsInPlay).toDouble() else 10.0
res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt()
return res
Резюмируем — в полном виде функция оценки выглядит так:
private fun handValue(hand: ArrayList<Card>, trumpSuit: Suit, cardsRemaining: Int, playerHands: Array<Int>): Int {
if (cardsRemaining == 0 && hand.size == 0) {
return OUT_OF_PLAY
}
val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25) // for cards of same rank
var res = 0
val countsByRank = IntArray(13)
val countsBySuit = IntArray(4)
for (c in hand) {
val r = c.rank
val s = c.suit
res += ((relativeCardValue(r.value)) * RANK_MULTIPLIER).toInt()
if (s === trumpSuit)
res += 13 * RANK_MULTIPLIER
countsByRank[r.value - 1]++
countsBySuit[s.value]++
}
for (i in 1..13) {
res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt()
}
var avgSuit = 0.0
for (c in hand) {
if (c.suit !== trumpSuit)
avgSuit++
}
avgSuit /= 3.0
for (s in Suit.values()) {
if (s !== trumpSuit) {
val dev = Math.abs((countsBySuit[s.value] - avgSuit) / avgSuit)
res -= (UNBALANCED_HAND_PENALTY * dev).toInt()
}
}
var cardsInPlay = cardsRemaining
for (p in playerHands)
cardsInPlay += p
cardsInPlay -= hand.size
val cardRatio = if (cardsInPlay != 0) (hand.size / cardsInPlay).toDouble() else 10.0
res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt()
return res
}
Итак, у нас готова функция оценки. В следующей части планируется описать более интересную задачу — принятие решений на основе такой оценки.
Всем спасибо за внимание!
P.S. Данный код является частью разрабатываемого автором в свое свободное время приложения. Оно доступно на GitHub [4] (бинарные релизы для Desktop и Android, для последней приложение доступно и на F-Droid [5]).
Автор: trolley813
Источник [6]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/kotlin/306396
Ссылки в тексте:
[1] game of skill: https://en.wikipedia.org/wiki/Game_of_skill
[2] game of chance: https://en.wikipedia.org/wiki/Game_of_chance
[3] в Википедию: https://ru.wikipedia.org/wiki/%D0%94%D1%83%D1%80%D0%B0%D0%BA_(%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0)
[4] на GitHub: https://github.com/hyst329/OpenFool
[5] на F-Droid: https://f-droid.org/en/packages/ru.hyst329.openfool/
[6] Источник: https://habr.com/ru/post/437346/?utm_campaign=437346
Нажмите здесь для печати.