AI for the "Fool"

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

           Folk wisdom. 

    Under the player - from Semak, under the whistler - from the ace.

           Another folk wisdom. 


    Everything seems to be mixed up in this post. " Fool " in the title, preferential sayings in the epigraph and KDPV , which has nothing to do with either. However, the very concept of " joker ", to the subject of today's conversation, has a very direct relationship.

    About a month ago, ComradMax published an article about its debut game under Android (the article, by the way, is also a debut one). The topic touched me pleasantly amazed by the abundance of options known to all. I knew about some, others became a revelation for me. The very idea - to turn a card game into a kind of RPG took me alive. Unfortunately, AI implementations proved to be not the best way. Although I have not played Fool since I was five years old, I easily beat the program. Some of her moves are simply stupid (I hope that the author will not be offended by 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 such a game should work. I must say that this problem is much more complicated than it seems at first glance. Card games (including “Fool”) belong to the category of games with incomplete information. The algorithms used in chess programs or programs for playing Go 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 bit, because the cards are closed from us? In fact, everything is not so bad. For example, we know what cards we have on hand and the face value of a card showing a trump card (if the game is played with a trump card). This in itself is already not bad, but even better is our knowledge that the opponent does not have these cards (this is if the game is played in one deck). Let's try to compile a complete list of sources of data on enemy maps, as applied to the "Fool":

    1. Open cards (I already spoke about this)
    2. Cards taken by players during the game (including those with which they tried to unsuccessfully fight back)
    3. Cards that exit the game as a result of hang up (this source is less obvious than the previous ones)
    4. Cards that could not be beaten (this is even less obvious and I will talk about it below)

    Another source
    The ComradMax program can get information about enemy cards in another funny way. The fact is that all the actions in it (such as hanging up or drawing cards from the deck), the author tried to implement with gestures. This control is intuitive enough to dispense with buttons (although there are buttons, just in case). So, if you take a card from the deck and “do not drag” it to your cards, it opens and opponents “see” it. Computer players make malicious remarks, but, according to the author, the AI ​​program does not use this information in any way.

    In principle, no one can stop the computer from spying everythingplayer cards. Moreover, the developers of most card games follow this path, but this path is vicious, in essence. The computer game, in itself, does not look much like a human one, and if it “knows” all the cards, it is even more striking. The user may not even realize this, but after playing a dozen games, he will cool off to the program. I believe that the playing style of such "entertainment" programs should be as close as possible to a human-like one. The goal is not to make the program play as hard as possible. The main thing is that it does not cause rejection! And the AI ​​option with “snooping” cards can be used for special options, such as “playing with a sharpie”.

    Although everything is clear with the second paragraph, I want to emphasize that we must take into account any cards we know that the opponent takes. For example, in the modification of the game " Magic ", if we go with a black joker (the picture is still in place), 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 some way (we will find out about this). Perhaps this is not obvious, but this can happen at a time when he, in turn, comes off as a black joker. What to do, in this case, will be clear from further narration.

    Starting with the third digit, things get a little more complicated. In general, it is clear that AI must take into account cards that have left the game, the question is how to implement this technically. To represent the cards in the hands of opponents, you can use two types of objects. The first is a card with a precisely known denomination (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 players make moves, we get more and more information about the cards that have left the game. Crossing out these values ​​from the "joker" (with such a representation of the data, he is the only one for all unknown cards), we refine our knowledge about closed cards. When the deck is completely disassembled, we know all the cards (we don’t only know which one), and when there are two players left, we just know all the opponent’s cards!

    The fourth source is even more ephemeral. Suppose we go under the enemy, and he takes a card without even trying to beat it. 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 with the same suit, but with a denomination higher (there is no reason to go lower, for obvious reasons) , then he will take it too (or finally take up trump cards). This means that for the "jokers" in his hands, you can make a note that they are not higher than the face value whose card we used (taking into account the seniority of the trump cards). If we make a mistake, it's never too late to uncheck a box.

    Of course, so that life didn’t seem like honey to us at all, various rules were invented that complicated the collection of information. At Poker"A fool, a player, before the end, has the right to exchange any two of his cards with cards from the deck. In fact, this means that we will have to completely discard information about the player’s well-known cards. After such an exchange, all his cards turn into" jokers ". An exception can be made, except for the highest cards in a suit and trumps (hardly anyone in sound mind will change them).

    The fool " On through the acquisition"(there is a ransom in Fool, didn’t lie an 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 In fact, in the final stage of the game, he almost does not change anything in our knowledge of the situation, but only obliges to end the game with completely random cards. If the cards fail, AI is unlikely to help.

    Also, it is aimed at an unexpected ending " Secret"fool. A trump card is placed under the trump card. When a trump card (after parsing the deck) is taken by one of the players, this card opens and shows a new trump card. At that moment, everything that was acquired by overwork, during the game (including the desired trump card, below decks), it may well turn into dust. In this game, randomness can also outweigh the AI ​​intellect (unless you use the strategy of playing the “ Smokeless ” fool with a set of high cards in all suits).

    Perhaps the toughest option for AI is " Chukotka . "Immediately after Section and opening and trump deck (with open-trump) is removed from the game. The game is very short-lived, and there is practically "in the dark». AI is nowhere to turn.

    The measure is important in everything


    Well, we collected the data and, to some extent, we know what kind of cards are in the hands of the enemy. We can calculate the probability that the enemy can successfully repel our approach (this does not mean that he will do it), but this is not enough! We still cannot “take and just use” the 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 cards are on hand, 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 thing to do with the " Bezmastny"Option. Are building card in order of size (without suit) and the number of those older (those that still in the game, of course). In" Bezkozyrnom "these" ranks "will have four (number of colors), and in the most common "Trump" option, a chain of trumps will cover each of the suits.

    There are more intricate options. In the " Two-trump " fool, each player announces his trump card. By agreement, the trump cards of one player must be beaten either with the same suit or, in addition, also with their trump cards. Athe, the evaluation functions used for players will be different, but, of course, unchanged from one move to another (otherwise the whole minimax will go to hell).

    A little clarification
    Generally speaking, even with a good evaluation function, two more circumstances interfere with alpha-beta clipping. Firstly, all these minimax pieces are designed for a two-player game. The evaluation function is constructed in such a way that from the assessment of the player’s state, the assessment of the state of his opponent is subtracted. If we calculate the assessment of the same position, but from the opponent’s point of view, the sign changes, but the absolute value remains the same (and this is important for the algorithm to work). In the case of Fool, a two-man game is the exception rather than the rule. However, we can turn around and consider all opposing players as one single opponent (we are interested in the worst case scenario for their joint behavior). In the case of the game " 2x2 ", opposing players should be considered pairs.

    Another open question is the "jokers" in the hands of opponents, the value of which we know only approximately. It is difficult to offer a satisfactory solution. You can average the ratings of those cards that the joker can represent, but experiments are needed to determine how good this approach is.

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

    Battle for the feeding trough


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

    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 collecting data) is the accumulation of high cards on his hands (especially trump cards). This means that you should walk in such a way as to get rid of as many low 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 lack cards in their hands.

    If you have a large number of high cards on hand, you should save them. It is often more profitable to take cards (thereby saving your high cards), even if there is an opportunity to fight back. The cards taken can then be given or thrown (especially if the taken card comes in a pair or three to cards of a different suit), and given the fact that the highest cards are already in our hands, the likelihood that opponents will find something valuable in the deck is small.

    At one point, there are so few cards in the deck that they will be completely selected before the next turn. This fleeting phase of the game is hard to notice for a person, but it can be very important. First of all, on this move, care should be taken to pick up a incomplete 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 an open trump card, the last cards of the deck may also be the goal of the fight. Less is known about them, but in some cases, it is highly likely to predict the presence of large cards there.

    From all that has been said, AI should try to ensure that the move after which the entire deck is parsed falls on its end (the batter takes the cards last), but at the same time there would be enough cards in the deck to catch the trump card. If there are few cards in the deck, AI can be beneficial to be one of the throwers (for those who take the last cards). This is a puzzling task, but it’s quite feasible for a computer, since he knows the exact number of cards remaining in the deck at any time in the game.

    When the deck is taken apart and the card showing the trump card is taken, the final stage of the game begins. The player’s only goal in this phase of the game is to get rid of all his cards as soon as possible. A special (but very important) case is the situation when there are two players left. In this case, the cards in the hands of the enemy are precisely known (if we are not talking about the "Chukchi" version) and you can plan the sequence of your moves so that the enemy could not fight back on any move except the last one. If this is not possible, one should fight back so that the opponent does not have the opportunity to throw his cards.

    Of course, folk wisdom also found ways to make our life more interesting. In the " Jack Off "“a fool every second hang-up goes to the deck, which complicates the game, but gives a“ second ”chance to get good cards. In the“ Empty ”cards are taken only when the hand is completely empty (with this approach, keep the trump cards received during the initial game it’s unlikely to succeed.) In the “ Second attempt ” option , a player who fails to beat a card may try to beat off a card taken from the deck, and in the “ Armenian ” fool, he can take a card from the deck for his call (these options can be combined ). Finally, in the Bulk deck, is divided between all players, after which any struggle for the deck is excluded, due to the absence of such a deck.

    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 “ Flip ” fool (and in “ Transfer ” too, if it’s not about “ Flapless ”) there is a great tactical opportunity. By throwing cards to the beating player, you can ensure that he takes them (or squanders all his trump cards). There are a number of restrictions regarding this feature, for example, you cannot throw more cards than there are on the hands of the beater and, as a rule, the one who walked is the first to throw, but, nevertheless, “throwing” cards is a great opportunity to change the course of the game.

    It remains to decide who to throw cards at. In a two-player game, everything is clear - small cards should be thrown whenever possible, large cards (especially trump cards) - only in rare cases (for example, when there is a struggle for the last cards of the deck). If three play (the most common case), everything becomes more interesting. The adversary walking under the player is obviously his natural enemy, but the one under whom the player himself goes is to some extent his ally! It is unprofitable to “drown” him by throwing cards at him or making a move with a large card (this, in any case, is not a good idea), because if he doesn’t fight off, the next move will be under us.

    The player on the left (the move is transmitted clockwise) should be allowed to easily fight back, and then support his move, possibly forcing the bouncer to pick up cards. By analogy with the preference saying from the epigraph, the one we walk under is the “player”, and the one who walks under us is the “whistler”. With a game of four players (or six, which is very rare), two “coalitions” are naturally formed (even if formally the game does not go “ 2x2 ”). Players sitting on top of each other are allies (at least until the number of players remaining in the game decreases).

    All our beautiful plans, as usual, are smashed to smithereens by " Good"a fool. In this version of the game, it doesn’t matter to whom to throw cards, because even if the player cannot fight back, he will still be the next to go! In the Baltic fool, the end process itself can easily develop 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 according to these rules).

    The End - Crown


    As I said, when the deck is completely disassembled and all the cards on hand, the player’s only task is to get rid of them as soon as possible. And here it becomes important not so much the strength of the cards as their number. In fact, if a player remains on his own move 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 successful rebound (and it is very desirable that after this rebound the opponent still has cards). If two players play (and if special rules are not used that hide information to the last), the winning sequence of moves can simply be calculated by exhaustive search (all cards on hand are known and there are not many possible options). At the same time, you can even save a couple of sixes for the last move in order to put “shoulder straps” 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 of the players has which. If it is not possible to immediately give away cards on your own (or discard all small cards, leaving the trump cards for the last hang up), you should follow the same tactics as in the main phase of the game - go with small cards, throw a bigger player to the right, keep your trump cards. Sooner or later, there will be two players left (and if you are not lucky, 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" that allow you to quickly get rid of your cards. For example, in " American " you can throw cards to yourself, on your last post, and cover them (after all other players have thrown). IN "A cunning "fool, if a player could not beat one or several cards, then that participant of the game, for which he could not fight back, can beat these cards from" his reserves. "As a result, he gets rid of excess cards, and the player who I couldn’t fight back - it picks up additional cards. In the “ Insolent ” fool, you can beat your card this way before throwing it to an opponent. Of course, if the rules provide such opportunities to get rid of your cards, they should be used in every way.

    Of course, my article doesn’t pretends to be any kind of adolescent a complete description of all the existing rules of the game nor a formal description of AI algorithms for it. It's just a disjointed thoughts that I promised to share with the distinguished ComradMaxbefore vacation. I hope that they will be useful to him.

    Also popular now: