neverendingbooks – Page 194

dvonn (1) mobility

Published January 7, 2006 by lieven

[Dvonn](http://www.gipf.com/dvonn $ is
the fourth game in the [Gipf Project](http://www.gipf.com/project_gipf/index.html) and the most
mathematical of all six. It is a very fast (but subtle) game with a
simple [set of rules](http://www.gipf.com/dvonn/rules/rules.html). Here
is a short version

DVONN is a stacking game. It is played
on an elongated hexagonal board, with 23 white, 23 black and 3 red
DVONN-pieces. In the beginning the board is empty. The players first
place the DVONN-pieces on the board and next their own pieces. Then they
start stacking pieces on top of each other. A single piece may be moved
1 space in any direction, a stack of two pieces may be moved two spaces,
etc. A stack must always be moved as a whole and a move must always end
on top of another piece or stack. If pieces or stacks lose contact with
the DVONN pieces, they must be removed from the board. The game ends
when no more moves can be made. The players put the stacks they control
on top of each other and the one with the highest stack is the winner.
That’s all!

All this will become clearer once we fix a
specific end-game, for example

$\xymatrix@=.3cm @!C @R=.7cm{ & &
\Black{2} \connS & & \bull{d}{5} \conn & & \bull{e}{5} \conn & &
\bull{f}{5} \conn & & \bull{g}{5} \conn & & \bull{h}{5} \conn & &
\SWhite \connS & & \SWhite \connS & & \SWhite \conneS & & \\ &
\bull{b}{4} \conn & & \SBlack \connS & & \Black{6} \connS & &
\bull{e}{4} \conn& & \bull{f}{4} \conn & & \bull{g}{4} \conn & &
\bull{h}{4} \conn & & \SWhite \connS & & \SWhite \connS & & \SWhite
\conneS & \\ \SBlack \connbeginS & & \SBlack \connS & & \BDvonn{7}
\connS & & \bull{d}{3} \conn & & \SBlack \connS & & \BDvonn{6} \connS &
& \bull{g}{3} \conn & & \bull{h}{3} \conn & & \Dvonn \connS & & \SWhite
\connS & & \SWhite \connendS \\ & \Black{5} \connbeginS & &
\bull{b}{2} \conn & & \SBlack \connS & & \bull{d}{2} \conn & &
\bull{e}{2} \conn & & \bull{f}{2} \conn & & \bull{g}{2} \conn & &
\bull{h}{2} \conn & & \SWhite \connS & & \SWhite \connendS & \\ & &
\bull{a}{1} \con & & \bull{b}{1} \con & & \Black{5} \conS & &
\bull{d}{1} \con & & \bull{e}{1} \con & & \bull{f}{1} \con & &
\bull{g}{1} \con & & \bull{h}{1} \con & & \White{2} & &} $

with
White to move. Some comments about notation : the left-slanted columns
are denoted by letters from a (left) to k (right) and the rows are
labeled 1 to 5 from bottom to top (surprisingly this ‘standard’
webgame-notation differs from the numbering on my Dvonn-board where the
rows are labeled from top to bottom…). So, for example, the three
spots on the upper right are k3,k4 and k5 (there are no k1 or k2 spots).
The three Dvonn pieces are colored red and in the course of the game a
stack may land on a Dvonn piece and so stacks containing a Dvonn piece
are denoted with a red halo. For example, the symbol on spot f3 stands
for for a stack of 6 pieces, one of which is a red Dvonn piece, under
the control of Black (that is, the top-piece is Black). Further note
that a piece or stack can only move if it is not surrounded by 6 other
pieces or stacks (so the White pieces on j3 and j4 cannot (yet) move). A
piece can only move by one step in either line-direction provided there
is another piece or stack on that position. The same applies for stacks
: an height 3 stack for example can move in each lin-direction by
exactly 3 steps provided there is a piece or stack to jump onto. For
example, the height 6 stack on d4 can only move to j4 whereas the height
6 stack on f3 cannot move at all! Similarly, the two black height 5
stacks are immobile. At the moment black has all its stacks defended,
that is, if White should be able to jump onto one of them (which White
cannot at the moment), Black can use one of its neighbouring pieces to
take the stack back under its control. So, any computer program would
‘evaluate’ the position as favourable for Black : Black has stacks of
total height 34 safely under control (there are no immediate threats to
be seen : the [horizon effect](http://www.comp.lancs.ac.uk/computing/research/aai-aied/people/paulb/old243prolog/subsection3_7_5.html) in such programs) whereas White
can only claim potential stacks of total height 13… Still, Black
has already lost the game. White has more pieces which are quite mobile
as opposed to the immobile black stacks, so Black will soon run out of
moves to make and his end position will have some large stacks on the
third row. All white has to do is to let Black run out of moves and then
continue (Dvonn forces each player to make a move if they still can and
to pass the move otherwise, so the most mobile player can still continue
long after the other player was forced to stop) to build a White stack
of the appropriate height on the third row to jump on the highest Black
stack with its last move! Here is how the play continued : 1) j2-k3 ;
a3-b3 2) i1-k3 ; c5-c3 3) i2-i3 ; c2-c3 4) i3-k3 ; d4-j4 5)
j3-j4 ; e3-f3 6) i4-j4 ; c4-b3 to arrive at the position where
Black is no longer able to make any moves at all

