Conference rusure::math

	Games can be incredibly complicated to analyze (eg: .0).   In Game
Theory, I suppose the art is to pick games which are simple enough to be
solved, but at the same time illustrate important general points.

	However, what can one say about Battleships?   Essentially, it falls
into the Mastermind / 20 Questions / Queries 'N' Theories family.   One person 
selects a member x from a set S (which may or may not be finite).   The other 
person asks a series of questions to which the other person has to respond 
truthfully, to identify x.   Normally, two games are in progress simultaneously,
and the goal of the meta-game is to guess the opponent's pattern faster than 
he guesses yours.   Otherwise the goal is to minimize the number of guesses 
necessary.   These two goals lead to different strategies.   Call these two
versions BTP (beat the player) and BTS (beat the system) respectively.

	S0 = S.   The question partitions Si into Ai & Bi.   The responder
reveals which of these contains x, and then S(i+1) is defined to be either
Ai or Bi accordingly.   When Sk = {x} the game is over, and the score is k.

	There are several sources of chrome.   Firstly, there is the 
militaristic garb in which the game is enshrouded.   This does not affect the
abstract structure of the game, and can be ignored.   Secondly, in the
versions of the game that I played when I were a youngling, one gained an
extra turn whenever one hit a boat.   In BTS, this is irrelevant, since at
the end of the game one has always hit everything once.   In BTP, the rule
tends to balance the game slightly, by allowing the losing player to have
more information about how far ahead the winning player is.   The question
of information is critical to the analysis of BTP.   Thirdly, and this is true 
of all games of this family, it's not normally possible to partition Si into 2 
sets of equal size.   The "interest" of the game comes from this feature.

	In BTS, we would try to partition Si at each stage into sets that are
as equally sized as possible.   (Simple communications theory suggests that
this is the way to minimize the expected number of questions required).
Ideally, one would do a complete analysis of the whole game tree, before
playing a single move, but since this is expensive, a reasonable heuristic
might be to play at each stage a move which minimizes | |Ai| - |Bi| |, and
worry about the next move afterwards.

	In BTP, the same strategy might be a good one.   However, it's more
complicated.   Suppose the opponent is winning, after n turns.   For
instance, let's say that |Sn| = 2 for his guessing, but the corresponding value
|S'n| = 4 for our guessing.   So he will take exactly one turn to finish.
Our expected value is 2 turns.   We must change our strategy, if possible, so
that |Ai| = 1.   This gives us a 25% chance of drawing the game, which we did
not have before using the balanced strategy   A similar tactic is involved in 
the endgame of Backgammon.   The point at which one enters this endgame, is
the point at which the game becomes simple enough to admit this analysis.

--------------------------------------------------------------------------------

	Getting rid of the tedious chrome, we can see an interesting game here.
Let S be the set of integers {1,...,m}.   A question is a partition of S
into {1,...,q} & {q+1,...,m}.   Normally, two games are played back-to-back
(ie, we are looking at BTP here.)   We can characterize a position at BTP
as [m,n], where one player has m possibilities to distinguish, and the other
has n.

	A game can end is a win, draw, or loss.   What can we say about the
probability of win, draw or loss for [m,n]?

Cheers,
Andrew.

> Q2.
> If player 2 uses an optimum strategy (T.B.D.) what is the expected value
>of number of shots for player 2 to sink the battleship?
>
> {Deciding the optimum strategy seems to be the key.
>
>  My first thoughts about such an algorithm were
>  (at each point in the game):
>
>  i)  Identify all the positions in which the battleship could be located.
>
>  ii) For each location of the battleship add 1 to the count for
>      each of the squares the battleship occupies.
>
>  iii) Select a square with the highest count.
>
>  It is not clear, however that this is optimum. Possibly the increased
>probability of hitting the battleship might be canceled out by the subsequent
>difficulty in locating the battleship after its been hit. 
>
>  For example, for the 1st shot C3 is the most likely to hit ( 6 chances in 30)
>whereas A1, A5, E1 or E5 are the least likely to hit (each have only 2 chances
>in 30). However if you do actually hit at C3 it is going to take longer to 
>sink than if you get a hit at ,say, A1. Maybe the problem is more subtle and it
>comes down to a minimax (JvN ?)like tree search?

	In the notation of .1, |S| = 30.   The nearest we can get to an 
