OK, no problem, here's the rules:
3 players, deck of 32 cards (7 to A). Each player gets 10 cards, and two are left on the table (faces down). Dealer changes clockwise after each contract is played. His left neighbour picks a contract to play. The game is made by 10 contracts. The aim - to score more points that other two players. The basis of this game is always the same (except one time, which I will tell later): Highest card takes the trick, and you always must follow suit.
Now the contracts and rules:
1. "Tricks". Rules: don't take tricks. Each trick is 4 negative points (-40 overall).
2. "Hearts". Rules: don't take hearts. Each heart is worth -5 points (-40 overall). You can't play hearts (if you are the first to lay a card) while still have other suits.
3. "Jacks". Each jack is -10.
4. "Queens". Each queen is -10.
5. "The King". Rules: don't take a king of hearts. It's worth -40. You can't play hearts during this contract as well.
6. "2 last tricks". Each of two last tricks are worth -20.
7. "Win-back". Rules: take as much tricks as you can. Each is worth 12. Before starting to play this contract, you must tell a trump. If a player can't follow suit, he must play with a trump (if he has at least one).
8. Another "Win-back"
9. "Take nothing". Rules: don't take tricks, hearts, jacks, queens, the king and two last cards. (-240 altogether).
10. "Take all". It's opposite of "Take nothing". Total score of this game is +240.

One little aspect of this game: when you pick a contract, you get those two cards, lying on the table. You must show them to your opponents, before taking. After that, you must discard any two cards you want. But if, let's say, you are playing "Queens" and discard one queen - this thing counts of course. So in this case, you instantly get -10.

Well, I think that's all. So, I'm working now with "tricks", because it's the core of all other contracts. But basically, I have to make my card game to pick any of those contracts, which suits computer player the best.

Quote:

Original post by InnocuousFox The order you and your opponents play your cards often makes a lot of difference in who will win.

I can't agree more, it's true. That's why I'm struggling here and don't have any actual solution so far.

Quote:

Original post by Marcius Quote: Original post by InnocuousFox The order you and your opponents play your cards often makes a lot of difference in who will win. I can't agree more, it's true. That's why I'm struggling here and don't have any actual solution so far.

Re-read the line about this problem being NP-hard.

I agree that precisely solving this problem is probably intractable. It doesn't mean you can't do anything -- chess is intractable too, but there are good algorithms for playing it. I know there are algorithms for playing bridge and poker, too, so you might want to read about that and see if you find something that works for this game as well. But it probably would require a lot of effort, so if you just want to implement something quickly and forget about it, then reading about bridge playing is not the way to go.

I thought a relatively simple heuristic can be implemented like this. First, restrict your game to just one suit. So there are just 8 cards. You know your cards, but don't know your opponents'. So just consider all the possibilities. Suppose you have 7, 8, 9, 10, J. Then your opponents have Q, K, A. Let's enumerate possibilities like this: (opponent1, opponent2). So there are the following possibilities: (QKA, nothing); (QK, A), (Q, KA), (KA, Q), etc. How many possibilities can there be total? Let's say your opponents have N cards. If you pick a subset of N for one opponent, that uniquely determines the cards for the other opponent. And the number of ways to pick a subset of N objects is 2^N. So in the worst case, when N=8, you will have only 256 possibilities, which is still manageable. Calculate the number of tricks you take for each possibility and take the average.

Now, how do we know how many tricks you take for a given possibility (i.e. for a given split of cards among all three players)? Just simulate the game. Do something like this:

* First player: PlayMyBestCard()
* Second: PlayMyBestCard()
* Third: PlayMyBestCard()
* Determine who takes the trick
* Repeat until no cards are left

So what's left is to decide how to implement PlayMyBestCard(). You might have some quick-and-dirty heuristics about how to do it. Something like "Play your highest card that's still below one of the other cards in the trick, to make sure you don't take the trick. If you can't (so you'll have to take the trick), then play the highest card instead to get rid of it." I tried this briefly and it doesn't seem to work too well, so this is where your knowledge of the game comes in.

Alternatively, you may be able to just do a brute-force search to find the best card to play. Basically, once you know who has which cards, there is no more uncertainty. So you can simulate it much like a brute-force version of chess or tic-tac-toe. There are only three moves in a trick, so the depth of search is 3, and you may be able to do it efficiently enough.

I like your approach to the problem, Gil. One little comment on your example though. Grounding on 2^N, where N is 3 in this case, we get these 8 pairs of combinations (opponent1,opponent2): (Q,KA), (KA,Q), (K,QA), (QA,K), (A,QK), (QK,A), (QKA,nothing), (nothing,QKA). But I think it would be reasonable to eliminate half of them, because it doesn't matter, how one combination is divided for two opponents. For example, either it's (Q,KA) or (KA,Q), the outcome is the same. So, in the worst case where N equals 8, you have not 256 possibilities, but twice less instead - 128. Just a thought.
Anyway, I'll try to solve my problem in this way and see, how it goes. If anyone comes up with something, feel free to share it. I'll let you know how things are progressing.

Quote:

Original post by Marcius But I think it would be reasonable to eliminate half of them, because it doesn't matter, how one combination is divided for two opponents. For example, either it's (Q,KA) or (KA,Q), the outcome is the same.

Be careful if you do that -- the outcome might depend on the order of moves as well. If the player who has Q moves first, the outcome may be different than if the player who has KA moves first. Otherwise, yes, there might be optimizations like that that you can use. Good luck!

You're right, thanks for emphasizing it. I'll have that in mind.