Conference rusure::math

    Go:  Is it not the case that two successive passes finish the game?
    In that case, say your opponent is ahead, and it would hurt you
    to move, then you don't have the option of passing.
    
    /Bevin

    (Simon Clinch)
    
    Attempted counter-example:
    
    Consider the game where two players each have a lighted cigarette
    and between them stands a cup with a tissue covering the opening
    completely and secured by an elastic band.  A coin is placed in
    the centre of the cup.
    
    At each turn,  a player places the cigarette on the tissue and the
    move is legal if and only if it decreases the area of the tissue
    that covers the opening by a noticeable amount.
    
    A player loses if his burn causes the penny to drop.
    
    Clearly:
    
    	1. A draw is impossible.
    
	2. A pass cannot hurt
    
        3. You cannot force a win from the first move.

    The problem with .2 is that it doesn't say what the consequence
    of an infinite series of passes is.  I suspect it would have
    to count as a draw...
    
    /Bevin

    The problem with .2 is it says "A pass cannot hurt.", but the theorem
    requires that an EXTRA MOVE not hurt.  In this game, an extra move
    can hurt.
    
    
    				-- edp

    The "forced-win" theorem for Go is something like this:
    
    Theorem:  In the game of Go, optimal strategy does not lead to
    	a win for white [black plays first in Go].
    
    Proof:  Suppose that there was a forced win for white.  Then
    	black should pass at his first move, forcing white to play
    	the first stone.  But now, if white plays a stone, then black
    	will win; so white will also pass, and the game will be a
    	draw.  
    
    	This contradicts the assumption that there is a forced win
    	for white.
    
    -Neil

    Depends on whether two passes or two consecutive passes makes the
    draw. If the latter, you could have a lot of pass-move-move-pass-
    sequences, each of which restores the original turn to move.

    re: 0  Example 2: Chess
    
    I do not totally agree with the statement that with perfect play
    the second player might win.  By having the first move, white possesses
    an initiative which is not enough to win outright with perfect play
    by black.  Because of the possibility of "zugswang" in black's position
    to oppose that initiative, an extra move can be detrimental to black.
    An extra move for white, along with the given initiative, could
    only increase white's advantage.  For white to be in a position
    of "zugswang", would mean inferior play and not perfect play by
    white.  Therefore, white can at least draw or win, and black can
    only hope to draw with perfect play.
    
    Steve

In GO, two passes does not necessarily end the game.  It's a revokable
declaration that the game is over.

After two passes, the players count up their individual territories.
However, there may be a dispute !

In the case of a dispute, let's say white claims a "black territory" is
actually dead black stones in white territory.  Hence white believes
he can kill black.  Hence white believes he can reduce the black
stones to less than two eyes.

The Japanese rules handle this dispute by saying that PLAY RESUMES,
with white moving first, and black being REQUIRED to place a stone
for each one white places.  This requirement neatly allows the
score to remain the same even if white's claim turns out to be
wrong.

So play will resume and continue until either the black stones have
been killed, or the situation is reduced to one in which both players
again believe it is played out and hence they both pass again.

/Eric

    When I said "second player might win" in chess, what I meant was
    that because there is a situation in which first player can be
    HURT with an extra move, the game theorem can not be employed
    in chess to prove that the game is at worst a draw for the
    first player.  Hence the theorem doesn't help, and therefore
    with exhaustive analysis it still MIGHT turn out that
    chess is a loss for the first player.
    
    Perhaps your .7 proves a draw for first player using different
    reasoning.
    
    /Eric

    re:9 
    
    With perfect play, there is no situation where an extra move would
    hurt white, only black.

    Re .7:
    
    > For white to be in a position of "zugswang", would mean inferior play
    > . . . 
    
    Why do you say that?
    
    
    				-- edp

    It is possible that the opening position is "zugswang", and that
    white has to make the move...
    
    /Bevin

    Yes, put another way, it's possible that no matter what first
    move white makes, black can carefully respond so as to lead
    white into a zugswang position.
    
    /Eric

    Re: 12,13:  That's absurd.  You can't be chessplayers.  If anyone leads,
it is White with the initiative.

Re: 11:
This is somewhat lengthy, but chess is a complex game of SKILL.  Let me
explain the nature of the game somewhat.  One must understand that chess
is a game of give and take, plus and minus, checks and balances for each
move in a position, and each position has its advantages and disadvantages.
Some of the advantages to be considered in evaluating a chess position are
the following:

