Думаю, ни для кого не секрет, что "Дурак" (далее это слово будет написано с маленькой буквы и без кавычек) — это самая популярная карточная игра в России и странах бывшего СССР (хотя и почти неизвестная за его пределами). Несмотря на свое название и довольно несложные правила, выигрыш в ней все-таки зависит больше от мастерства игрока, чем от случайного расклада карт (в английской терминологии игры того и другого типов называются соответственно game of skill и game of chance. Так вот — дурак в большей степени game of skill).
Целью статьи является написание простого ИИ для игры. Под словом "простого" подразумевается следующее:
- интуитивно понятный алгоритм принятия решений (то есть, как следствие, никакого машинного обучения, в котором этот алгоритм скрыт глубоко "под капотом");
- отсутствие состояния (то есть, алгоритм руководствуется только данными на текущий момент времени, проще говоря, ничего не запоминает (например, не "считает" вышедшие из игры карты).
(Строго говоря, первый пункт уже не дает права такому ИИ называться искусственным интеллектом per se, а лишь псевдо-ИИ. Но такая терминология в разработке игр устоялась, поэтому ее мы менять не будем.)
Правила игры, думаю, известны всем, поэтому лишний раз их напоминать не буду. Тем, кто хочет свериться, советую обратиться в Википедию, там довольно хорошая статья на эту тему.
Итак, начнем. Очевидно, что в дураке чем старше карта, тем выгоднее иметь ее в руке. Поэтому, построим алгоритм на классической оценке силы руки и принятии решения (например, о подкидывании той или иной карты) на основе этой оценки. Припишем картам значения, например так:
- туз (A) — +600 очков,
- король (K) — +500,
- дама (Q) — +400,
- валет (J) — +300,
- десятка (10) — +200,
- девятка (9) — +100,
- восьмерка (8) — 0,
- семерка (7) — -100,
- шестерка (6) — -200,
- пятерка (5) — -300,
- четверка (4) — -400,
- тройка (3) — -500,
- и наконец, двойка (2) — -600 очков.
(Используем числа, кратные 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 (бинарные релизы для Desktop и Android, для последней приложение доступно и на F-Droid).
Автор: trolley813
