2
$\begingroup$

A friend of mine and I are trying to teach a bot play a card game (bela)

We are using monte carlo tree search (MCTS) to estimate the probability of winning hand in regards to multiple possible (!important) card configurations.

We are randomizing both plays and possible card configurations. The problem is not all card configurations are possible in the later stages of the game, according to the rules (e.g. you have to follow the card suit cast by the first player if you can do so).

So, not to iterate over every (illegal) combination of cards, we have come up with an idea of blacklisting certain cards for a certain player, so that the algorithm doesn't go through card combinations that cannot happen according to rules.

To summarize, we need to deal N cards over M players in such a way that no player receives a card they shouldn't receive according to rules (each player has its own set of blacklisted cards).

The main problem is, reshuffling cards until the constraints are met doesn't seem feasible (even after millions of iterations we never satisfy all the constraints (factorials)).

Can you point us to a direction which would efficiently solve our problem?

Thanks!

Edit #1 as per comment below:

Problem definition in summary(second attempt): There are n players and m cards available(n=3, m=x*3, x E (1,8)). Each player has its own list of illegal cards(cards she/he shouldn't receive). How to spread m cards over n players so no violation of constraints occurs. Constraints are satisfied if no player received a card that is subset of hers "blacklisted" cards.

We need efficient algorithm that doesn't just randomly spawn card configurations until constraints are met.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Can you given a simple nontrivial example to demonstrate the requirements? You may use less cards and players. $\endgroup$ – Apass.Jack Nov 14 '18 at 22:10
  • $\begingroup$ Your question are missing any details, which makes it impossible to answer. $\endgroup$ – Yuval Filmus Nov 14 '18 at 22:12
  • $\begingroup$ Thank you for replying. Problem definition in summary: There are n players and m cards available(n=3, m=x*3, x E (1,8)). Each player has its own list of illegal cards(cards she/he shouldn't receive). How to spread m cards over n players so no violation of constraints occur. Constraints are satisfied if no player received a card that is subset of hers "blacklisted" cards. $\endgroup$ – ritaj Nov 14 '18 at 22:41
  • $\begingroup$ Are you interested in finding one feasible solution or a random feasible solution? In the former case it's finding a perfect matching in a bipartite graph, in the latter it's sampling a random perfect matching in a bipartite graph. $\endgroup$ – Yuval Filmus Nov 14 '18 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.