Material: One needs more than a king to checkmate.  Without getting into
          the relative values of the pieces, three attackers verses two
          defenders is an advantage for the person with three pieces even
          after a one for one exchange. In the majority of cases, a mere
          pawn is enough to win with other aspects equal.

Space:    Controlling more space allows greater mobility and scope for the
          pieces increasing their effectiveness.

Time:     A more difficult concept then above to explain. Typically, the
          measurement of quick development of the pieces in the opening 
          and the gaining of tempos or moves in the middle and end game.

King Position: How safe the king is from attack in the earlier
          portions of the game, and how effective it is in the endgame when
          there is no risk of immediate checkmate due to lack of material.

These advantages can change from move to move, and one type of advantage
can be converted to another.  Space can be given up on one side of the board
for a material preponderance on the other for attack.  Or material can be
sacrificed  to expose the king to attack or to gain tempos for an attack.
they all result in an initiative for the person with the greater advantage
to ultimately checkmate the opponent's king.

At the beginning of the game, the material is even, and the space is even.
Having the first move, White has an ever so slight initiative in time (one
tempo ahead) and is first to capture space.  With perfect play, Black being
one tempo behind can only match or oppose White's objective (to increase
the advantage enough to checkmate).  This would result in a draw with perfect
play.  To give White an extra move would give him/her an extra tempo (or
loss of tempo for Black) to increase his/her initiative and advantage. If
this is not enough to win outright, it may be enough to place Black in a
position of "zugswang" where the opposition is lost.  This would force Black
to concede either space, material or the king's life.  Worst case, White
would only draw with perfect play by Black.

Now to give Black an extra tempo would only reverse the roles where Black
would be one tempo ahead of White.  With perfect play, again a draw.  So
this is why I say for White to be in "zugswang" then White has lost the
initiative by way of losing tempos, material, space, jeopardized the king,
or a combination of these.  This is all the result of mistakes and inferior
play and not an example of perfect play.

Steve

    You're wrong - I used to be a reasonably capable player, played
    several hours a day for 8 years.
    
    There is a SERIOUS contention that white, by moving first, has to
    make the first commitment; and that black can always exploit that
    commitment.
    
    Just because the HEURISTICS of tempo, material, etc. give white
    a lead doesn't mean it is!  They are only heuristics and don't
    always give the right answer, as zugswang shows...
    
    /Bevin

re:.15

Chess is a game of position. When you talk about time and space, you are
talking about ways to characterize positions without fully understanding
everything about that position. This characterization is not exact. There
are positions that are symmetrical and the player with the move loses!
The opening position may be one of these 'double zugzwang' positions,
but it is far to complex to know! 

Phil Hays (U.S. Chess Federation rating of 1590 or so..)

    Re .15:
    
    The things you describe are only approximations.  We currently have
    no way to evaluate almost any position in its entirety; current
    descriptions of the game are therefore approximations.  There is
    no way of knowing that the approximations always describe EVERY
    single possibility adequately enough to say Black can never put
    a perfect White player in a position where an extra move would be
    bad.
    
    
    				-- edp

    The importance of zugzwang is frequently underrated. If it were
    not for the necessity to make a move every time, even the elementary
    ending of K+R vs K would be a draw. You don't believe it? Try to
    find a mate in a center position in which the weaker side only
    moves when the stronger side tries to take the opposition, or checks.
    
    To the contributor you said "you're obviously not a chessplayer":
    you're obviously not a game theorist!
    
    I will follow this with another reply containing a little endgame
    problem to illustrate some of the difficulties.

+---+---+---+---+---+---+---+---+
|8  |   |   |   |   |   |   |   |    Black (lower case) k,p,p
+---+---+---+---+---+---+---+---+
|7  |   |   |   |   | p |   |   |
+---+---+---+---+---+---+---+---+
|6  |   |   |   |   |   |   | k |
+---+---+---+---+---+---+---+---+
|5  |   |   |   |   |   | p |   |    WHITE is to play. What is the outcome
+---+---+---+---+---+---+---+---+    of the game with best play on both 
|4  |   |   |   |   | P |   | P |    sides?
+---+---+---+---+---+---+---+---+
|3  |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|2  |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|1  |   |   |   |   |   |   | K |    White (Upper case) K,P,P
+---+---+---+---+---+---+---+---+
  A   B   C   D   E   F   G   H

    re: 17
