boymimbo
boymimbo
Joined: Nov 12, 2009
  • Threads: 16
  • Posts: 5098
August 6th, 2017 at 1:23:48 PM permalink
The logical move from the computer would be to move directly move away from you and then report its position such that it maximizes the deviation of your path, which to me, seems to be at the top or bottom of a sphere (as any other would cause you to deviate less), alternating each time.

If your strategy is to point yourself at the computer's known position then you would be deviating up and down each time getting further and further behind.
----- You want the truth! You can't handle the truth!
BobDancer
BobDancer
Joined: Jun 22, 2013
  • Threads: 13
  • Posts: 140
August 6th, 2017 at 1:49:06 PM permalink
Doesn't being on an infinite plane preclude spheres?
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 24
  • Posts: 1315
August 6th, 2017 at 2:02:39 PM permalink
Say you move the grid system so you are at (0,0) and the computer at (say) (50,0). The computer moves to (51,0) then it could report (roughly) (51,1) or (51,-1). However if it reported (50,1) last time and now flips to (51,-1) then you would know where the computer is.

Now this is why I asked whether you assumed game theory - because if you know the computer is always going to be consistent, then you could calculate more accurately where it is. For instance your worst case scenario is going to (-1,0) while it has gone to (1,0). On the 2nd move it goes to (2,0) and reports (2,1). Your correct strategy is actually to head back to (0,0) - you then know you're not more than 2 away. Thus the computer shouldn't report (2,1) but something else!
boymimbo
boymimbo
Joined: Nov 12, 2009
  • Threads: 16
  • Posts: 5098
August 6th, 2017 at 6:19:09 PM permalink
Quote: BobDancer

Doesn't being on an infinite plane preclude spheres?



Circles. Damnit, I meant circles, or two dimensional spheres!
----- You want the truth! You can't handle the truth!
boymimbo
boymimbo
Joined: Nov 12, 2009
  • Threads: 16
  • Posts: 5098
August 6th, 2017 at 6:21:10 PM permalink
Quote: charliepatrick

Say you move the grid system so you are at (0,0) and the computer at (say) (50,0). The computer moves to (51,0) then it could report (roughly) (51,1) or (51,-1). However if it reported (50,1) last time and now flips to (51,-1) then you would know where the computer is.

Now this is why I asked whether you assumed game theory - because if you know the computer is always going to be consistent, then you could calculate more accurately where it is. For instance your worst case scenario is going to (-1,0) while it has gone to (1,0). On the 2nd move it goes to (2,0) and reports (2,1). Your correct strategy is actually to head back to (0,0) - you then know you're not more than 2 away. Thus the computer shouldn't report (2,1) but something else!



Well it is always going to go one unit away from you. If you start thinking game theory, then the computer should just randomly pick one unit up or down from you. In that way, you couldn't assume an average and would have to go for the direction because you can't predict which one it will choose.
----- You want the truth! You can't handle the truth!
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 972
  • Posts: 16345
August 7th, 2017 at 7:29:30 AM permalink
I investigated this idea of just following the computer's last reported position, as it can never be far from his true position...

Let's say the game as been played awhile. Let's define a set of coordinates relative to YOUR position. Let's say the current state is:

You: (0,0)
Computer: (50,0)

The computer tries to both distance himself from you and throw you off to the side by moving to (51,0) and reporting (51,1).

The angle you should pursue the computer is atan(1/51) = 0.019605331 (in radians).

Your move should be to (0.999807822,0.019604075), again in radians.

Given that the computer is actually at (51,0), the distance between you is now 50.00980298.

So, over time, this distance would increase. However, at some point would it reach an equilibrium? Let's see what would happen if the computer were 500 units away and repeated the same strategy. Again, readjust the coordinates so you're at (0,0)

The angle you should pursue the computer is atan(1/501) = 0.001996005 (in radians).

Your move should be to (0.999998008,0.001996004), again in radians.

Given that the computer is actually at (501,0), the distance between you is now 500.000998.

So, the computer is still getting away from you. Remember, the computer knows your position. I don't immediately see how the computer just can't keep adding to his distance minute amounts every time.

Sorry, but but this post adds nothing of value to the discussion.
It's not whether you win or lose; it's whether or not you had a good bet.
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 24
  • Posts: 1315
August 7th, 2017 at 10:35:57 AM permalink
^ The case you have is similar to mine - so I've run it through a program and the computer continues to get away. (I've used right angled triangles and sqrt.) Essentially the fractions the computer gains each turn don't decrease enough to stay under 100. Assuming you return to (0,0) thus ensuring you are 2 away and the computer moves to (3,0) reporting (3,1) then it subsequently takes 676798 turns to reach a distance of 100.

I'm guessing the player may be able to play better by looking for a pattern, but I can't see a strategy better than going towards the computer's reported place.


