A new way to play computer-Go?

Computers have started to outperform humans in games they used to lose [full text here]

[...] Deep Blue and its successors beat Mr Kasparov using the “brute force” technique. Rather than search for the best move in a given position, as humans do, the computer considers all white's moves—even bad ones—and all black's possible replies, and all white's replies to those replies, and so on for, say, a dozen turns. The resulting map of possible moves has millions of branches. The computer combs through the possible outcomes and plays the one move that would give its opponent the fewest chances of winning.

Unfortunately, brute force will not work in Go. First, the game has many more possible positions than chess does. Second, the number of possible moves from a typical position in Go is about 200, compared with about a dozen in chess. Finally, evaluating a Go position is fiendishly difficult. The fastest programs can assess just 50 positions a second, compared with 500,000 in chess. Clearly, some sort of finesse is required.

In the past two decades researchers have explored several alternative strategies, from neural networks to general rules based on advice from expert players, with indifferent results. Now, however, programmers are making impressive gains with a technique known as the Monte Carlo method. This form of statistical sampling is hardly new: it was originally developed in the Manhattan project to build the first nuclear bombs in the 1940s. But it is proving effective. Given a position, a program using a Monte Carlo algorithm contemplates every move and plays a large number of random games to see what happens. If it wins in 80% of those games, the move is probably good. Otherwise, it keeps looking.

This may sound like a lot of effort but generating random games is the sort of thing computers excel at. In fact, Monte Carlo techniques are much faster than brute force. Moreover, two Hungarian computer scientists have recently added an elegant twist that allows the algorithm to focus on the most promising moves without sacrificing speed.

The result is a new generation of fast programs that play particularly well on small versions of the Go board. In the past few months Monte Carlo-based programs have dominated computer tournaments on nine- and 13-line grids. MoGo, a program developed by researchers from the University of Paris, has even beaten a couple of strong human players on the smaller of these boards—unthinkable a year ago. It is ranked 2,323rd in the world and in Europe's top 300. Although MoGo is still some way from competing on the full-size Go grid, humanity may ultimately have to accept defeat on yet another front.

Copyright © 2007 The Economist Newspaper and The Economist Group. All rights reserved.

Kakuro

[from Nikoli website]

Write numbers from 1 to 9 on all white cells such that:

1. A number in a cell separated by diagonal line tells the sum of numbers in consecutive cells at its right or downward.
2. No number may appear more than once in consecutive cells.

Solution:

Yajilin

[from Nikoli website]

Draw a single line with a loop following the next rules:

1. Lines must pass through the centers of cells horizontally or vertically and never cross, branch off, or go through the same cells twice.
2. Cells where the line is drawn must not be black.
   
3. Black cells must not touch each other horizontally or vertically.
   
4. Lines don't go through numbered cells. Numbered cells cannot be black cells.
5. Numbers represent how many black cells are at the direction of the arrow.

Solution:

ALTERNATING WEAPON CHESS

No-capture chess plus:

First player makes one move, then players make series of two moves until
captures are made, whereupon the series become of length three, etc.

Captures may be made as a series of one move only. The first capture
may be of either type, hand-grenade(*) or machine-gun(:), (which must
make the maximum number of takes available for that particular move);
and after that each player's capture types must alternate.

During a series of non-captures it is permissible to play a piece into
a position where it could make either sort of capture but does not do so,
at the mover's choice. Declaration of ambiguous capture type is unnecessary.

r . . . . Q . .     |  1. e4               11. Ng5::
. p k r . . b .     |  2. e5 Nc6           12. Bf6:
p . p . . R . .     |  3. Nf3 c3           13. f4* +
. . N p . . . .     |  4. d5*              14. Kf7e7d7c7
O . . O . . . .     |  5. Bb5: +           15. Nd2b3c5 Qg4
. . O . . . . .     |  6. c6:              16. Be6 Rf7d7 h6
. O . . . . O O     |  7. 0-0 d4 a4        17. Qg8::
R . . . . . K .     |  8. Be7 Nf6 O-O      18. Bg7*
____________________'  9. Bh6**            19. f5f6f7f8Q Rf6
                      10. Nh7*             20. resign

LOVE-Y

LOVE-L modifier:
Along with one's own stone one must play an opponent
stone as (Euclidean) close as possible to one's own.

          .            1.   n6  o5    m5 n4
         . .           2.   g7  f6    h6 g5
        . . .          3.   f8  e7    k7 m7
       . . . x         4.   l10 m11   j10 k11
      x . . o o        5.   j8  i9    i7 j6 !
     o o x . x .       6.   h8  g9    l8 n8
    o x o o x . .      7.   resign
   . x x x O X . .     8.  
  . . o o . . . . .    9.  
 . . . . o x . . . .  10.
. . . . . x o . . . . 11.  
abcdefghijklmnopqrstu

