Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

optimal game strat


Best Answer Quantum.Mechanic , 08 August 2014 - 04:52 PM

After further study, I realized that the first path to a goal generated may not be the shortest path. It needs to keep generating goals until no new or shorter paths are found. It seems this doesn't happen all that often, so it hardly affects the runtime.

 

Eliminating some of the low level structure, the full matrix including paths can be saved, at least as high as 256. Judging by the memory usage, it could probably go a bit higher.

 

Here's the results I have for 256. Hopefully they pass all of plasmid's tests this time.

Spoiler for Results for 256

 

Here's the latest code.

Spoiler for Perl code
Go to the full post


  • Please log in to reply
29 replies to this topic

#1 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 551 posts

Posted 25 July 2014 - 04:51 AM

in this two player game, each  player secretly picks two  numbers, one of  which is his own starting number and the other is his opponents goal number. numbers are allowed to be any integer value between 1 and 256. then both players reveal the numbers, and may use addition, subtraction, multiplication, and division, to try to get to the  goal number using only numbers they generate from their starting value.

for example, player A may pick start 36 goal 47, and player B may pick start 123 goal 123.

player A does 36/36 for 1. player B does 123/123 for 1.

player A does 1+1 for 2. player B does 1+1 for 2.

player A does 1+2 for 3. player B does 1+2 for 3.

player A does 36*3 for 104. player B does 123/3 for 41.

player A does 36/2 for 18. player B does 41+3 for 44.

player A does 104+18 for 126. player B does 44 +3 for 47. therefore player B wins.

note ties are possible if both players get it  in the same number of operations.

so you know the drill, whats the best starting value and worst ending value, assuming you don't know what your opponent is going to pick?


  • 0

#2 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 25 July 2014 - 07:38 AM

Nice problem.

 

Are you asking for the starting and ending values to chose, that would maximize your chance to win?

By this question I'm trying to clarify "worst ending value."

 

Also, by your example, can we conclude that only two numbers can be combined on each turn?

 

Thanks.

 

Spoiler for Very first thoughts


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#3 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 551 posts

Posted 25 July 2014 - 09:25 AM

close enough. best starting value to chose, and the worst goal value your opponent could chose given your starting value.

correct. you can only combine two previously generated numbers each step.


Edited by phil1882, 25 July 2014 - 09:26 AM.

  • 0

#4 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 26 July 2014 - 07:11 PM

It looks like this will be more of a programming exercise than anything.

And it looks like it won't be all that amenable to a simple greedy algorithm. (It would probably be solved with some sort of greedy algorithm, but not the simple one I'm thinking of.)

 

For example, getting from 1 to 7 would involve

1+1=2

2*2=4

2+1=3

4+3=7

 

It takes two steps to generate 3 (1+1=2, 2+1=3) and two steps to generate 4 (1+1=2, 2+2=4).

But it does not take [two steps to make 3] + [two steps to make 4] + [a step to combine 3 and 4] = 5 steps to generate 7 because the 1+1=2 is shared by the generation of 3 and 4.


  • 0

#5 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 26 July 2014 - 10:17 PM

Agree. What it seems to boil down to is constructing a 255 x 255 matrix, looking for the smallest number in each column and selecting the row having the largest minimum, for the second answer, and the column through the smallest maximum for the first part. That's a lot of computing, once an algorithm is found to get from any A to any B in the fewest moves.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#6 wolfgang

wolfgang

    Senior Member

  • Members
  • PipPipPipPip
  • 780 posts
  • Gender:Male

Posted 27 July 2014 - 09:16 AM

Spoiler for As I see


  • 0

#7 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 27 July 2014 - 10:08 PM

Perl's dynamic arrays make things easy to program (relatively). This program works if you have a small range that you're working over -- if the maximum value of the numbers is 10 instead of 255 -- but would be horribly inefficient if you wanted to calculate it for 255. It does give an algorithm that would work in principle, though. If there were an easy way of eliminating redundant arrays and repeated terms within arrays (which I imagine there are a bunch of) then it might be feasible for 255.

Spoiler for code

Spoiler for output (omitting lines giving updates on progress)

Edited by plasmid, 27 July 2014 - 10:21 PM.

  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 28 July 2014 - 06:55 AM

Wondering if the "moves from A to B" calculation could be put into an Excel macro to paste into the cells of a 255x255 Excel array.
Just thinking.

Or maybe there's an Aha! Solution...

Wolfgang's answer answer has merit.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#9 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 29 July 2014 - 02:17 PM

I got the code a little more efficient (thanks to the magical ~~ operator in perl) so it could work with a max value of 30 instead of 10, running for a matter of hours, but it's still far less than the 255 in the OP.
The answer was surprising.

Spoiler for matrix

Spoiler for updated perl code

  • 0

#10 plainglazed

plainglazed

    Abuse of PoWers

  • Moderator
  • PipPipPipPip
  • 4756 posts
  • Gender:Male
  • Location:nc us

Posted 30 July 2014 - 05:57 PM

Spoiler for some thoughts

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users