(Trial no., Player X, Player Y, Computer's position, New Distance.)
X: 19 PX: 0.9697950116046666 PY: 0.2439213714841422 CX: 3.9758509297645324 ND: 3.0159359772002223
X: 52 PX: 0.9805211694567034 PY: 0.19641343194206107 CX: 4.992128897508099 ND: 4.016413175957989
X: 103 PX: 0.9863847731292482 PY: 0.16445388210304296 CX: 5.997941553676444 ND: 5.014254325818281
X: 175 PX: 0.9899166840088099 PY: 0.14165083381682625 CX: 6.988428217012168 ND: 6.000183794709567
...
X: 637194 PX: 0.9999489887003615 PY: 0.010100494895005084 CX: 98.99999941536115 ND: 98.0000509471707
X: 656797 PX: 0.9999500037417145 PY: 0.009999500834789662 CX: 99.99999202587678 ND: 99.00004252713492
X: 676798 PX: 0.9999509887862765 PY: 0.009900506317758177 CX: 100.99998491922588 ND: 100.00003442053956
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 972
  • Posts: 16345
August 7th, 2017 at 11:31:56 AM permalink
I've toyed around with some other player strategies but nothing seems better than heading right towards the last stated position. It seems to be logical that if you know somebody is within radius 1 of point x, then you head straight towards x if the object is to minimize the distance between your point and his.
It's not whether you win or lose; it's whether or not you had a good bet.
gordonm888
gordonm888
Joined: Feb 18, 2015
  • Threads: 20
  • Posts: 518
August 7th, 2017 at 11:46:25 AM permalink
I think there are two very interesting parts to this problem.

First, given that the opponent is a computer and must be guided by a rule-based algorithm, is there an optimum algorithm or set of rules to give the computer such that it maximizes separation, and what is it?
- needs to cover where to move and what (false) position to report

Secondly, how do you counter the algorithm to minimize the growth of separation, what is your chase algorithm.

Chase algorithm: I think that the player cannot do better than to move one unit directly towards the last reported position.

Computer flight algorithm:
Definitions: an = the computers position (coordinates) after n moves
bn = the computer's (false) reported position (coordinates) after n moves
The computer's first move is in a random direction away from (0,0) The computer's first reported position is (0,0) so as to minimize information. Here are two possible algorithms to stimulate the discussion.

Algorithm A
1. On subsequent moves the computer must move 1 unit in a direction that maximally increases the separation from the players latest position.
2. After its nth move, the computer must report a bn that is as close as possible to bn-1 because this minimizes the information given to the player.
Algorithm B
Based on player's current position, the computer must pick a combination of a new location an and a new reportable location bn such that when the player moves one unit directly towards bn it maximizes the separation distance from an

I think if you develop the algebra for Algorithm B, and then extend its logic for n steps into the future (like a chess computer looking n moves ahead) you will develop a flight algorithm and an expression for maximum distance from the player that converges on some finite number.
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 24
  • Posts: 1315
August 7th, 2017 at 2:29:38 PM permalink

Let the computer be L units ahead of the player at C (L,0). It moves to C' at (L+1,0) and reports (L+1,1).
The player proceeds from A (0,0) and after traveling 1 unit gets to position X.
Since the distance AC' = L+1 and the computer says it's 1 away, the Y co-ordinates of the player's position is approx 1/(L+1).
The angle alpha (BAX) is therefore 1/(L+1). Construct two triangles to show that XBY = alpha/2.
Thus XY is about BY * (aplha/2) = 1/(L+1) * 1/2(L+1) = 1/2*(L+1)^2.
Using similar logic shows that beta = 1/L(L+1), so YZ is of order 1/2(L+1)(L+1), i.e of order L^(-3), so can be ignored.

Thus when the computer is L units away the difference increases each turn by about 1/2(L+1)(L+1).

NOTE: The next move has L increasing by the small amount, thus it is not the total of 1/N^2 (which = pi^2/6), but there are multiple turns before L increases by 1.
I am guessing that if the delta is 1/2 L^-2 then the total is the sum of 1/2 N^-1, and this keeps growing.


X: 767 PX: 0.9958907041363316 PY: 0.09056326746999395 CX: 10.996629560282782 ND: 10.001148902713743
X: 5748 PX: 0.9988681228513349 PY: 0.047565461749577584 CX: 20.999861792789293 ND: 20.001050228876725
X: 44310 PX: 0.9997026901599955 PY: 0.02438301225993199 CX: 40.99996667773417 ND: 40.00027141916553
X: 347835 PX: 0.9999238007552851 PY: 0.012344743136443827 CX: 80.99996814055501 ND: 80.00004529225346
X: 2756487 PX: 0.999980711177106 PY: 0.006211060596153274 CX: 160.99999278648622 ND: 160.0000121958631
X: 21948192 PX: 0.9999951475978428 PY: 0.0031152497120672776 CX: 320.99999679776766 ND: 320.00000166533357
X: 175173204 PX: 0.9999987831048686 PY: 0.0015600605058695564 CX: 640.9999992580307 ND: 640.0000004768273
X: 999439751 PX: 0.9999996186192375 PY: 0.0008733621124956036 CX: 1144.9999997844782 ND: 1144.0000001661922

  • Jump to: