Math Problem/Algorithm

[metrologist]

Perhaps posed more of a computer program algorithm...for 2 players. I think this was the way it went...

There is a series of random numbers. The players alternately select a number from either end of the list until all numbers have been selected. The player with the highest sum wins.

Proposed solutions:
Add the first and second to last number; add the second and last number; whichever sum is higher tells you from which end to select your number.
No solution because it depends on who goes first or there are other variables that dominate.
Other solution.

[u666sa]

You radomize and then get random number.
You'd have stack for each player. You'd push random number to one stack, switch to other stack, get random number and push it there, and then rinse and repeat however many random numbers you want to have for each player time two.

Then you pop from stock and add all numbers up. Do this for each player. Whoever has highest sum wins.

It's as simple as that.

There is a catch however, that sum variable has to be big enough to hold entire sum. int64 at least.

[ledtester]

I think you can use dynamic programming.

Suppose the numbers are a[0], a[1], ..., a[n].

Let S[i,j] (where i <= j) be the best way to play the game on the numbers a[\i], a[i+1], ..., a[j].

Given you know S[i,j] you can find the best plays for intervals which are one larger, i.e. S[i-1,j] and S[i,j+1].

So you only have to solve a quadratic number of boards.

[EPAIII]

Random numbers? The problem seems to be very vaguely stated.

Are they sequential? Or with random gaps? Or regular gaps?

Can the players view all of the randomized list before beginning? If not, what parts?

Does the list have an even or an odd number of numbers?

I wouldn't waste any time on creating an algorithm until all the details are fully stated. Who knows which one may be important.

[metrologist]

It's as ledtester stated

a[0], a[1], ..., a[n]

where each a[n] is a random number, and n is also a random number.

So in programming, I assume the list is an array of random numbers, and the programmatic algorithm just has to deal with what it's fed.

[Nominal Animal]

There is a series of random numbers. The players alternately select a number from either end of the list until all numbers have been selected. The player with the highest sum wins.

The key question is whether each player sees the entire list, a partial list, or just the currently available two numbers.  That determines whether you need an offline (sees everything) or an online (only sees the values to choose from) algorithm.

A greedy algorithm takes the option that yields the best immediate result.  These are typically only used when it can be mathematically proven that it leads to an optimum or an acceptable solution for all possible inputs, but can also be used to implement "strategically easily beatable" computer opponents.

A brute force algorithm examines all possible ways the rest of the game could proceed, and chooses the "best" option among those.  "Best option" is the one that maximizes/minimizes some scoring criteria; here, it could be the difference in scores for the two players, or perhaps the number of sub-paths where the computer loses.

For learning purposes, you'll want to implement more than two algorithms, with different strategies, and let each unique pair of algorithms play a set number of randomized games against each other.  Record the scores separately based on which algorithm made the first choice, how many rounds it took, and what the difference in scores was.  You'll learn a lot about this particular "game" at hand.

To learn how to apply mathematics to find a winning strategy for a player algorithm, look into combinatorial game theory, and at least initially assuming the players can see all numbers left when making their next choice.

[John Coloccia]

I feel like there is more to the original problem.  If it's truly just random numbers, and it's turn based, and you know nothing else, and once a slot is picked it's gone, I believe there is no strategy. The list is irrelevant because the number is random, so it may as well be just a random number from wherever.

[metrologist]

The program is fed the entire list, so the entire array can be accessed by the program.

Looks like the solution I posted is almost like a greedy algorithm but not really.

[John Coloccia]

The program is fed the entire list, so the entire array can be accessed by the program.

Looks like the solution I posted is almost like a greedy algorithm but not really.

Brute force would be to created a weighted, binary graph. 0 at the top. Left/right corresponds to turn.

You can make it more memory effecient by culling paths which are definite loosers....no reason to explore beyond that. But that's a pretty heavy handed algorithm.

But for sufficiently small lists, it works. At least I think it does...   Lol.

I've only thought about this for about 30 seconds. It's there a better way? Seems like an interesting problem!

[u666sa]

a[0], a[1], ..., a[n]

where each a[n] is a random number, and n is also a random number.

Does n a random number at the start of the program or is it a random number each time we loop?

[metrologist]

The list of numbers is finite and static at the start.

[u666sa]

So we have

Code: [Select]

static int n = random();
int64 resultA = 0;
int64 resultB = 0;
std:stack<int> stackA, stackB;


std::srand(static_cast<unsigned int>(std::time(nullptr)));

for (int i=0; i<n; i++) {
  stackA.push( std::rand() );
  stackB.push( std::rand() );
}

for (int i= n-1; i > -1; i--) {
  stackB.pop() + whatever math here to determine who wins
}