2
$\begingroup$

Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at the end of the game (and assuming each player is playing optimally).

All presented solutions based on recursion suggest to save at each position in an array (memoization) the points difference between the 2 players, thus deriving the current step as the number of stones taken minus the difference at the following position.

I tried instead a different approach, where I save at each array position the best score any player get starting from that position onward. I then compute a single recursion step as the number of points collected in the current turn plus the best score the same player might get from here on (recursion), taking into account the player are alternating.

My solution fails with some test cases and I wanted to understand if there is a problem with the theory (or if I just have to counter check the implementation).

$\endgroup$
3
  • $\begingroup$ Are you prepared to accept an answer that says "there is no problem with the theory"? You should counter check your implementation. Are you not able to see the failing test case? $\endgroup$
    – John L.
    May 28, 2023 at 13:50
  • $\begingroup$ @JohnL. Absolutely! As I couldn't spot the issue in the implementation I was just wondering if there was a problem with the theory behind it before wasting time in counter checking the code. $\endgroup$ May 28, 2023 at 15:49
  • $\begingroup$ Have you corrected your solution? Is my answer good enough? $\endgroup$
    – John L.
    Jun 8, 2023 at 19:07

2 Answers 2

1
$\begingroup$

It is certainly a valid approach to compute "at each array position the best score any player get starting from that position onward".


If a player starts first from position pos, denote that best score as best_score_from_pos(pos, "Alice"). Otherwise, denote that best score as best_score_from_pos(pos, "Bob").

The recurrence relations are
best_score_from_pos(pos, "Bob") = value_sum_from_pos(pos) - best_score_from_pos(pos, "Alice")
and
best_score_from_pos(pos, "Alice") = max(
   stoneValue[pos] + best_score_from_pos(pos+1, "Bob") ,
   stoneValue[pos] + stoneValue[pos+1] + best_score_from_pos(pos+2, "Bob"),
   stoneValue[pos] + stoneValue[pos+1] + stoneValue[pos+2] + best_score_from_pos(pos+3, "Bob") )
when the indices for stoneValue are within bound. If out of bound, replace the corresponding argument for the max function with 0.

If best_score_from_pos(0, "Alice") * 2 > total value, Alice wins.
If best_score_from_pos(0, "Alice") * 2 < total value, Bob wins.
If best_score_from_pos(0, "Alice") * 2 == total value, it is a tie.


It is slightly more complicated to implement the approach above than the "presented solutions" that computes for each position "the points difference between the 2 players". On the other hand, the approach above is somewhat easier to understand.

By the way, my implementation of the approach above passes all tests for the LeetCode problem.

$\endgroup$
2
  • $\begingroup$ I have used the second recurrence relation you mention, swapping Alice and Bob in consecutive calls. I'm not sure why also the first relation is needed? What does it add with respect to using just the second one alternating the players? $\endgroup$ Jun 10, 2023 at 21:10
  • 1
    $\begingroup$ Your "using just the second one alternating the players" should be equivalent to using the two recurrence relations I mentioned. The point is that starting at a position onward, the best score obtained by the player going first at that position is different from the best score obtained by the player going second at that position. The sum of these two scores is the sum of all values from that position, which is my first relation. $\endgroup$
    – John L.
    Jun 10, 2023 at 21:41
0
$\begingroup$

There is a well known algorithm to solve Zero sum games called MiniMax algorithm. The reason for the failure of your above mentioned approach: Let's say at Alice's turn she took a move to maximize her score in the next turn Bob will try to minimize Alice's score. I think you focussed on only one player's action and didn't take account of other player's action . Score_of_player(Alice,i)=Max(Min(Score_of_player(Bob,i-1))) where i is the number of turns

$\endgroup$
1
  • $\begingroup$ Well actually I did take into account both players' actions, as a every recursion step I check for the best score from that position on, assigning that score to either player alternating between them. Something like: Best_score_from_pos(pos, alice) = max( 1 stone + Best_score_from_pos(pos+1, bob), 2 stones + Best_score_from_pos(pos+2, bob), 3 stones + Best_score_from_pos(pos+3, bob), ) $\endgroup$ May 28, 2023 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.