Undergrad Stochastic Minimax partition problem card game

[NotASmurf]

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

 

[.Scott]

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?

 

[NotASmurf]

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,

Do they alternate putting down cards?
After A puts down 10, is it B's turn?

yes

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

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]

 

[NotASmurf]

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?

 

[.Scott]

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?

 

[NotASmurf]

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?