I was just stating some examples to show anyone who might not be that familiar
with the game.  I could have gone on with opening strategy, endgame technique,
critical squares, pawn structure, manuevering, relative values, commitment,
etc.  Chess is a game of position and manuevering like war.  The execution
of a sound strategy through tactics to maintain an initiative for White
and to strive for equality for Black.  You state " there are positions that
are symmetrical....".  Yes, they are symmetrical but are not even!

re: 19
The importance of zugzwang is as important as analysing a lost position.
It is the moves (mistakes) before it that need to be questioned.  I did
not say "obvious", and yes I am not a game theorist.

re: 20
If I was playing White in a tournament with this position, I would have
already resigned.  (Rueben Fine is shabby!)
                                                                        

When I read the chess example, the example states that "zugzwang" 
positions exist and an extra move can hurt.  Yes I agree.  Then the
example states "hence in chess, we cannot conclude that whoever moves 
first can force a draw or win, even with perfect play.  In other words, 
with perfect play on both sides, the second player might win."  Well, this 
seems to me that you are putting the cart before the horse.

Zugzwang is German for "move compulsion" or for our usage "force to move".
In master tournament play, "zugzwang" is very rare.  It is indicative of
a lost position reached by the results of mistakes by the player in such
position.  Statistics show that in master play, the majority of games won
are by White.  Ask any grandmaster which color they would prefer to play
in a game against a person of their strength and I'm sure 9 out of 10 would
say White.  The one who didn't might be looking for a psychological advantage
against a known opponent based on past experience.

Getting back to the example, how can one take a lost position out of context
of a game and conclude that Black could win with perfect play at the start
of the game?  The position of zugzwang is not the result of perfect play.
Is this the way theorists approach solutions to problems or is it a sign
of desperation based on a lack of knowlege of the problem?  I really seem
to be missing something.

Steve (Life member USCF, MACA, inactive for 8 years had ratings 1900-2100+)

re:.21

