Conference rusure::math

I had to reread your note several times to figure out what you were talking
about.  But now that I think I understand...

Perhaps tomorrow I'll program this game in X so we can play with it.  It'll
be *alot* easier to think towards a proof if we have a model to play with
first.

    This would also make an interesting contest between two people.  
    One person "guesses", i.e., selects lines trying to score as many 
    points as possible, and another "decides", saying if each guessed line
    is solid or dashed, trying to minimize the guesser's score.  
    
    The person who "decides" has to keep the entire board in mind, for if
    s/he/it decides wrong, an illegal configuration may ensue.
    
      John

You start without knowing anything.  You pick a segment.  Murphy's watching, so that segment is solid.

So, you make sure the next segment you pick is on a different square.  Murphy's persistent, so every
segment you pick is solid !

Since you're going for the perfect score, you can't risk picking a second segment on any square.  So
eventually, you've picked lots of solid segments all over the board, and you dare not pick anything
else.

Hence I don't think perfect play is possible.

However, discussing "best" strategy is still an interesting question.

/Eric

    First, please don't run your responses past column 80.  In return, I
    won't post any 10,000-line entries.
    
    I don't think it's sufficient to simply say "every segment you pick
    is solid".  It may be that a perfect player[/computer] can select lines
    in a manner that IF the next segment selected is solid, THEN ultimately
    the completed board will be illegal, e.g., may end up with 3 broken
    lines around a square.  Thus, it may be that a certain pattern of
    selected lines "forces" the rest of the lines into a known state.
    If this happens early enough, the selector can select what must be
    broken lines.
    
      John

First of all, I'm on a b&w ews system, and decw$notes makes my
send window n pixels wide, so I have no idea when 80 occurs.  I've
just narrowed the window, so I hope it's 80 in your font size now!

John, I don't see how any person or computer can necessarily
glean enough information to play a perfect game.  Unless some
dashed segments are picked, there's no way to safely complete
*any* square.

Think along as I think out loud here:  I start with blank board.
I pick a segment.  No matter what segment I pick, I have no idea
whether it will be solid or dashed.

Let's suppose it's solid, since it might be, and that produces
the case that I am telling you prevents the perfect game from
being played.

o.k. so we've picked a solid segment that is a member of one or
two squares depending on whether it's an edge or not.

To play our perfect game, we dare not pick another segment in
either of those squares, so we pick one in a different square.
Again, it might be solid.  Suppose it is.  So again, we go to
a new square.

In order not to risk losing a square, we're always forced to pick
from untouched squares, and we never have any information about
these squares, so we're always picking in the dark.

So, eventually, we might very well have picked all solid segments,
one from each square on the entire board.  There's nothing safe
we can possibly do next, right ?

/Eric

> First of all, I'm on a b&w ews system, and decw$notes makes my
> send window n pixels wide, so I have no idea when 80 occurs.  I've
    
    I don't know what "b&w ews" is, but you've got about 10 characters to
    spare, thanks.
    
> John, I don't see how any person or computer can necessarily
> glean enough information to play a perfect game.  Unless some
> dashed segments are picked, there's no way to safely complete
> *any* square.
    
    This is what I'm thinking of:
    
    		.--.  .
    		      |		[1] Here we are, playing vs. Murphy
    		.  .  .		    and of course have chosen only
    		|     |		    solid lines so far.
    		.  .  .
    then:
    		.--.  .
    		      |		
    		.  .  .		[2] Oh, drat, there goes our perfect game!	
    		|     |	
    		.--.  .
    then:
    		.--.  .
    		      |
    		.--.  .		[3] Impossible!  Murphy's cheating!
    		|     |
    		.--.  .
    
    In case [1] we're guessing away and find ourselves in a box, so to speak.
    So we make a wild stab down at the lower left, and alas we find we can't
    box in a square with a solid line.
    
    At this pint we decide to go for a "high though not perfect" score, and
    proceed to select what must be dashed lines.  Except Murphy tries to
    keep us from "scoring" the top left box by creating a solid second line.
    
    This is not right, since it results in 3 solid lines around the lower
    left box.  Murphy CANNOT force you into a solid line here, he MUST give
    you a dashed line.
    
    What I hypothesize, but cannot demonstrate, is that there are similar
    cases where Murphy is FORCED to show you dashed lines without your
    having to ruin your chances of a perfect game.
    
    Now I can't demonstrate such a situation but perhaps only because I
    haven't tried enough complicated arrangements.  Or maybe it truly isn't
    possible.  So far the question remains open.
    
      John