$\xymatrix@=.3cm
@!C @R=.7cm{ & & \bull{c}{5} \conn & & \bull{d}{5} \conn & & \bull{e}{5}
\conn & & \bull{f}{5} \conn & & \bull{g}{5} \conn & & \bull{h}{5} \conn
& & \SWhite \connS & & \SWhite \connS & & \SWhite \conneS & & \\ &
\bull{b}{4} \conn & & \bull{c}{4} \conn & & \bull{d}{4} \conn & &
\bull{e}{4} \conn& & \bull{f}{4} \conn & & \bull{g}{4} \conn & &
\bull{h}{4} \conn & & \bull{i}{4} \connS & & \White{9} \connS & &
\SWhite \conneS & \\ \bull{a}{3} \connbegin & & \Black{3} \connS & &
\BDvonn{10} \connS & & \bull{d}{3} \conn & & \bull{e}{3} \conn & &
\BDvonn{7} \connS & & \bull{g}{3} \conn & & \bull{h}{3} \conn & &
\bull{i}{3} \conn & & \bull{j}{3} \conn & & \WDvonn{6} \connendS \\ &
\Black{5} \connbeginS & & \bull{b}{2} \conn & & \bull{c}{2} \conn & &
\bull{d}{2} \conn & & \bull{e}{2} \conn & & \bull{f}{2} \conn & &
\bull{g}{2} \conn & & \bull{h}{2} \conn & & \bull{i}{2} \conn & &
\bull{j}{2} \connend & \\ & & \bull{a}{1} \con & & \bull{b}{1} \con & &
\bull{c}{1} \con & & \bull{d}{1} \con & & \bull{e}{1} \con & &
\bull{f}{1} \con & & \bull{g}{1} \con & & \bull{h}{1} \con & &
\bull{i}{1} & &} $

Note that all pieces and stacks no longer
connected to a Dvonn piece must be removed. So, for example, after the
third move by Black, the Black height 5 stacks on c1 was removed. All
white now has to do is to built an height 8 stack on k3 and jump onto
the height 10 Black stack on c3 to win the game. The (only) way to do
this is by 7. j5-k5 and 8. k5-k3 to finish with 9. k3-c3 with final
position (note again that the White right-hand pieces and stacks are no
longer connected to a Dvonn piece and are hence removed)

$\xymatrix@=.3cm @!C @R=.7cm{ & & \bull{c}{5} \conn & & \bull{d}{5}
\conn & & \bull{e}{5} \conn & & \bull{f}{5} \conn & & \bull{g}{5} \conn
& & \bull{h}{5} \conn & & \bull{i}{5} \conn & & \bull{j}{5} \conn & &
\bull{k}{5} \conne & & \\\ & \bull{b}{4} \conn & & \bull{c}{4} \conn &
& \bull{d}{4} \conn & & \bull{e}{4} \conn& & \bull{f}{4} \conn & &
\bull{g}{4} \conn & & \bull{h}{4} \conn & & \bull{i}{4} \conn & &
\bull{j}{4} \conn & & \bull{k}{4} \conne & \\\ \bull{a}{3} \connbegin
& & \Black{3} \connS & & \WDvonn{18} \connS & & \bull{d}{3} \conn & &
\bull{e}{3} \conn & & \BDvonn{7} \connS & & \bull{g}{3} \conn & &
\bull{h}{3} \conn & & \bull{i}{3} \conn & & \bull{j}{3} \conn & &
\bull{k}{3} \connend \\\ & \Black{5} \connbeginS & & \bull{b}{2} \conn
& & \bull{c}{2} \conn & & \bull{d}{2} \conn & & \bull{e}{2} \conn & &
\bull{f}{2} \conn & & \bull{g}{2} \conn & & \bull{h}{2} \conn & &
\bull{i}{2} \conn & & \bull{j}{2} \connend & \\\ & & \bull{a}{1} \con &
& \bull{b}{1} \con & & \bull{c}{1} \con & & \bull{d}{1} \con & &
\bull{e}{1} \con & & \bull{f}{1} \con & & \bull{g}{1} \con & &
\bull{h}{1} \con & & \bull{i}{1} & & } $