The 5th move for the second player finishes the game abruptly (a kind of mate in 6).

Ripple Effect

[from Nikoli website]

The areas, divided by bold lines, are called "Rooms". Fill in all empty cells with numbers under following rules:

1. Each Room contains consecutive numbers starting from 1.
2. If a number is duplicated in a row or a column, the space between the duplicated numbers must be equal or larger than the value of the number.

Solution:

Nonogram (aka Paint By Numbers)

1. Paint some black cells such that they obey all numbers:
   
2. Each number determines a number of consecutively filled squares (called a cluster).
3. Each number sequence (row or column) shows how many clusters are there and the cluster sequence (naturally, each cluster is separated by, at least, one empty cell).
   

To read more, go to the Wikipedia entry.

Kurodoko

[from Nikoli website]

1. Place black cells according to the next rules:
2. Each number on the board represents the sum of white cells from that number to black cells or outer frame, horizontally and vertically.
3. The cells which include numbers are always white.
4. Black cells must not touch each other horizontally or vertically.
   
5. All white cells must be orthogonally connected.

Solution:

Tentai Show

[from Nikoli website] [Wikipedia]

1. Draw a bold line over the dotted line and divide the board into blocks.
2. Every block must have horizontal and vertical symmetries with a star at its center.

Solution:

Number Link

[from Nikoli website]

1. Connect same numbers with continuous line.
2. Lines must go through the center of a cell horizontally or vertically and never go through twice the same cell.
3. Lines cannot be crossed, branch off or go through number's cells.

Solution:

Shikaku (Divide by Box)

[from Nikoli website]

1. Divide the grid into rectangles.
2. Each rectangle contains only one number.
3. The number indicates how many cells are contained in the rectangle.

Solution:

Heyawake

[from Nikoli website]

The rectangle, divided by bold lines, is called "Room". Each number indicates how many painted cells exist in its room, while no number rooms may have any number of painted cells. Paint cells under following rules:

1. White cells must not exceed two rooms in a straight line.
2. The painted cells must not be orthogonally connected.
   
3. White cells must not be (orthogonally) separated by painted cells.

Solution:

Nuruomino (aka LITS)

[from Wikipedia]

1. Shade a tetromino on each area, such that:
2. Every pair of orthogonally adjacent tetrominoes are not equal (considering rotations and reflections),
3. The shaded cells are all orthogonally contiguous and contain no 2×2 square tetrominoes as subsets.

Solution:

DIAMOND & PIVOTS (v.2)

1. On each turn, each player passes or drops a stone on an empty cell.
   There is a swap option after the first half-turn.
2. If any diamond patterns with four friendly stones are made, the player
   must choose one, choose a stone from it (the pivot), and place
   its other three stones in a line starting from the pivot.
  2.1 Every stone (of either color) that was on those destination cells
      are captured and removed from the board.
  2.2 If, after a pivot movement, another diamond shape is made,
      the player must repeat this procedure.
3. A stone may not be played to make a group of more than four stones,
   unless it thereby makes a diamond.
4. After two consecutive passes, wins the player with more
   stones (if equal, wins the 2nd)

Sample game:
abcdefghijklmnopq
    . . . . .      1.  c7 <--pied  i5
   . . . . . .     2.  d6          j4
  . . . . x x .    3.  e7          k5
 . . o x o x . .   4.  h4          m5
. . x x . x o . .  5.  l4        j6,h4-n4::
 o o x o . . . .   6.  h6     k5,k5-e5,h4-e7:
  o x . . . . .    7.  f4          l4
   . . . . . .     8.  m5          k3
    . . . . .      9.  j4          m3
abcdefghijklmnopq 10.  b6

And then...

abcdefghijklmnopq
    . . . . .      1.  c7 <--pied  i5
   . . . . . .     2.  d6          j4
  . . . . x . .    3.  e7          k5
 . . o . x . . .   4.  h4          m5
. . . . x x x x .  5.  l4        j6,h4-n4::
 x x x x . . . .   6.  h6     k5,k5-e5,h4-e7:
  o x . . . . .    7.  f4          l4
   . . . . . .     8.  m5          k3
    . . . . .      9.  j4          m3
abcdefghijklmnopq 10.  b6

10...   l2,k3-h6::,h4k5,i5-o5:,e5i6,h6-b6::

First player resigns.


Nurikabe

[from nikoli website]

1. You cannot fill the cells containing numbers.
2. A number tells the number of continuous white cells. Each area of white cells contains only one number in it and areas are separated by black cells.
3. The black cells are linked to be an orthogonally continuous wall.
4. Black cells cannot be linked to be 2x2 square or larger.

Solution:

Filomino

[from nikoli website]

1. Fill in all empty cells with numbers under the following rules:
2. The area, connected by the same numbers horizontally or vertically, is called "Block". Separate the entire board by Blocks.
3. Each Block contains as many cells as the number it contains (e.g., a Block of 6 has 6 cells).
4. Blocks of the same size must not touch each other, horizontally or vertically.

Solution:

Hitori

[from nikoli website]

1. Paint enough cell numbers such that:
   
2. No number may appear more than once in each row and each column.
3. The painted cells must not be orthogonally connected.
4. Un-painted cells must not be orthogonally separated by painted cells.

Solution:

Akari

[from nikoli website]

1. Place circles according to the following rules.
2. Circles are permitted at any white squares. Each number indicates how many circles are next to it, vertically and horizontally.
3. Each circle 'illuminates' from it to black square or outer frame in its row and column.
4. Every white square must be illuminated and every circle should not illuminate each other.
   

Solution:

It's possible to play online at http://www.puzzle-loop.com/

Hashiwokakero

[from nikoli website]

1. The number of connections is the same as the number inside the node
   
2. There can be up to two connections between two nodes
3. Connections cannot cross nodes or other connections
4. There is a continuous path connecting all nodes

Solution:

It's possible to play online at http://www.puzzle-loop.com/

Slitherlink

[from nikoli website]

1. Connect dots with vertical / horizontal line and make one loop.
2. Numbers are the hints to know how many lines can be drawn around it.
   There may be any number of lines around cells without number.
3. Lines cannot be crossed or branch off.

Solution:

It's possible to play online at http://www.puzzle-loop.com/

Masyu

[from nikoli website]

1. Make a single loop. Lines must pass through the centers of cells horizontally or vertically and never cross, branch off, or go through the same cells twice.
2. Lines must pass through all cells containing black and white circles.
3. Lines passing through a white circle cell must go straight through the cell, then make a right-angled turn in the very next cell (on at least one side of the white circle cell).
4. Lines passing through a black circle cell must make a right angled turn immediately, in the black circle cell, then go straight for the next two cells.

Solution:

Futoshiki

A new Japanese puzzle. As in Soduku, you must place all numbers from 1 to 5 in each row and column without repetition, but you must also satisfy the less than/greater than signals.

SLOW PROGRESSIVE GO 9x9

This game uses a progressive mutator in order to increase the dynamics of the original game. However, unrestricted Go drops would kill the game so two restrictions are added: (a) each stone on a drop sequence cannot belong to the same group (b) an atari stops the sequence.

Here's an example at a 9x9 board (white won 41-40). Herein it is used the slow progressive (1222344456667...)

a b c d e f g h i
. . . o x . . . . 1: c7
. . . o x . . . . 2: g3 g6
. . o o x . x x . 3: c3 e8
. . o x . . . . . 4: e2 g8
. . . o x . . . . 5: d2 d5 e7
. . . . o x x . . 6: d4 e3 e5 f7
. . o . o x . . . 7: d1 c4 e6 f9
. . . . o o x . . 8: e1 f6 g9 h3
. . . . . o x . . 9: d3 f8
a b c d e f g h i

HYDRA CHESS

Rules:

  1. Basic chess rules apply, except:
  2. When a piece makes a capture, it reduces rank and buds off
     a piece one rank lower, leaving this behind on the exit square.
     Ranks: KQRBNP-.

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

The Hydra game is a one-person game.

You start with a rooted tree, and at any move, you may remove one
leaf, and then duplicate (later triplicate, quadruplicate etc)
the whole remaining subtree it leaves, right down to the root.
The "n" in the n-plicate goes up one on every move, starting at 2.

                    *   *                         * *   * *
                     \ /                           \|   |/
So e.g. if we     *   *   *  ...it goes             *   *   *
delete the left    \ /   /      to this one,         \  |  /
leaf from this      *   *       when n=2.             * * *
tree...              \ /                               \|/
                      R                                 R

The number of nodes increases dramatically every time, but... the theorem is, no matter what you start with, and how you choose your leaf cuttings, IT WILL ALWAYS REDUCE to the empty tree, eventually !!

In fact, you don't even have to restrict yourself to increasing the n by one every time, you can up it in squares or powers of two or anything you like!

And it's one of those things that can be easily stated in basic number theory, (PA), but not proved there.  To prove it requires knowing about infinite ordinal numbers up to epsilon_0, if that means anything to you, which is the first ordinal that PA "can't handle".  i.e. can't prove that it is an ordinal, i.e. that
the above process must halt, (as it executes a decreasing series of ordinals, which therefore must always terminate).

You can see how the newly proposed budding chess emulates this slightly; there is an increasing number of pieces, but the total metric (in an appropriate sense) is always decreasing... i.e. the "top value".

Trabsact Sagme Diaries

The abstract game's fog should be adequate to the player's myopia [T.Sagme, Proverbs]