Card Game Algorithm

Question

I will be asked to develop a card game in language c between two players, where the player can choose the largest or the most right card from the list of cards: If the list is [2,14,12,6,20,10], the player can choose 2 or 10. Finally, the player with the highest score (the sum of the cards selected by the player) wins the game. Is there a way to optimize the player’s choice, knowing that the best choice is not always the maximum (for example: choosing 10 in the above case allows another player to choose 20). (Sounds like a recursive function ...)

Answer 1

I do not know about maximization. but if (at the beginning) there is an even number of cards, there is a simple algorithm for the first player:

First mark the cards in red and black (alternately), so that the cards on the edges will have different colors. Summarize (separately) black cards and red cards and choose the color that you prefer. Assuming (for example) that the sum of black cards is higher, continue to choose black cards, and your opponent will have to choose red cards - and you will win!

Answer 2

Playing optimally, for this game, players will receive points. Let the input be a list L and define F(i,l) and S(i,l) as the first and second player ratings for the part of the list, starting from the ith element with a length l. If (part) of the list has a length of 1, then this card will go to the first player.

 F(i,1) = L[i] S(i,1) = 0 

If (part) of the list is longer than the first player wants to maximize the amount of the card that he chooses, and that he will receive as the second player with the list of remaining ones.

 F(i,l) = max( L[i] + S(i+1,l-1), L[i+l-1] + S(i,l-1) ) 

Since the second player does not select a card, he will receive the fact that the first player is on the shorter list.

 S(i,l) = F(i+1,l-1) if L[i] + S(i+1,l-1) >= L[i+l-1] + S(i,l-1), or F(i,l-1) if L[i] + S(i+1,l-1) < L[i+l-1] + S(i,l-1). 

The implementation is performed by filling in two arrays n^2 for F and S The result is F(1, length(L) ) .

Answer 3

We had this exercise in one of our programming courses, and this is the solution I came across (in C ++, but it easily translates to c). It uses dynamic programming with O (n ^ 2) and O (n) times. First, he calculates the optimal game score for each subscriber of length 1, then uses them to calculate ratings for lists of length 2, etc. Finally, there are two lists of length n-1, and we select the one that gives the best overall score.

 int f(const vector<int>& numbers) // return 0 if left is optimal pick, 1 if right { vector<int> s(numbers); for(size_t len = 1; len < numbers.size() - 1; ++len) for(size_t i = 0; i < numbers.size() - len; ++i) s[i] = max(numbers[i] - s[i + 1], numbers[i + len] - s[i]); return numbers.front() - s[1] < numbers.back() - s[0]; } 

Answer 4

@asaelr's answer is simple and clear, this is a really good trick for this problem. However, this decision can only guarantee that the first player will not lose, cannot make sure that he earns more points than the opponent. If we want an optimal solution, we must use DP. For example: {3, 2, 2, 3, 1, 2}, using the trick we can win 2, using DP, we can win 3 points. A detailed explanation can be found here. Really nice article. http://articles.leetcode.com/coins-in-line/