Stochastic Minimax partition problem card game

In summary: X.pass() //pass if there are no more cards to playelif len(piles) == 1:playerX.play(piles[0]) //play 1 onto the active pileelif len(piles) == 2:playerX.play(piles[1]) //play 2 onto the active pileelif len(piles) == 3:playerX.play(piles[2]) //play 3 onto the active pileelif len(piles) == 4:playerX.play(piles[3]) //play 4
  • #1
NotASmurf
150
2
Hey all, ran into a game theory problem I can't solve.
A and B have a set of 10 random numbers from 1-10, players can make so called "piles", a pile has a goal number from 1 to 10, if 6,3 are on the table, a pile of nine may be started, the pile is added to by adding sets of numbers that sum to the piles defining value.

Simple case:
During each turn, player places a number on the table,
goal is to get rid of all your numbers, numbers can be removed by making piles, minimize number of piles.

in a one player scenario, player would find all combinations of their hand in the form ([a+b+c+d+e],[a+,b+c+d+e],[a+b,c+d+e],[a+b+c,d+e],[a+b+c+d,e], [a,b,c+d+e],[a,b+c,d+e]) etc. Pick the combination for which the most subsets satisfy the constraints and for which the most subsets sum to the same value.

Real case:
A and B have a set of 10 random numbers from 1-10, the elements are picked from 4 sets of the numbers 1-10
During each turn, player places a number on the table,
Objective is to obtain as many of n special "point" numbers. Point numbers may be accrued by terminating a pile containing them, numbers can be removed by making piles, Once a player places a number/card whose single value is the piles value, they may terminate that pile.
The game ends when all 20 of A+B's numbers are used. but you may want to wait for multiple point numbers before terminating.

I can see that this is a stochastic minimax problem, probability inferences are made via card counting.
that requires nested bruteforcing and recursion, but can't come up with a fullproof, non tautological algorithm, Having trouble figuring out how to span all the search space without missing anything. Any help appreciated. :D
 
Physics news on Phys.org
  • #2
Let's see if I understand what you've said with this example:
A starts with: 1,3,4,4,6,7,7,8,9,10
B starts with: 2,2,2,4,6,7,8,8,9,9
A puts down 7, B puts down 2, so we have piles of 9. Or are the 2 starter cards drawn from the deck of 40?
Then A puts down a 10. Does A go first? What happens when he goes over the goal of 9? Do they alternate putting down cards?
After A puts down 10, is it B's turn?
If B wants to throw away a 2, can he put it on the 10?
 
  • #3
.Scott said:
What happens when he goes over the goal of 9?
If B wants to throw away a 2, can he put it on the 10?
They may not, The sum may not exceed ten,
.Scott said:
Do they alternate putting down cards?
After A puts down 10, is it B's turn?
yes
.Scott said:
A puts down 7, B puts down 2, so we have piles of 9. Or are the 2 starter cards drawn from the deck of 40?
A starts
.Scott said:
Then A puts down a 10. Does A go first?
A must complete a pile before starting another, only one may be active. if he cannot contribute, the card either stays on the table or the other player uses it.

[/QUOTE]
 
  • #4
Assuming we know A and B's sets. I'm still confused. I know there has to be a better solution than pure turn based minimax, any suggestions?
 
  • #5
If I understand the rules correctly, we could have:
1st: A puts down a 3, then B puts down 1, so piles must total 4.
then:
A puts down 3.
B does not have a 1, so it cannot play onto the 3. So it puts down a 2 - starting a new pile.
A puts down a 2 and scores 1 point.
B puts down a 2.
A does not have any card less than 4, so it passes.
B does not have a 1 or 2, so it starts a new pile. It puts down a 4 and scores a point.
A passes again.
B passes because it also has no more cards that are 4 or less.

Would that be correct play?
Or does it remain your turn for as long as you can add cards to your pile?
 
  • #6
.Scott said:
If I understand the rules correctly, we could have:

B does not have a 1, so it cannot play onto the 3. So it puts down a 2 - starting a new pile.

Or does it remain your turn for as long as you can add cards to your pile?

Not this part, if it puts down a 2, that remains on the "usable to both" table stack, He cannot start a new pile til one of them closes current one.

So far my logic is, Get possible moves for player X:


for i in range(0,len(hand)):
for r in range(0,len(piles)): // this was for the 2 pile variant, much more complicated
moves.append([i,r,-2]) //add potential move from hand to pile
for i in range(0,len(hand)):
for r in range(0,len(table)):
for k in range(0,len(pile)):
moves.append([i,r,k]) //add potential move from hand to table, to pile (since you may use as many table cards as there are during your move

taking the move tree, i then apply minimax algorithm.

The above assumes you know B's hand, I'm using this formula for extrapolating card probability:

def ProbablityOfKcardsWithB(Bhand_length, cards_not_being_played, how_many_B_has_in_hand):

return 1.0 - (Choose(cards_not_being_played, how_many_B_has_in_hand)/(1.0*Choose(cards_not_being_played+ Bhand_length,how_many_B_has_in_hand)))I then mix the the two with:


if deadly:
defend against deadly
iv both deadly:
defend against maxALTHOUGH I think the above needs a more rigorous definition. Any help appreciated?
 

1. What is a Stochastic Minimax partition problem card game?

A Stochastic Minimax partition problem card game is a mathematical game that involves partitioning a deck of cards into two groups based on certain rules. The goal of the game is to minimize the maximum difference between the sum of the values in each group.

2. How do you play a Stochastic Minimax partition problem card game?

To play a Stochastic Minimax partition problem card game, you first need to have a deck of cards. The deck can be of any size, but the values of the cards should be positive integers. Then, players take turns choosing a card from the deck and placing it into one of the two groups. The game ends when all the cards have been placed, and the winner is the player whose group has the smallest maximum sum.

3. What is the strategy for winning a Stochastic Minimax partition problem card game?

The optimal strategy for winning a Stochastic Minimax partition problem card game is still an area of active research. However, one possible strategy is to always place the highest value card in the group with the lower current sum, and the lowest value card in the group with the higher current sum. This strategy can lead to a near-optimal solution in many cases.

4. Can Stochastic Minimax partition problem card game be solved using a computer?

Yes, Stochastic Minimax partition problem card game can be solved using computer algorithms. However, as the number of cards in the deck increases, the complexity of the problem also increases, making it computationally challenging to find the optimal solution.

5. How is Stochastic Minimax partition problem card game related to other mathematical problems?

Stochastic Minimax partition problem card game is related to other mathematical problems such as the Partition problem, Knapsack problem, and Subset sum problem. These problems all involve finding an optimal partition or allocation of items to different groups based on certain constraints.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
859
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Poll
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
29
Views
1K
Replies
9
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Replies
2
Views
636
Back
Top