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?
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.