A game (not) for fools. Writing AI for the Fool (Part 1)

I think it is no secret to anyone that “Fool” (hereinafter this word will be written in small letters and without quotes) is the most popular card game in Russia and the countries of the former USSR (although almost unknown beyond its borders). Despite its name and fairly simple rules, the gain in it still depends more on the player’s skill than on the random distribution of cards (in English terminology, games of this and other types are called game of skill and game of chance, respectively . So - fool in more game of skill ).


The purpose of the article is to write a simple AI for the game. The word "simple" means the following:


  • an intuitive decision-making algorithm (that is, as a result, no machine learning in which this algorithm is hidden deep "under the hood");
  • lack of state (that is, the algorithm is guided only by data for the current time, in other words, it does not remember anything (for example, it does not “count” the cards that have left the game).

(Strictly speaking, the first paragraph no longer gives the right to such an AI to be called artificial intelligence per se , but only a pseudo-AI. But such terminology in game development is well-established, therefore we will not change it.)


I think the rules of the game are known to everyone, so I’ll not remind them once again. For those who want to check, I advise you to contact Wikipedia , there is a pretty good article on this topic.


So, let's begin. Obviously, the more foolish a card is, the more profitable it is to have it in your hand. Therefore, we will build an algorithm on the classical assessment of the strength of the hand and making a decision (for example, about throwing a particular card) on the basis of this assessment. We assign cards value, for example:


  • ace (A) - +600 points,
  • King (K) - +500,
  • lady (Q) - +400,
  • Jack (J) - +300,
  • ten (10) - 200,
  • nine (9) - +100,
  • eight (8) - 0,
  • seven (7) - -100,
  • six (6) - -200,
  • the five (5) - -300,
  • four (4) - -400,
  • three (3) - -500,
  • and finally, two (2) - -600 points.

(We use numbers that are multiples of 100 in order to get rid of floating-point in calculations and operate only with whole numbers. For what we need negative estimates, see later in the article.)


The trump cards are more valuable than any simple ones (even the trump deuce beats the "usual" ace), and the hierarchy in the trump suit is the same, so for their evaluation we simply add 1300 to the "base" value - then, for example, the trump deuce will "cost" -600 + 1300 = 700 points (that is, just a little more than an unprofitable ace).


In the code (all the code examples in the article will be on Kotlin), it looks like this (the function relativaCardValue()returns that same estimate, but RANK_MULTIPLIERthis is just a coefficient equal to 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
    // еще не все, продолжение чуть ниже
}

Alas, that's not all. It is also important to consider the following evaluation rules:


  • it is advantageous to have many cards of the same value - not only because they can “overwhelm” an opponent, but also to easily repel the attack (especially if cards of high value). For example, at the end of the game, the hand (for simplicity, we suppose that here and below trumps are diamonds)

    $$ display $$ \ clubsuit 2 \ spadesuit 2 \ diamondsuit Q \ heartsuit Q \ clubsuit Q \ spadesuit Q $$ display $$ almost perfect (of course, if the opponent does not go under you kings or aces): you will be beaten off by the ladies, after which hang rival shoulder straps hand him a pair of twos.


    but many cards of the same (of course, non-transparent) suit, on the contrary, are not profitable - they will “interfere” with each other. For example, arm

    $$ display $$ \ spadesuit 5 \ spadesuit J \ spadesuit A \ diamondsuit 6 \ diamondsuit 9 \ diamondsuit K $$ display $$very unsuccessful - even if the opponent does not “knock out” your trump card with the first move and goes with the card of the peak suit, then all other cards thrown up will be of other suits, and you will have to give trumps to them. In addition, it is very likely that the top five will remain unclaimed - all the trump cards you have are worth above five, so under no circumstances (unless, of course, you initially went to the card under) you will not be able to cover it with any other card - the probability of taking a very is high. On the other hand, we replace the jack with a ten of clubs, and the trump six with a triple:

    $$ display $$ \ spadesuit 5 \ clubsuit 10 \ spadesuit A \ diamondsuit 3 \ diamondsuit 9 \ diamondsuit K $$ display $$ Despite the fact that we replaced the cards with the younger ones, such a hand is much better - firstly, the treasure will not have to give away a trump card (and you can be more likely to use the peak ace), and secondly, if you beat then the card is your trump card, there is a possibility that someone will throw a peak at you (for there’s usually no point in holding such a card), and you will get the five of them.



    To implement these strategies, we modify our algorithm: Here we count the number of cards of each suit and value ...


    /* бонусные коэффициенты в зависимости от количества карт одного достоинства - например, если нет ни оной карты какого-то достоинства или она только одна, бонусы не начисляются, а за все 4 карты коэффициент равен 1.25  */val bonuses = doubleArrayOf(0.0, 0.0, 0.5, 0.75, 1.25)
var res = 0val 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]++
}

    ... here we add bonuses for them (the call is Math.maxneeded in order not to charge negative bonuses for junior cards - because in this case it is also profitable) ...


    for (i in1..13) {
    res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt()
}

    ... and here, on the contrary, we are fined for an unbalanced hand (the value is UNBALANCED_HAND_PENALTYempirically set to 200):


    // считаем среднее количество карт некозырных мастей...var avgSuit = 0.0for (c in hand) {
    if (c.suit !== trumpSuit)
        avgSuit++
}
avgSuit /= 3.0for (s in Suit.values()) {
    if (s !== trumpSuit) {
        // и вычитаем штрафы в зависимости от отклонения от этого среднего по каждой мастиval dev = Math.abs((countsBySuit[s.value] - avgSuit) / avgSuit)
        res -= (UNBALANCED_HAND_PENALTY * dev).toInt()
    }
}

    Finally, let us take into account such a banal thing as the number of cards in your hand. In fact, it’s very good to have 12 good cards at the beginning of the game (especially since you can still throw no more than 6), but at the end of the game, when there’s only a 2-card opponent left behind you, it’s not like that.


    // считаем количество оставшихся в игре карт (в колоде и на руках у игроков)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() else10.0
res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt()
return res

    We summarize - in full, the evaluation function looks like this:


    privatefunhandValue(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 rankvar res = 0val 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 in1..13) {
        res += (Math.max(relativeCardValue(i), 1.0) * bonuses[countsByRank[i - 1]]).toInt()
    }
    var avgSuit = 0.0for (c in hand) {
        if (c.suit !== trumpSuit)
        avgSuit++
    }
    avgSuit /= 3.0for (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() else10.0
    res += ((0.25 - cardRatio) * MANY_CARDS_PENALTY).toInt()
    return res
}

    So, we have the evaluation function ready. In the next part, it is planned to describe a more interesting problem - making decisions based on such an assessment.


    Thank you all for your attention!


    PS This code is part of an application developed by the author in his free time. It is available on GitHub (binary releases for Desktop and Android, the latest application is also available on F-Droid ).

Tags:

Also popular now: