AI for "Fool"

If I knew a pack, I would live in Sochi.

Popular wisdom.

Under the player - with semak, under the whistler - with the goat.
')
Another popular wisdom.

It seems that in this post everything is mixed up. " Fool " in the title, the preference sayings in the epigraph and the KDPV , which has nothing to do with either. However, the very concept of " joker ", to the subject of today's conversation, the relationship is the most direct.

About a month ago, ComradMax published an article about its debut game for Android (the article, by the way, is also a debut one). The theme touched pleasantly struck me with an abundance of options for the well-known game . About some I knew, others were a revelation to me. The idea itself - to turn the card game into a kind of RPG took me for real. Unfortunately, the AI ​​implementation proved to be not the best way. Even though I have not played Fool since the age of five, I easily beat the program. Some of her moves are just stupid (I hope that the author will not be offended at me).

This discrepancy between the power of the idea and the very weak “intelligence” of the implementation made me think about how the AI ​​of this game should work. I must say that this problem is much more complicated than it seems at first glance. Card games (and “Fool” including) belong to the category of games with incomplete information. Algorithms used in chess or Go programs are not suitable for them. In any case, in its original form.

Data collection

The key to victory is intelligence! And the basis of intelligence is a thorough analysis of completely open data. What do we know about enemy cards when we play Fool? It would seem a little, because the cards are closed from us? In fact, everything is not so bad. For example, we know what cards we have in our hands and the face value of the card that shows the trump card (if the game is played with a trump card). This in itself is not bad, but our knowledge that the opponent does not have these cards is even better (this is in the case when the game is played with the same deck). Let's try to compile a complete list of sources of information about the cards of opponents, with reference to the "Fool":

1. Open cards (I already spoke about this)
2. Cards taken by players as the game progresses (including those they tried to fight off unsuccessfully)
3. Cards out of the game, as a result of rebound (this source is less obvious than the previous ones)
4. Cards that could not be beat (this is even less obvious and I will tell about it below)

Although everything is clear with the second point, I want to emphasize that we must take into account any cards we know that the enemy takes. For example, in the modification of the game " Magic ", if we walk with a black joker (the picture is still there), then we give our opponent two cards. After that, we know for sure that he has these cards, until he gets rid of them in any way (we find out about it). Perhaps this is not obvious, but this can happen at the moment when he, in turn, comes off with a black joker. What to do, in this case, it will be clear from the further narrative.

Starting from the third digit, everything becomes a bit more complicated. In general, it is clear that AI must take into account the cards that have left the game, the question is how to implement it technically. To represent the cards in the hands of opponents, you can use two types of objects. The first is a card with exactly known face value (suit + value), the second is a joker, which, in the worst case (that is, at the beginning of the game), can be almost anything. As the players make their moves, we get more and more information about the outgoing cards. By deleting these values ​​from the “joker” (with such a presentation of the data, it is one for all unknown cards), we clarify our knowledge of the closed cards. When the deck is completely disassembled, we know all the cards (we don’t know which ones), and when there are two players left, we just know all the cards of the opponent!

The fourth source is even more ephemeral. Suppose we go under the enemy, and he takes a card, without even trying to beat her. What does this give us? Most likely nothing (maybe he just saves cards for his turn), but you can take note that he takes this suit and, most likely, if you go the same suit, but with a face value higher (there is no reason to walk below, for obvious reasons) then he will take it too (or finally he will take up the trump cards). This means that for “jokers”, in his hands, you can make a note that they are not higher than the nominal, the card of which we went (taking into account the seniority of the trumps). If we make a mistake, it's never too late to remove the mark.

Of course, so that life does not seem at all to us honey, a variety of rules were invented, complicating the collection of information. In the " Poker " fool, the player, before rebound, has the right to change any of his two cards to cards from the deck. In fact, this means that we will have to completely reset the information about exactly known player cards. After such an exchange, all his cards turn into "jokers". An exception can be made, perhaps, for high cards in suits and trumps (hardly anyone in a sober mind will change them).

In the fool " With the buy-in " (there is a buy-in in the "Fool", did not lie to the epigraph), each player, at the beginning of the game, is dealt several closed cards. The player takes these cards when the cards in the deck and on the hands are completely finished, after which, they play the game with them. This is a much more benign option. In fact, in the final stage of the game, it almost does not change anything in our knowledge of the scenario, but only obliges us to end the game with completely random cards. If the cards fail, AI can hardly help.

Also, the " Secret " fool is focused on the unexpected finale. Under the trump card placed a closed card. When a trump card (after parsing a deck) is picked up by one of the players, this card opens and shows a new trump card. At this moment, everything that was acquired by overwork, during the game (including the coveted trump card at the bottom of the deck) may well turn into dust. In this game, randomness can also outweigh the AI’s intelligence (unless using the strategy of playing the Seeked Fool, with a set of high cards in all suits).

Perhaps the toughest option for AI - " Chukchi ". Immediately after the distribution and opening of the trump card, the deck (along with the open trump card) is removed from the game. The game is very transient and occurs, practically, "in the dark." AI has nowhere to turn.

In all the important measure

Well, we have collected the data and, to some extent, know what cards are in the hands of the enemy. We can calculate the probability that the enemy can successfully fight off our approach (this does not mean that he will do it), but this is not enough! We still cannot “take and just use” a minimax algorithm with alpha-beta clipping . A quantitative assessment of the position is required. As you already guess, in different "fools" it will be different.

In order to understand how good the cards on hand are, we can, for each of them, determine the number of cards (in the game) that can beat it (this is not the only possible approach, but it seems to me the most promising). The easiest is with the " Muteless " option. We build cards according to the ranking (without taking into account the suit) and count the number of those that are older (of those that are still in the game, of course). In the " Duckless " of these "ranks" there will already be four (by the number of suits), and in the most common "Trump" variant, the chain of trumps will cover each of the suits.

There are more intricate options. In the " double trump " fool, each of the players declares his trump card. By agreement, the trumps of one player must be beaten either with the same suit or, in addition, with their own trumps. As a result, the evaluation functions used for players will be different, but, of course, unchanged from one move to another (otherwise the entire minimax will go to hell).


The " double ", " Royal " and " Wild " versions of the game also require special construction of evaluation functions, but the approach proposed above works well in their case.

Battle for the feeder

What strategy should be followed when playing "The Fool"? First of all, it depends on the phase of the game. In the most common form, there are three main phases:

1. Initial
2. Intermediate
3. Final

The first phase is the longest. Until the deck is disassembled, the main task of the player (except for data collection) is the accumulation on the hands of high cards (especially trumps). This means that you should go so as to get rid of as many junior cards as possible (in order to take the appropriate number of cards from the deck). Opponents should be pushed away from the deck, making sure that they do not have a lack of cards in their hands.

If you hold a large number of high cards, they should be saved. It is often more profitable to take the cards (thereby saving your high cards), even if you have the opportunity to fight back. Taken cards can later be given away or thrown (especially if a taken card comes in a pair or a triple to cards of a different suit), and taking into account the fact that the higher cards are already in our hands, the likelihood that the opponents will find something valuable in the deck is small.

At some point, there are so few cards in the deck that they will be fully selected before the next move. This fleeting phase of the game is hard for a person to notice, but it can be very important. First of all, on this turn, you should take care to pick up not a complete set of cards. The second goal is an open trump card at the bottom of the deck (if there is an ace or a king, you should fight for it). In addition to the open trump card, the purpose of the struggle may be the last cards of the deck. Less is known about them, but in some cases, the presence of large cards can be predicted with high probability.

From all this it follows that AI should try to move, after which the whole deck is dismantled, fell on his back (the beating player takes the last card), but there would be enough cards left in the deck to have time to take the trump card. If there are not many cards in the deck, AI can be beneficial to be one of the pickers (those who pick up the last cards). This is a puzzling task, but for the computer it is quite feasible, since he knows the exact number of cards left in the deck at any time during the game.

When the deck is dismantled and the card showing the trump card is taken, the final stage of the game begins. The only goal of the player in this phase of the game is to get rid of all his cards as soon as possible. A private (but very important) case is the situation when there are only two players left. In this case, the cards in the hands of the opponent are precisely known (if we are not talking about the “Chukotka” variation) and you can plan the sequence of your moves so that the opponent cannot fight off on any move except the last. If this is not possible, you should fight back in such a way that the opponent will not be able to throw up his cards.

Of course, the proverbial wisdom has here and found ways to make our life more interesting. In the “ Pullback ” fool every second release goes to the deck, which complicates the game, but gives the “second” a chance to get good cards. In the " Empty " cards are taken only when the hand is completely empty (with this approach, it is unlikely that the trump cards obtained in the initial scenario will be preserved until the end of the game). In the " Second Attempt " variant, a player who fails to beat a card may try to fight off a card taken from the deck, and in the " Armenian " fool he may take a card from the deck for his call (these options can be combined ). Finally, in the " Piled " deck is simply divided between all players, after which any struggle for the deck is excluded, due to the lack thereof. With a fool you will not get bored!

Enemy of my enemy

So, with strategic goals, everything is clear (you need to accumulate large cards), but how to achieve this? In the most common “ Flush ” fool (and in the “ Translational ” too, if we are not talking about “ Impervious ”) there is a great tactical opportunity. Throwing a fighting player a card, you can ensure that he took them (or squandered all his trump cards). There are a number of restrictions regarding this possibility, for example, you cannot throw more cards than the one who has fallen away and, as a rule, the one who went first, but, all the same, “throwing up” cards is a great opportunity to change the course of the game.

It remains to determine the one who toss cards. In a two-player game, everything is clear - small cards should be thrown up whenever possible, large ones (especially trumps) - only in rare cases (for example, when there is a struggle for the last cards). If you play three (the most common case), everything becomes more interesting. The enemy, walking under the player, is obviously his natural enemy, but the one under whom the player goes, to some extent, his ally! It is unprofitable to “drown” him by giving him cards or making a move with a large card (this is not the best idea anyway), because if he doesn’t get out, the next move will be under us.

The player on the left (the turn is passed in a clockwise direction) should be allowed to fight off easily, and then maintain his turn, possibly forcing the beating player to take the cards. By analogy with the preference saying from the epigraph, the one by whom we walk is the “player”, and the one who walks under us is the “whistling”. When playing four players (or six, which is very rare), two “coalitions” naturally form (even if the game is not formally “ 2x2 ”). Players seated against each other are allies (at least until the number of players remaining in the game decreases).

All our beautiful plans, as usual, are shattered by the " Good " fool. In this version of the game, it does not matter to whom the cards are thrown, because even if the player cannot fight off, he will be the next to go! In the “ Baltic ” fool, the very process of rebound can easily turn into a counterattack (but, perhaps, this is too exotic version of the game, in any case, it is not very clear how to play three or more players by these rules).

The end - the cause of the crown

As I said, when the deck is completely disassembled and all the cards in hand, the only task of the player is to get rid of them as soon as possible. And here it’s not so much the strength of the cards that matters how many are their number. In fact, if a player has remained on his turn with one, even the youngest card (or with a pair of cards of the same rank), he has already won. Strong cards are needed only for a successful end (and it is very desirable that after this end of the opponent there are still cards). If two players are playing (and if special rules are not used that hide the information to the last), the winning sequence of moves can be simply calculated by exhaustive search (all the cards in the hand are known and there are not very many possible options). At the same time, you can even save a couple of sixes for the last move to put “epaulets” on the loser.

If there are more than two players, the cards remaining in the game are also known, but there is no information about which player has any. If there is no possibility to immediately give away cards under your own power (or discard all small cards, leaving trumps for the last post), you should follow the same tactics as in the main phase of the game - to walk with small cards, toss the player to the right on the larger side, to save trumps. Sooner or later there will be two players left (and if you are unlucky you will be one of them). At this moment it will become clear who won, since there will be no hidden information in the game.

There are several varieties of "Fool", allowing you to quickly get rid of their cards. For example, in “ American ” you can throw up cards to yourself, on your rebound, and cover them (after all the other players planted). In the " Sly " fool, if a player could not beat one or more cards, then that participant of the game, because of whom he was unable to fight back, can beat these cards from "his reserves". As a result, he gets rid of the extra cards, and the player who could not fight back - takes additional cards. In the " Brazen " fool, you can beat your card this way even before you throw it at your opponent. Of course, if the rules provide such opportunities to get rid of their cards, they should be used in every way.

Of course, my article does not claim any detailed description of all existing rules of the game or a formal description of AI algorithms for it. These are just scattered thoughts that I promised to share with the distinguished ComradMax before the holidays. I hope that they will be useful to him.