balanced partition of S is |A| = 6, |B| = 24.   The heuristic says that we
should go for this one, if playing BTS.   The sequence of squares that I would 
try until I get a hit are as follows:

	C3, B2, D4, A4, B5, D1, E2, A1, E3

which splits the possibilities at each stage as:

A(i)     6   4   4   3   3   3   3   2   1
B(i)    24  20  16  13  10   7   4   2   1

	In fact, as I write this I realize that it's not sufficient just to 
uniquely identify the pattern, you have to destroy the boats as well.

Can anyone produce a better solution?

Cheers,
Andrew.

RE: .2

>The sequence of squares that I would 
>try until I get a hit are as follows:
>
>	C3, B2, D4, A4, B5, D1, E2, A1, E3

Given this sequence (or any other fixed sequence) the opponent can increase
the number of choices required.  I use this fact to good effect when I play
games of this nature.  As I prepare for the next game I review the choices
made in the previous game.  I create my new position such that the choices
made in the previous game would have missed as long as possible.

On the other hand, I deliberately attempt to avoid making the same choices
in the next game that I made in the previous one to preclude giving my
opponent the same opportunity.  Naturally none of this matters in a single
disjoint encounter.

 Thanks for the input on these problems:

 Concerning reply 1, I am not sure that there is not some purpose in
attempting to analyse "incredibly complicated" games. Always selecting simple
games is likely to bias us towards what is known and understood, attempting
the "incredibly complicated" - whilst probably doomed to failure - might at
least surface some ideas and principles that might not otherwise be discovered.

 There is also,I think, some benefit in the kind of "fuzzy" reasoning which
one is obliged to apply to "incredibly complicated" problems. The fact that
one might not be able to be completely rigorous in the analysis, or make
completely definitive statements does not preclude the analysis from
yielding usefull insights. Neither is "fuzzy" in this context a synonym
for loose or fallacious.
  
For what its worth the real world IS incredibly complicated, and I like chrome.   

The game we were playing was BTS (beat the system) and I am only
considering the BTS game - although we played BTP when I was a kid. BTP seems
much harder to analyse....

Q1.

 Trying to strip Q1 of the "tedious chrome" complained about in reply 1,  

Because our shots are random, the fact that the battleship is in a staight
line makes no difference to the probability of getting a hit on any shot,
and any information we might get from the result of a shot doesn't 
affect our subsequent shots.

So I believe the problem is equivalent to:

Given a bag of 25 marbles, 3 of which are white and 22 of which are black,
and marbles are taken from the bag one at a time without replacement, 
what is the expected number of marbles to be taken from the bag in order
to get 3 white marbles?

This is easily solved but the solution is extremely tedious to type,
particularly is ASCII. 


Q2.

My reading of replies 1,2 and 3 is that, whilst they represent the problem
and the suggested heuristic more succinctly, they:-

	1. Essentially propose the same algorithm as I suggested.

	2. Do not prove, or indeed analyse whether it is optimal in
	    minimising the expected number of tries.

Q3.

Does the possibility player 1 may lie about a result completely change
the nature of the problem?

My thoughts on this were as follows:-

For either player to play optimally he must assume that his opponent will
play optimally. (Any arguments ?)

Considering Player 1, he has to optimize his cheat so as to give player 2 the
least information.

It would appear that the earlier in the search tree that player 1 lies
the more he will confuse player 2, but if player 2 is playing optimally he will
expect some lying and adjust his strategy accordingly. 

A first cut at the distribution of the lies that would give player 2 the
minimum information might be (if N were large)

		1. Lie 1/2 the time on 1st guess 
		2. Lie 1/4 the time on 2nd guess 
		3. Lie 1/8 the time on third guess
                    .............
                   
		   Lie 1/ 2**N of the time on the Nth guess

As N became larger this approximates increasingly closely to the following
simple strategy for player 1

		" If I haven't already lied lie 50% of the time on this
                  go"

 
However all lies do not carry the same degree of "mis_information".

For example, discounting cheating, at any point in the game player 2 knows the
probability that his shot will be a hit. ( Because he knows all the possible
positions the battleship can be in (N), and the number of these positions 
that occupy a given square (n), so the probabilty he will get a hit on the
given square is n/N). This is also true when  cheating is allowed, because,
iteratively, if after allowing for cheating Player 2  can make a probabalistic
assesment for each position of the battleship he can hence make a probabalistic
assesment that he will get a hit on the given square - albeit after long and
tedious calculations).  

It would appear to me that for player 1 to convey the minimum information
to player 2 his decision whether or not to lie (assuming he has not yet
lied and is eligable to lie) should be a function of

      	a) Did player 2 truly hit or miss on that shot

	b) The respective probabilities for a hot or a miss on that shot.

Lets assume that (because both players are playing optimally) player 1
knows player 2 knows, and player 2 knows player 1 knows that the probability
of a hit on the square selected by player 2 is Ph and the probability of
miss on that square is Pm. Clearly Pm + Ph = 1.

We need to figure the optimum or "saddle point" frequency for player 1 to lie

	a) When player 2 actually misses : call this PLm 
	b) When player 2 actually hits : call this PLh

 ( Note PLm + PLh is NOT necc =1 )
 
Both PLm and PLh are functions of Ph.
   
It appears to me that figuring out PLm and PLh is the crux of this problem.

If they can be determined then player 1 will know them, player 2 will
know them, and figuring out the best way to sink the battleship again
seems to come down the same heuristic - fire at a square which the battleship
is the most likely to occupy. Of course figuring out the probability that
the battleship will occupy each of the squares is now much more tedious 
because probabilities have to be assigned to the the truth of the outcome of 
each shot as reported to player 2 by player 1 and "rippled" down the search
tree underneath.

 
Richard

Re: .4:

Replies .1 & .2 which I put in was (a) arrogant, (b) wrong.   These are both 
vices which tend to crop up when I'm tired, but it's exactly *then* that the 
inner censor is at his least acute, and I'm prone to submit notes which really
need more work.

Sorry.   No offence intended.

Unfortunately, when I'm alert (like now) I often have work to do (like now).

Cheers,
Andrew.

Re .5 OK.

Re .2

>	In the notation of .1, |S| = 30.   The nearest we can get to an 
>balanced partition of S is |A| = 6, |B| = 24.   The heuristic says that we
>should go for this one, if playing BTS.   The sequence of squares that I would 
>try until I get a hit are as follows:
>
>	C3, B2, D4, A4, B5, D1, E2, A1, E3
>
>which splits the possibilities at each stage as:
>
>A(i)     6   4   4   3   3   3   3   2   1
>B(i)    24  20  16  13  10   7   4   2   1
>
>	In fact, as I write this I realize that it's not sufficient just to 
>uniquely identify the pattern, you have to destroy the boats as well.
>
>Can anyone produce a better solution?

The algorithm proposed in .0 is still efficacious (if not optimum) after
hits have been made, and hence can be used to destroy the boat as well.

For example, suppose in your search the results were C3 (miss) B2 (hit).

The possibilities for the boat would then be

	A2,B2,C2
	B2,C2,D2
	B1,B2,B3
        B2,B3,B4

The counts for the squares we could then choose would be

  A2(1),B1(1),B3(2),B4(1),C2(2),D2(1)

So the algorithm would suggest B3 or C2 as equally good choices.

It turns out that either of these is in fact optimum. Suppose we choose
B3 then the ways the game can unfold, if the algorithm is applied, are as
follows:-

    B3 (hit) , B1 (hit)
    B3 (hit) , B1 (miss), B4 (hit)
    B3 (miss), A2 (hit).  C2 (hit)
    B3 (miss), A2 (miss), C2 (hit), D2 (hit)

This yields an expected number of 3 further shots to sink the boat.

However I now suspect the algorithm is NOT optimum, and that most likely
way to show this would be by counter example.

The most likely form of a counter example would be,

Using the notation of .2

If at any stage i we can identify possible partitions

	A(i,1), A(i,2).............A(i,l)

and partions A(i,x) and A(i,y) exist such that

	1) A(i,x) = A(i,y)
	2) A(i,x),A(i,y) >= all other partitions

then the algorithm is not optimum unless the expected values of the number
of tries is the same for all such A(i,x) and A(i,y).

I believe that such counter examples can be found, but rather than search
for them "by hand" I will write a quick program to do this when I have time.

Richard