I never intended Murphy to cheat.  I'm saying you'll have nothing to work
with.

But I guess you're suggesting that even though every square has exactly
one segment showing, and it's solid, we may have a situation where some
square's other solid line is determinable.

In other words, if we tediously try a solid line in each spot on each
square, there will be forced arrangements.

Maybe it's time for me to write an X program...

/Eric

> But I guess you're suggesting that even though every square has exactly
> one segment showing, and it's solid, we may have a situation where some
> square's other solid line is determinable.
    
    That is precisely what I am suggesting.  Mind you, I don't believe it,
    but that is a possibility that must be demonstrated or refuted.
    
    An alternatative approach is to look at "near perfect" solutions.
    In an NxM square, what is the -best- one can score with optimum play?
    For small N,M I think the results can be enumerated.
    
      John

We can gain some insight - but, I think, no help - by detailing a simple 
case, e.g. the 1x2.
	+-1-+-5-+
	2   4   6
	+-3-+-7-+

There are 2^7 = 128 possible shadings of these edges, *but only 18 legal 
ones* (i.e. 2 choices for edge 4 * 3 on each side). To enumerate:
(#4 shaded)	(#4 solid)
	1256	347
	1257	346
	1267	345
	1356	247
	1357	246
	1367	245
	2356	147
	2357	146
	2367	145

We can gain 1 bit of information by choosing #4 first (as opposed to 
somewhat less for a different 1st choice), but we still have nine patterns 
to identify, and if Murphy lives we hit solids on all the rest, giving us 
nothing. The probability of scoring both squares is (2/3*1/2)^2 for the
4-solid case and (1/3)^2 for the 4-shaded case, 1/9 either way, and each
square is independent of the other.

My conclusion is that there is no really rational way to play the game. You
guess, and either you get lucky or you don't. You can minimize the guesses, 
but there is nothing you can do to maximize your score.

.3> Since you're going for the perfect score, you can't risk picking a second
.3> segment on any square.  So eventually, you've picked lots of solid segments
.3> all over the board, and you dare not pick anything else.
.3> Hence I don't think perfect play is possible.

Eric's created an oracle that *chooses* whether the player-chosen edge is
solid or shaded. It always displays solid lines, unless that would create
an invalid configuration.  This forces the player (who is seeking a perfect
game) to play a certain way (as described in .3 and .5).

Is any set of "lots of solid segments all over the board", with no two on
the same square, necessarily part of a valid configuration?  (my guess: yes).
Is the oracle free to choose the next edge as solid, thereby ruining the
perfect game?  (my guess: yes).


.9> The probability of scoring both squares is (2/3*1/2)^2 for the
.9> 4-solid case and (1/3)^2 for the 4-shaded case, 1/9 either way, and each
.9> square is independent of the other.

Given the 4-shaded case, the probability of scoring both squares is:
	(1/3 + 2/3*1/2)^2 = 4/9
So overall, the probability is: �*( (2/3*1/2 + 1/3*0)^2 + (1/3 + 2/3*1/2)^2 )
	= 1/2*( 1/9 + 4/9 ) = 5/18.

But we can do better than that!  In fact, we can get both squares with
probability 1/2; and this is the best possible.  On way to do this is to
choose edges 1, 2, and 3.  We've determined the 4 edge, and we've either
lost (if edge 4 is shaded), or won (if edge 4 is solid).


DOTS is available from Lee Publications, 1100 W. Broadway, P.O. Box 32120,
Louisville, KY,40232.  I think the price is about $2.  I have a half-empty
book of DOTS in my office (ZKO2-3R71).