Read about the game on Wikipedia: https://en.wikipedia.org/wiki/Ti%E1%BA%BFn_l%C3%AAn
I. What’s covered in that topic
I will discuss the basic things that humans (us, not the computer) can learn and use in the game: Heuristic and the minimax algorithm in the human case, and leave the configuration to you.
II. Introduction
If you could remember all the cards were played by everyone, you have a high chance to be the winner, of course, it’s almost impossible for normal people. What you could easily do is remember approximately the number of the cards, that were played based on the type of these cards like some are greater than 10 (“quân hình”) (J, Q, K, A, 2), and some are less than or equality.
Based on the rule of the game, you have to shed all thirteen cards before the others, but you couldn’t just play your card all the time you can, because you can use these cards later for some reason like get the advantage when these cards became the highest cards in the game, etc…
So how you can decide that? When you should play your card, and when not? This post introduces heuristic and minimax algorithms as an extension you can use, combined with other things like psychology,… to win the game.
III. Heuristic in the Vietnamese Card game
What’s heuristic? You could Google that for more details. For simplicity, it’s the method you define to evaluate/estimate the distance between your deck status at a specific time (your state) and the goal (become the first shed all cards), the value calculated by that function called heuristic value, we notate that by h(t). That is the concept, if you don’t know how to make the decision as I said before, now you have a specific value to evaluate your next step h(t+1), and you could choose which one is better based on the value of h(t+1). (If you could calculate 2 steps, it’s h(t+2))
Unlike chess, Gomoku (caro), or tic tac toe,… In the Vietnamese card game, we can not see other cards’ values. That’s why it’s not easy for the beginner, you have to estimate information about the other players’ hands if you want a good heuristic value, that values based on: your cards (you have the value), and other cards (you can count and estimate).
For the beginner, we see that common, naive rule: play the card that is as small as possible. For example, if other before you play the pair <5,5>, you have <9,9>, and <10,10> is larger than that, then you want to play <9,9>. So the heuristic function here is:
\begin{equation} h(t)=\frac{sum(\text{your cards})}{count(\text{your cards})} \end{equation}You could see that the lower of count(your cards) (or the number of the cards in your hand) the higher h(t), and the higher of sum(your cards) the higher h(t). So the higher h(t) the better. In this case, h(t) when you pass is lower than play <10,10> lower than play <9,9>, therefore you want to play <9,9>.
More complex examples, better heuristic:
Other: <5,5> You : <9,9>, <10,10> and <J,J> -> pass. h(t) now should involve “Bombs”.
Other: <5,5> You : <don’t have 6>,<7>,<8>, <9,9>, <10,10> and <J> -> pass or <10,10>. h(t) now should involve sequence.
In the above paragraph, we have the rule, then have h(t). Now, when you know about h(t), you can build your own h(t), your own rule.
But the game is not just you, so the good heuristic should comprehend the other hand. When the heuristic function is just about you, it’s easier than when it involves others, in the first situation, you know correctly how h(t) will become, like it gives you the power to know about the future, actually, it’s based on that power of you: you know how your hand changes after that. In the second situation, let’s move to the next section.
Before moving on to the next section, I can say that until now, you have enough “supplements” to “strengthen your game”. If you want to challenge yourself, let’s go.
IV. MiniMax Algorithm in the Vietnamese Card game
Let’s say the higher h(t) the better, so we want to maximize it as much as possible, assuming that all opponents are the best player, therefore they want to minimize it as much as possible. Let’s try the minimax algorithm here in the human case.
Here are a few things we need to pay attention to in the human case. First, in the game, you don’t have too much time to think. Second, you can not calculate 3 or more steps in the game tree like the computer in a short time. But you don’t need a specific value like the computer, you can just estimate the value. The final thing is very important, it’s the mobility we have when applying the minimax algorithm in the human case, not the computer case.
I draw some pictures that demonstrate the idea using the first example above:
The red square means another turn next, and the red number means it’s their play. So the red number will be covered by the blue square, which means you play next.
I’m not superman, so I just go to level 2 of the tree:
Because h2 is the Heuristic value for others’ turn, they will want to choose the smallest value. The Heuristic value of level 1 then will be decided by h2, which is -10 in the example below:
The graph goes backward to level 1 which is your turn, now you will want to choose the way that has the highest Heuristic value: 10 in the example:
Okay, it’s the idea.
So who is “the other” in this tree? How to calculate level 2, what is the heuristic function now?
Here are some suggestions.
First, “the other” could be “One vs. Rest”, which means “the other” here is everyone except you. It’s could be “One vs. One” which means “the other” could be anyone. Or it could be any else that you could think like the one that has the highest chance of not passing and after that one is your turn (maybe he or she still has a lot of cards in hand).
Second, what is the heuristic function? While I’m playing the game, I don’t want to calculate a formula that has a lot of variables or calculate any formula. So the heuristic function with me is some questions I ask myself about my cards, and other cards like what’s the best card I have, how many <K, A, 2> are left, how many cards each one has, etc. After I answer these questions, I can estimate whether one state is good or bad for me. To have a more correct value, I try to predict the final question to go deeper in the game tree and apply the minimax algorithm:
Finally, how do you know which cards others will play? This is the predicted concept that your brain will help you automatically, we move on to the next section to have a glimpse of that.
V. One more thing…
Reinforcement learning. You could hear that term somewhere… Yes, in the Vietnamese card game, it’s what you use to learn to be better. The concept is very simple, and reinforcement learning happens very naturally, when you go right, you get your prize (play more cards or win the game), when you go wrong, you lose, and you learn from that, that’s the thing you could call reinforcement learning in the game.
VI. Combine all!
“Fail smart”.
- List all the paths you’re able to choose.
- With each path, think about what the worst-case could happen, or you try to predict others’ steps, assuming that they will choose the worst for you (maybe not true in your game).
- When you play more, your brain will auto-tune to give you better intuition to predict others.
- After you have a good sense, you estimate the value to know what is the worst case, this should be based on your hands, and other hands.
- Finally, when you know the estimated value that all paths lead to (the worst case), you choose the path that has the best value.
VII. What’s next
Minimax algorithms for multiplayer? see that interesting answer from Prof.Chao: https://stackoverflow.com/a/63609301
More about poker algorithms: https://www.google.com/search?q=poker+algorithm
Similar problem in the computer case: https://stackoverflow.com/questions/12666119/using-minimax-search-for-card-games-with-imperfect-information