There is at least one position that is a even game in that whoever moves loses!
The position is even in the sense that both players have the same material and
see the same position!!!!!!!!!!!!!!!!!!!!!!!!!!!!! (what do you mean by even?)
The opening position may also be such a position. Yes known 'simple' zugzwang
positions are rare in real play, and double zug is a very rare beast. 
As it is possible that the opening is a double zug (prove it isn't!), the 
theorum given in .0 does not apply. I agree that it is unlikely that black
has a forced win, BUT I CAN NOT PROVE THAT.

Phil Hays

    The problem here is that the discussants are not using the same
    terminology. 
    
    There is a broad theory called Game Theory which applies to Chess,
    Go, Bridge, tic-tac-toe, and the stock market. In this space, Chess
    is known as a two-person, zero-sum game with perfect information.
    That is, there are two players whose fortunes are completely opposed,
    and (1) the entire history of the game is known to both players,
    while (2) there are no chance elements in the game. (In these last
    two characteristics Chess is completly unlike war.) There is a theorem
    about games of this specific type: There exists at least one strategy
    that one can select at the beginning of the game, independently
    of the opponent's choice of strategies, that will guarantee an optimum
    result. Now both White and Black have such strategies, and when
    both play their best, the outcome is a foregone conclusion; neither
    player can deviate from that strategy without risking a worse outcome.
    
    Chess is also complex enough that it is not possible to determine
    what those strategies are. The best one can do with finite resources
    of time and energy is to develop heuristic methods of play, which
    include such considerations as King safety, control of the center,
    etc. However, for a subset of the game, e.g. the example problem
    I cited in .-2, it is possible to calculate the optimum strategies
    for both sides. The example problem is tricky to evaluate: at first
    blush White looks like a winner, then further analysis makes Black
    look stronger, then more study makes it look drawish, then...
    But it is CERTAIN that with best play the outcome is determined.
    Furthermore, it is also the case that in the end the outcome is
    affected by the compulsion to make a move at each turn. What is
    not obvious is which player is most affected by that necessity.
    
    The upshot of this discussion is that, in spite of the evaluations
    of the initial Chess position made by experts applying their best
    heuristic rules, it is still possible that the preordained outcome
    of the game may come down to a position like the one below, the famous
    K+P vs K+P trap in which the player who is to move must lose. The
    game is, after all, quite delicately balanced, and there are a lot
    of those final positions which may be involved.           
               .....
    	       ..pK.
    	       .kP..
    	       .....

    I've been on vacation and have just finished reading this.  I have been
thinking a lot about what was written and about the game of chess.

re: 23   Thanks for the explanation of the theory.  This helps me understand
what theorists are up against.  I do not believe there is a strategy that
can be selected and followed independently of the opponent's to achieve
an optimal result.  The strategy must be consistent yet flexible to assure
the objective is met without disruption from the opponent's strategy.
Realistically, the objective is checkmate, but there are usually many lesser
objectives that are achieved along the way to insure a winning advantage
to obtain the final objective checkmate.  Since there are many types of
advantages, and they are all convertible, this is what adds to the game's
variety and opponents' styles of play.  Some positions demand certain strategies
for success and other positions demand other strategies.  White to play
first can always chose the same strategy but must be able to adapt to the
resulting position arising from Black's strategy.  Not to do so would mean
not taking advantage of the give and take aspect of the game which allows
one to accrue many small advantages to one winning advantage.  Anyway, this
leads me to...

re: 22    I have never really heard of "double zugzwang", but I understand
that to be at the beginning of the game White is to move and lose?!  If
that was realistic, I believe tournament play would bear it out or at least
show 50/50 chances for Black which it doesn't either.  Now I can't prove
this one way or the other, for starters what constitutes a proof?  Is this
a formula or is it the ability of a player to be unbeatable with White over
the board.  We have had players who were just that in the prime of their
time.  One other item I wish to mention about the "even" position.  What
I meant is that prior in time to this symetrical zugzwang was a position 
with "the person with the move" wins.  Also, the person with the move could
make an extra neutral move first then the winning move (gains tempo) to
accomplish the same scenario where the "player with the move" loses.  In
reality its the "player without a move" (lost position) loses.  I meant
not "even" in that a decisive advantage is held by one of the players.

All in all I found this interesting enough to activate myself into playing
over the board again and applying some ideas brought about by this.

Thanks, 

Steve ( Soon to be one of Mass.'s new masters)

Can anyone prove the theorem ?
    
    /Eric

    The theorem is false. Consider a game which is totally unfair for
    the first player, i.e. he cannot win or draw. Then the extra move never
    hurts but has no effect on the outcome.
    
    It may not be obvious from the rules that a game has this property.
    
    A classical example is the famous "heads I win, tails you lose"
    ploy.

Re .26:

I'm not convinced you've demonstrated a counterexample at all.
I think we have to be careful that what we're dealing with is
indeed a "game" by some formal definition.  Also, even if it is
a game, if first player is set up to lose, then it seems to me
that having an "extra" move does indeed hurt, since having even
a "normal" move hurts.  So I'm not sure you are within the domains
of the theorem.

/Eric

    Well, let's take a more concrete example. The class of games we
    want to consider includes those two-person games between players
    A and B where: 
    	Play begins with a sequence of moves by A
    	Play continues with alternating plays by A and B
    	ending after a predetermined number of plays by B (or when some
    	other predefined stopping condition occurs).
    The rules specify for the players a payoff function which is determined
    by the final state, and the payoff(winner) > payoff(loser).
    
    So far we have not pinned down what is meant by a play, the stopping
    condition, or the payoff function. But this describes the class
    of games referred to in (.0).   
    
    Now let's consider the game of telling the biggest lie (or naming
    the largest number, or whatever). Once A has agreed to play the
    game, A can take as many turns as desired at the outset, and this
    certainly does not diminish his chances of winning. But obviously
    the last player wins - and if our stopping condition is defined
    to be, "B plays last," A can neither win nor draw.
                         
    Nobody said anything about these games being fair!

    I thought Lynn's example was reasonable.

    Another example is Russian Roulette, played with six bullets.
    An extra turn never hurts, since the first player loses, regardless.

The theory of combinatorial games defines a two-person "game" as a directed
graph, where each possible "position" is represented by a vertex and each
possible "move" is represented by an arc from one position to another.

An "impartial" game is a game where the moves are the same for both players
and depend on the position only (e.g., Nim). A "partizan" game is a game where
the moves depend also on who's turn it is (e.g., Chess).

A player is "loosing" the game if he is "stuck" in a position where there is
no more moves (a vertex with out degree of 0).

[1] None of the last replies refered to this definition.
[2] The theorem itself does not say if it speaks about "impartial" games only.
[3] What is a "zugswang" position in Chess? (I know Chess, but my English is 
    not the best)

Can someone clear the subject?

ND

    Chess does not fit the definitions in .30: There is a difference
    between a Checkmate position and a Stalemate position (in the former
    one's King is attacked, in the latter it is not attacked) in that
    while both are terminal positions one is a win/loss and the other a draw.
    
    "Zugswang [German: the compulsion to move]" is a position in which
    the value of the position is greater (win or draw) with the opponent's
    turn to move than with one's own turn to move (draw or loss). An
    example (K+P vs K+P) was given in a previous note. In that position
    whoever has the move must give up the protection of his pawn and
    allow the opponent to capture it and advance his own pawn to Queen
    and Checkmate.

Gary Kasparov is currently defending his chess world championship against
the previous champion, Anatoly Karpov.  After three draws in a match that
may be 24 games long, Kasparov got to this position and sealed his move
on Monday.  Karpov resigned yesterday without seeing the sealed move.


		  Karpov/Black/lower case pieces
		+---+---+---+---+---+---+---+---+
		|   |   |   |   |   |   |   |   |
		+---+---+---+---+---+---+---+---+
		| R |   |   |   |   |   | p |   |
		+---+---+---+---+---+---+---+---+
		|   |   | r |   | n | p |   | k |
		+---+---+---+---+---+---+---+---+
		| P |   |   | N |   |   |   | p |
		+---+---+---+---+---+---+---+---+
		|   |   |   |   | p |   |   |   |
		+---+---+---+---+---+---+---+---+
		|   |   |   |   | P |   | P |   |
		+---+---+---+---+---+---+---+---+
		|   |   |   |   |   | P | K | P |
		+---+---+---+---+---+---+---+---+
		|   |   |   |   |   |   |   |   |
		+---+---+---+---+---+---+---+---+
		 Kasparov/White/upper case pieces

See reply (+1) for newspaper analysis.

John

	A potential spoiler for those who want to ponder 519.32:

Karpov felt no need to see Kasparov's sealed move [P-R6].  The ex-champion
would have wasted his time and energy combatting it, for example, 41...R-Q3
(or 41...N-B4; 42 R-QB7!); 42 N-N4, R-Q8; 43 R-K7, N-N4 (or 43...N-B4; 44
P-R7, R-QR8; 45 N-B6 followed by 46 R-K8 and 47 P-R8/Q); 44 P-R4, N-B6;
45 RxP, N-K8ch; 46 K-B1, R-QR8; 47 K-K2.

(NY Times)

>   Chess does not fit the definitions in .30: There is a difference
>   between a Checkmate position and a Stalemate position (in the former
>   one's King is attacked, in the latter it is not attacked) in that
>   while both are terminal positions one is a win/loss and the other a draw.

Chess does fit the definition of a "partizan" game. Each possible position
can be represented as a distinct vertex (including Stalemate positions).
Each possible move is an arc from one vertex to another, with a label
"white moves" or "black moves" on it.

Note that in order to cover ALL possible position (according to the official
rules of chess) the position includes more information than just the current
layout of the pieces on the board. For example: A king and a rook in their
original places, while not moved yet, is a different vertex from the same
layout while the king or the rook have already moved before.

Nitsan

>                                                  ...Each possible position
> can be represented as a distinct vertex (including Stalemate positions).
> Each possible move is an arc from one vertex to another, with a label
> "white moves" or "black moves" on it.

The whole theory is much bigger, but to make things short, a "draw" (or "tie")
positions are defined as those position in which none of the players can force
a "win". If you want to "declare" a position as a "draw" - point an arc from it
to some closed loop of vertices.

Nitsan

    It seems to fit that chess is not "impartial" also, because each
    player does not have the same moves (options) available all the
    time due to exchanges.  For example, in a knight versus a bishop
    endgame, the bishop can only attack/defend squares of one color
    while a knight can attack/defend either (white on one move, black 
    on the next).
           
    SN