So White wins with 18 to
Black’s 15. This shows that it is important to maintain mobility and
also that it is possible to win a Dvonn-game from computers. In fact,
the above end-game was played against a computer-program (Black). The
entire game can be found
[here](http://www.littlegolem.net/jsp/game/game.jsp?gid=426457&nmove=91)
.

Alain Connes on everything

Published January 6, 2006 by lieven

A few
days ago, Ars Mathematica wrote :

Alain Connes and Mathilde Marcolli have posted a
new survey paper on Arxiv A walk in the
noncommutative garden. There are many contenders for the title of
noncommutative geometry, but Connes‚Äô flavor is the most
successful.

Be that as it may, do
not print this 106 page long paper! Browse through it
if you have to, be dazzled by it if you are so inclined, but I doubt it
is the eye-opener you were looking for if you gave up on reading
Connes’ book Noncommutative
Geometry…. Besides, there is much better
_Tehran-material_ on Connes to be found on the web : An interview
with Alain Connes, still 45 pages long but by all means : print it
out, read it in full and enjoy! Perhaps it may contain a lesson or two
for you. To wet your appetite a few quotes

It is
important that different approaches be developed and that one
doesn‚Äôt try to merge them too fast. For instance in noncommutative
geometry my approach is not the only one, there are other approaches
and it‚Äôs quite important that for these approaches there is no
social pressure to be the same so that they can develop
independently. It‚Äôs too early to judge the situation for instance
in quantum gravity. The only thing I resent in string theory is that
they put in the mind of people that it is the only theory that can
give the answer or they are very close to the answer. That I resent.
For people who have enough background it is fine since they know all
the problems that block the road like the cosmological constant, the
supersymmetry breaking, etc etc…but if you take people who are
beginners in physics programs and brainwash them from the very start
it is really not fair. Young physicists should be completely free,
but it is very hard with the actual system.

And here for some (moderate) Michael Douglas bashing :

Physicists tend to shift often and work on the
last fad. I cannot complain because at some point around 98 that fad was
NCG after my paper with Douglas and Schwarz. But after a while when
I saw Michael Douglas and asked him if he had thought more about
these problems the answer was no because it was no longer the last
fad and he wanted to work on something else. In mathematics one
sometimes works for several years on a problem but these young
physicists have a very different type of working habit. The unit of
time in mathematics is about 10 years. A paper in mathematics which is
10 years old is still a recent paper. In physics it is 3 months. So
I find it very difficult to cope with constant
zapping.

To the suggestion that he is the
prophet (remember, it is a Tehran-interview) of noncommutative geometry
he replies

It is flattering but I don‚Äôt think
it is a good thing. In fact we are all human beings and it is a
wrong idea to put a blind trust in a single person and believe in
that person whatever happens. To give you an example I can tell you
a story that happened to me. I went to Chicago in 1996, and gave a
talk in the physics department. A well known physicist was there and
he left the room before the talk was over. I didn‚Äôt meet this
physicist for two years and then, two years later, I gave the same
talk in the Dirac Forum in Rutherford laboratory near Oxford. This
time the same physicist was attending, looking very open and convinced
and when he gave his talk later he mentioned my talk quite
positively. This was quite amazing because it was the same talk and
I had not forgotten his previous reaction. So on the way back to
Oxford, I was sitting next to him in the bus, and asked him openly
how can it be that you attended the same talk in Chicago and you
left before the end and now you really liked it. The guy was not a
beginner and was in his forties, his answer was ‚ÄúWitten was seen
reading your book in the library in Princeton‚Äù! So I don‚Äôt want
to play that role of a prophet preventing people from thinking on
their own and ruling the sub ject, ranking people and all that. I
care a lot for ideas and about NCG because I love it as a branch of
mathematics but I don‚Äôt want my name to be associated with it as a
prophet.

and as if that was not convincing
enough, he continues

Well, the point is that what
matters are the ideas and they belong to nobody. To declare that
some persons are on top of the ladder and can judge and rank the
others is just nonsense mostly produced by the sociology (in fact by the
system of recommendation letters). I don‚Äôt want that to be true in
NCG. I want freedom, I welcome heretics.

But please, read it all for yourself and draw your own conclusions.

a Da Vinci chess problem

Published December 30, 2005 by lieven

2005
was the year that the DaVinci code craze hit Belgium. (I started reading Dan Brown’s
Digital Fortress and Angels and Demons a year
before on the way back from a Warwick conference and when I read DVC a
few months later it was an anti-climax…). Anyway, what better way
to end 2005 than with a fitting chess problem, composed by Noam Elkies

The problem is to give an infinite sequence
of numbers, the n-th term of the sequence being the number of ways White
can force checkmate in exactly n moves. With the DVC-hint given, clearly
only one series can be the solution… To prove it, note that
White’s only non-checkmating moves are with the Bishop traveling
along the path (g1,h2,g3,h4) and use symmetry to prove that the number
of paths of length exactly k starting from h2 is the same as those
starting from g3…

If that one was too easy for you,
consider the same problem for the position

Here the solution are the 2-powers of those
of the first problem. The proof essentially is that White has now two
ways to deliver checkmate : Na6 and Nd7… For the solutions and
more interesting chess-problems consult Noam Elkies’ excellent
paper New directions in
enumerative chess problems. Remains the problem which sequences can
arise on an $N \\times N$ board with an infinite supply of chess
pieces!

neverendingbooks Posts

dvonn (1) mobility

Alain Connes on everything

a Da Vinci chess problem