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

#11 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 05 August 2014 - 11:08 AM

Just some random analysis...

 

Any choice of start and goal can be a winner.

 

If we have the matrix of shortest path lengths from each start to each goal, is it not the case that we would use some game theory, and randomly choose our start and goal values based on this matrix?

 

For instance, if choosing a starting value of 23 has a 1% chance of winning, and 24 has a 0.1% chance of winning, we should choose 23 ten times more often than 24. But we should still choose 24 sometimes, to keep the opponent honest.

 

While it might be interesting to note what the initial matrix looks like (what are good starting numbers and good goals), it seems the best approach is to iteratively generate start and goal vectors.


  • 0

#12 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 05 August 2014 - 12:28 PM

I wrote a Perl program. These results took about 5 minutes:

 

Spoiler for Results for 256

 

The Perl program is below. To avoid blowing up memory, it only keeps the paths long enough to compute the worst one for each start. However, it is easily tweaked to keep the longest path for each start value. There is also a speedup by limiting paths to less than the square of the highest allowed starting value. This makes a few paths a bit longer, but doesn't seem to affect the overall results much.

 

Spoiler for Perl code

Edited by Quantum.Mechanic, 05 August 2014 - 12:28 PM.

  • 0

#13 bonanova

bonanova

    bonanova

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

Posted 05 August 2014 - 02:30 PM

Spoiler for I am not good at game theory, but will give it a try


  • 1

Vidi vici veni.


#14 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1483 posts
  • Gender:Male

Posted 06 August 2014 - 07:21 AM

I've been trying to figure out what makes your code run so much faster, and I think I can more or less follow its logic but I'm not sure about one point. If you wanted to get from a starting point of 1 to an ending point of 7, you could do that with
1+1=2
2*2=4
2+1=3
4+3=7

With the algorithm, after you get one path with
1, 2, 4
and another path with
1, 2, 3
it looks like the first of those sets wouldn't allow you to add 4 in the next round because there is already a different path to reach 4, and the second of those sets wouldn't allow you to add 3 in the next round because there is already a different path to reach 3. (This is from the next if (exists($m->{$result})); line.) I'm wondering if it would have a way of discovering that path to 7?


For the most part our algorithms seem to agree, but when I set the max size for both algorithms to 30, mine said you can go from 25 to 13 in 4 steps (from the matrix in my earlier post) while yours said that 25 to 13 took 6 steps (when I commented out the
if ($start{$s}{$STEPS} == $start{$start_best}{$STEPS}) {
and subsequent close bracket surrounding the print statement). A path with four steps is:
25/25 = 1
25+1 = 26
1+1 = 2
26/2 = 13
  • 1

#15 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 06 August 2014 - 11:50 AM

I've been trying to figure out what makes your code run so much faster, and I think I can more or less follow its logic but I'm not sure about one point. If you wanted to get from a starting point of 1 to an ending point of 7, you could do that with
1+1=2
2*2=4
2+1=3
4+3=7

With the algorithm, after you get one path with
1, 2, 4
and another path with
1, 2, 3
it looks like the first of those sets wouldn't allow you to add 4 in the next round because there is already a different path to reach 4, and the second of those sets wouldn't allow you to add 3 in the next round because there is already a different path to reach 3. (This is from the next if (exists($m->{$result})); line.) I'm wondering if it would have a way of discovering that path to 7?
 

 

 

I see now that my algorithm doesn't merge paths. I'll go off and chew on that a bit, and see what I can do.


  • 0

#16 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 06 August 2014 - 04:52 PM

OK, now I've added path merging, and fixed a bug where some paths didn't progress. (Thanks plasmid for checking my work.)

 

Here's a run with 256, also printing out details for a worst start/goal pair of (195,170), and some other stats that might be interesting.

Spoiler for Results

Note that order is not preserved in the path listing. This can be done, but it takes more work, and is usually thrown away.

 

Here's the code, much of it just for recording info for stats.

Spoiler for Code

Note that it has to dump the full list of paths after each start value. Otherwise, the memory blows up.

 

I've also limited the upper end to twice the $last value. There may be a few rare results that find a shorter path via a large power, but I can't prove or disprove this. Anyone have a counter example?


Edited by Quantum.Mechanic, 06 August 2014 - 04:53 PM.

  • 0

#17 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1483 posts
  • Gender:Male

Posted 07 August 2014 - 04:12 AM

Unless I'm reading it incorrectly, under Best starts with 10 worst case steps, it seems to say that it takes 10 steps to get from 9 to 13. But that's clearly not optimal.

It isn't giving me quite the same answers when I tried running the code. I set $last to 20 and forced $start to just be 9, and it said the worst case was 9 => 14 in 9 steps. Setting $my_start and $my_goal to 9 and 14 and rearranging the operations, it seemed to have taken
9/9 = 1
9-1 = 8
1+1 = 2

9+9 = 18
18+9 = 27
27+8 = 35

18+1 = 19
19+2 = 21

35-21 = 14

It didn't pick a path like
9/9 = 1
1+1 = 2
2+2 = 4
9+4 = 13 (to get to 13 in four steps)
13+1 = 14 (to get to 14 in five steps)

My best guess about what's going on is that, when it goes through the "generate" subroutine, it just looks at all the numbers that it reached so far and finds some combination of two numbers that have been reached that leads to a number that hasn't been reached yet, without regard to the number of steps it took to reach the intervening numbers. So for example to reach 14: after one round of "generate" the algorithm will have reached 9+9 = 18 and 9/9 = 1. In the second round it could reach 9-1 = 8 and 1+1 = 2 and 18+9 = 27 and 18+1 = 19. In the third round it could reach 27+8 = 35 and 19+2 = 21. Then in the fourth round it could reach 35-21 = 14. So it only takes four rounds of the generate subroutine to reach 14 via that route which requires nine operations, as opposed to five rounds of generate to reach 14 with the five operations shown above. Essentially, it finds the path that invokes generate the fewest number of times rather than the path that uses the smallest number of operations.
  • 0

#18 bonanova

bonanova

    bonanova

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

Posted 07 August 2014 - 05:25 AM

Does it blow memory to keep a tree structure for each starting number?

That's the same storage requirement as a 255x255 matrix.


  • 0

Vidi vici veni.


#19 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 07 August 2014 - 09:07 AM

My best guess about what's going on is that, when it goes through the "generate" subroutine, it just looks at all the numbers that it reached so far and finds some combination of two numbers that have been reached that leads to a number that hasn't been reached yet, without regard to the number of steps it took to reach the intervening numbers.

 

Doh! Yes, of course. With path merging, there will be longer and shorter ways to get the same result.

 

So I need to either run them all, and find the shortest; or generate in order by shortest new path length. The latter should be less space and less run time.


  • 0

#20 Quantum.Mechanic

Quantum.Mechanic

    Junior Member

  • Members
  • PipPip
  • 86 posts

Posted 07 August 2014 - 09:21 AM

Does it blow memory to keep a tree structure for each starting number?

That's the same storage requirement as a 255x255 matrix.

 

Possibly not. One problem I've seen is that allowing intermediate numbers larger than the upper limit (e.g., 256) generates a lot of intermediate results of little use, which could be trimmed. And this is Perl, so the overhead for arrays and hashes is larger than you might expect. From http://perlmaven.com...l-variables-use, in bytes:

                          size    total_size
SCALAR                       24    24
ARRAY                        64    64
HASH                        120   120

Those are empty, unassigned variables.

 

When the structure for each start number is filled out, it could be trimmed down to the useful bits and saved long term.


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users