optimal game strat

[phil1882]

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?

[Quantum.Mechanic]

Here's a concrete example.

I tried modifying the code so it generates a matrix of steps to get from each starting point to each goal, just like the matrix I posted earlier, and runs from 1 to 30 so I could directly compare the matrices they produce. They differ at some spots, one of which is the path going from 11 to 3. For some reason it took four steps and went 11/11=1, 11+11=22, 22/11=2, 2+1=3. Obviously a shorter path would be 11/11=1, 1+1=2, 1+2=3.

Apparently there are two equally short paths from 11 to 2: {11/11=1, 1+1=2} and {11+11=22, 22/11=2}, and the algorithm ended up storing the second path as the most efficient path to get to 2. However, since it didn't store the path to 2 that creates 1 as an intermediate rather than 22, it wasn't able to discover that you could reach 3 from a path going to 2 through 1 that had a useful intermediate already generated.

 

Yes, that was possible for earlier versions. The current version gives me this:

four_banger.pl 30 11 3

[...snip...]

Steps for 11 => 3 (not in order):
        11 / 11 = 1
        1 + 1 = 2
        2 + 1 = 3

[...snip...]

because it compares multiple paths to the same goal, and keeps the shortest. (In case of ties, it takes the path with the smallest max operand.)

[plasmid]

I was using the code from post #21; is there another version?

[Quantum.Mechanic]

I was using the code from post #21; is there another version?

Are you sure? Because starting at line 193, it has:

    # This result might already exist. Keep the new one if the path is shorter.
    if (not exists($m->{$result})
     or (scalar keys %$new_path < scalar keys %{$m->{$result}})) {
        # print STDERR "\tAdded $expression = $result\n";
        $m->{$result} = $new_path;
        ++$results_added;
    }

[plasmid]

Yep, using the version straight from the post and not the one I tweaked to output a matrix. That block even shows up if I show the code from the command line to make sure I didn't do something silly like forget to save the most recent version from the text editor. Ran it with command line parameters of 30 11 3 just like you did and I'm still getting the same four-step answer. Very bizarre that we're getting different answers from it; it should be completely deterministic.