General > Tutorial, training, online play
Any info on how the AI works?
Jimmy V.:
--- Quote from: Ti D. on 10/03/18, 01:03pm ---Really interesting.
One thing that has always interested me is whether the bots play with perfect memory. This is especially relevant for Glastonbury, where knowing exactly what you and your opponent has is a huge advantage in the endgame. Most humans will remember most but not all of the cards, and weigh up the benefits of lokking at the cards collected or picking up a different card
--- End quote ---
Well indeed the bots use their perfect memory when it is needed (by that I mean for the better bots). As I said, it is hard enough to program an AI. It would be cruel on us to forbid the use of this.
I already hear people complaining. "This is not fair. I can't have perfect memory. The bots should not have perfect memory. Nor should they be allowed to play with precomputed tables/knowledge/opening database/endgame database." To this, I reply that the fight against an AI is not fair by definition. They use electricity, we don't. They have perfect maths, we don't (and they are quick at it too). They have infinite storage, etc. Suppose you were racing a 100 meter against a car. What would the point of saying that the race is unfair? Of course it is. :)
Of course, it is always better if the bots play similarly to humans, with the same strengths and the same flaws... And we always hope to be as close to that as possible. But by essence, it is not possible. For a start, computers will always be stronger at tactics (that requires computation and short-mid term exhaustivity) than at strategy. As much as we try to avoid the issue, our bots will always struggle with strategy, at least from the point of view of the top human players.
I hope this answers the question.
Jimmy V.:
--- Quote from: Pouche H. on 10/03/18, 09:28pm ---IMO one of the more 'advanced' techniques to be on the watch for (and bots use!), is their ability to grasp probabilities that their opponent has X number of playable cards in their hand. Given the number of remaining draw cards, the bot may choose to extinguish the discard piles (something most players don't keep track of) eliminating the players ability to extend the match.
I hate when that happens. :)
--- End quote ---
They don't know anything about that specifically and as a player, I have never really thought about it this way really. There is little a chance the AI could have grasped it by itself without me telling them about it. In any case, you are right, it is an important part of the game to figure out the best moment to start laying your last cards and always an advantage to be the one who does not need to slow down the end game by drawing useless discarded cards. I guess sometimes the AI find the right timing.
--- Quote ---Congrats on keeping it fun...
--- End quote ---
Thanks!
--- Quote ---And have you ever considered an even higher level bot (for Lost Cities) that wouldn't be in the regular rotation, but could be accessed if desiring a higher challenge?
--- End quote ---
I am not sure what you have in mind here. Can you develop? I have in any case never thought about that possibility. That's why I am curious.
Chris M.:
Wow, that was a very interesting read! Thanks for sharing the details, as I am a computer programmer myself it makes the game more interesting.
It's very impressive they can play so well in only 10ms, that speaks to a very well designed evaluation function.
I understand how Alpha-Beta works in the perfect information case like with Buggy (very cool by the way), and I even understand how it could extend to a game like Backgammon that has dice where each outcome has a fixed probability. But I'm hoping you can explain to me how this can work in Lost Cities where the actions your opponent can take depend on the hidden information...?
So suppose the bot would search each of the 8 cards in hand to either play or discard that card, then it would search a draw action. Is it going to have a lot of branches and search every card that's still in the deck, and assume they're equal probability? Or does it already know what card is on top of the deck and only needs to search the true outcome (which a human player wouldn't know)?
Then the same question for when the bot is searching the opponent's turn - would the bot search every possible card the opponent could have, or does it already know?
Anyway, I understand that you might not want to say too much about how the AI works, but I would appreciate any info you're willing to give :)
Jimmy V.:
--- Quote ---So suppose the bot would search each of the 8 cards in hand to either play or discard that card, then it would search a draw action. Is it going to have a lot of branches and search every card that's still in the deck, and assume they're equal probability? Or does it already know what card is on top of the deck and only needs to search the true outcome (which a human player wouldn't know)?
Then the same question for when the bot is searching the opponent's turn - would the bot search every possible card the opponent could have, or does it already know?
--- End quote ---
Well in both cases, that would be considered cheating. And I don't want to use this kind of technique to make my life easier. Players have already accused the bots of cheating on many occasions. I can only imagine what the reaction would be if the bots actually knew what cards were coming and based their decision upon it. brrr...
In case of hidden information, one can imagine three approaches.
The first one is to go through all possibilities. If we are talking about the deck (and the remaining cards in the deck), it is doable. But it is not even good enough. Near the end of the game, the probability of drawing a 10 that has not been played yet, is much lower than the possibility of drawing a 2 that has not been seen. Why is that? Because the 10 is probably in your opponent's hand and they kept it. In case of a 2, there is every chance that they would have discarded it earlier. The program knows this sort of thing and uses it when estimating the potential remaining in each suit.
The first approach is in any case completely impractical if we think of the hand of the opponent. We can try to compute all possible hands and decide for each one what would be the best play. Then compute the best moves from there. But that's going to be a big/huge number of combinations, especially at the start of the game. In that case, the second approach could be used: generating a set of possible opponent's hands (and their likelihood to refine the process) and for each of them find the best course of action. So we would decide on the best move based on a subset of possible opponent's hands. The method would probably be called Monte-Carlo simulation.
We don't use any Monte-Carlo simulation because we went for the 3rd approach which is guaranteed to be less CPU-intensive and hopefully gives good enough estimations. Basically, we built a simplified model that does not need to know exactly what the opponent has. We are simply interested in the potential of each expedition (for us and for the opponent) and decide from there what cards are worth.
As I said, dealing with hidden information very easily leads to huge combinatorial complexities. So simplifying the process is absolutely needed for all games but the simplest ones. Even for Hanamikoji, a game that has only 21 cards, of which we know 6-7 at the start, an exhaustive approach would probably already be too much.
Christian W.:
So, interestingly I think I do quite well against other players but the computer can be hard to beat. Computer seems to play quite differently than normal players. Very aggressive discards, see discards up to 4,5. Most humans just avoid aggressive discards, not sure when to use them or how to counter.
--- Quote ---Obviously, the program will also recognize the end game and try not to get stuck with all his good cards in hand at the end (as we humans always do).
--- End quote ---
I think this might be one of the weakness's of the AI. I think it delays the endgame too often. It might be correct to delay the endgame at that point, but it might've been better to play more cards earlier (or not start a new colour so late).
Navigation
[0] Message Index
[#] Next page
[*] Previous page
Go to full version