Gardner's minichess solved

Code, algorithms, languages, construction...
BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Gardner's minichess solved

Post by BB+ » Thu Aug 29, 2013 10:39 am

Not sure I saw this announced anywhere (other than on the CCRL page, perhaps as Kryukov had solved smaller versions).

http://arxiv.org/abs/1307.7118
Gardner's Minichess Variant is solved
Mehdi Mhalla, Frederic Prost
(Submitted on 26 Jul 2013)

A 5x5 board is the smallest board on which one can set up all kind of chess pieces as a start position. We consider Gardner's minichess variant in which all pieces are set as in a standard chessboard (from Rook to King). This game has roughly 9x10^{18} legal positions and is comparable in this respect with checkers. We weakly solve this game, that is we prove its game-theoretic value and give a strategy to draw against best play for White and Black sides. Our approach requires surprisingly small computing power. We give a human readable proof. The way the result is obtained is generic and could be generalized to bigger chess settings or to other games.
Their webpage is http://membres-lig.imag.fr/prost/MiniChessResolution/

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: Gardner's minichess solved

Post by BB+ » Fri Aug 30, 2013 5:18 am

It appears that the Italian Chess Variant league (AISE) gave up the game in the early 90s(?) on the grounds that it was so drawish. http://web.archive.org/web/200907310439 ... amp_mn.htm
Il campionato di Miniscacchi 5x5 non viene più disputato in quanto la variante è stata demolita. L'esito della partita a gioco corretto è sempre la patta..

User923005
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Gardner's minichess solved

Post by User923005 » Fri Aug 30, 2013 7:29 am

This is the part that is interesting:
"The way the result is obtained is generic and could be generalized to bigger chess settings or to other games."

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: Gardner's minichess solved

Post by BB+ » Fri Aug 30, 2013 8:20 am

The way the result is obtained is generic and could be generalized to bigger chess settings or to other games.
I am not fully in agreement with this assertion. It seems that the 5x5 game tends to trade off the pawns too fast. Furthermore, White has no "blitz" win (such as aiming for the enemy King), so if down a pawn after a few moves, White has no hope (even with equal material Black typically draws). The authors themselves note something along these lines (paragraph 4 of section 2):
It turns out that most of the deviations from the main line can be quickly decided. It is mainly due to the fact that in Gardner’s chess pawns are immediately exchanged or blocked. Moreover, pieces cannot develop naturally since almost all free squares are controlled by pawns. Also the fact that promotion happens quickly leads to some very rapid checkmates that allow to prune the game tree.
In particular, if White opens by pushing the knight pawn this loses a pawn (rook file pin), while pushing the rook pawn leads to a pawn then piece exchange (if White does not recapture the pawn is lost) and the dust quickly settles. Similarly with the king pawn push.

For the B and Q pawn pushes, Black aims to blockade. One aspect of the current setup is that (particularly) after a push of the rook pawn [by either side], the knight's movement can be suppressed by pawn guards, and the bishop is similarly clunky [especially when the opponent has a pawn on the central square]. So White has to exchange pawns early, and as with the other lines, this kills all tension.

On a larger board (5x6 even), I don't think there is such an early detonation. Maybe even some of the others in the 5x5 class (varying RNBQK, perhaps asymmetrically) could be more interesting (the authors do not discuss this).

frprost
Posts: 1
Joined: Mon Sep 02, 2013 12:25 pm
Real Name: Frédéric Prost

Re: Gardner's minichess solved

Post by frprost » Mon Sep 02, 2013 1:23 pm

On a larger board (5x6 even), I don't think there is such an early detonation. Maybe even some of the others in the 5x5 class (varying RNBQK, perhaps asymmetrically) could be more interesting (the authors do not discuss this).
We are investigating 6X6 (los alamos chess) and we are 99% sure that it is a draw (we made some analysis but we don't have a formal proof yet). Nevertheless, due to the size of the Oracles to produce, it is beyond the scope of hand driven proof. We are working on a completely automated proof system : a 5X6 variant (together with the other 5x5 settings) is a good candidate to test it before los alamos chess. Good candidates are also drawn games from the TCEC championship for instance : we could formally prove that the last position of a drawn game is a draw, and from that point to backtrack to see until what move we can still prove the draw (if we can backtrack up to move 1 then chess is solved :) ).

What can be generalized is rather the spirit of our approach than the raw result. We don't look for "best moves" or "perfect games" in the sense that we just want to prove the theoretical value of a position : thus we only have to find a move that doesn't change the theoretical value of the position. Moreover since we are looking for a draw we can select the most drawish lines first (blocking pawns, exchanging material fast etc.). It allows to simplify the analysis a lot : our proof for Gardner is only few pages of text to be compared with the proof for checkers (the proof required hundreds of computers and Terabytes of data) : however both games have roughly the same space search.

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: Gardner's minichess solved

Post by BB+ » Tue Sep 03, 2013 3:07 am

frprost wrote:We are investigating 6X6 (los alamos chess) and we are 99% sure that it is a draw (we made some analysis but we don't have a formal proof yet).
Sounds about like the siutation with Othello: http://en.wikipedia.org/wiki/Computer_Othello
Othello 8 x 8

The Othello 8x8 game tree size is estimated at 10^54 nodes, and the number of legal positions is estimated at less than 10^28. Although not mathematically solved yet, a solution could possibly be found using intensive computation with top programs on fast parallel hardware or through distributed computation.

Some top programs have expanded their books for many years now. As a result, many lines are in practice draws or wins for either side. [...] Although it is not proven yet, practically the game always ends in a draw if both players play perfectly. On standard games, using their opening book, top programs lose less than 1% of the time.
On other hand, although computer International Draughts also has large draw rates (with Kingsrow International), I don't think a "solution could be found using intensive compution" (with Othello, I am not as optimistic as Wikipedia, but admit it is perhaps feasible). I guess one reason might be that checkers/draughts has some (very) long drawing/winning lines, while this is not so with Othello or small chess versions.

Tord
Posts: 35
Joined: Mon Jun 14, 2010 9:08 pm
Real Name: Tord Romstad

Re: Gardner's minichess solved

Post by Tord » Wed Sep 04, 2013 6:21 pm

Damn, that's a disappointment. I was planning to release an iOS app for this game next year on the occasion of the 100th anniversary of Gardner's birth. With this news, it's hard to find the motivation.

lostman
Posts: 3
Joined: Sat Sep 14, 2013 11:08 am
Real Name: Mehdi Mhalla

Re: Gardner's minichess solved

Post by lostman » Sat Sep 14, 2013 11:16 am

The fact that it is theoretically a draw doesn't mean that it is not interesting to play, there are positions that are very challenging even with the engine we made:
for example the 4 positions below where the side that play can win but its a challeging checkmate. (they come from analyzing different variations and are in the set of positions reachable after one (theoretical) mistake that is not easy to see at first.

8/8/1rnbqk2/1p1p1p2/1Pp1PP2/2P1P3/1RNBQK2/8 b - - 0 3
8/8/1rnbqk2/3ppp2/1p1p1P2/1PP1P3/1RNBQK2/8 w - - 0 3
8/8/1r2qk2/2bppp2/1n3P2/1P2P3/1RNBQK2/8 b - - 0 4
8/8/1rnbqk2/1p1pp3/1P3p2/3PPP2/1RNBQK2/8 w - - 0 3

and many lines in various variations are very sharp and very interesting to play.

Tord
Posts: 35
Joined: Mon Jun 14, 2010 9:08 pm
Real Name: Tord Romstad

Re: Gardner's minichess solved

Post by Tord » Mon Sep 16, 2013 9:45 am

lostman wrote:The fact that it is theoretically a draw doesn't mean that it is not interesting to play
True, that the game is theoretically solved doesn't automatically make it less interesting in practice for human players. I was discouraged not so much by the game being solved as by this statement by BB+ earlier in the thread:
BB+ wrote:It appears that the Italian Chess Variant league (AISE) gave up the game in the early 90s(?) on the grounds that it was so drawish.
Maybe an app for the game is still worth doing, though. It wouldn't take much work to hack up something basic, and I've had feedback from a few people who would actually like to see such an app.

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: Gardner's minichess solved

Post by BB+ » Fri Sep 20, 2013 3:27 pm

There is now an on-line browser. http://membres-lig.imag.fr/prost/MiniChessResolution/

I was looking at the Mallet Chess version: http://membres-lig.imag.fr/prost/MiniCh ... etM25.html
It seems to me that this line: 1.b4 c4 2.e4 cxd3 3.Qxd3 f4 4.Rb3 d4 5.cxd4 Qc4 6.d5 Bxd5 7.exd5 Qxd5 8.Ne4+ Ke6 9.Nc5+ Kd6 10.Ke2 Qxd3+ 11.Rxd3+ Kc6 12.Ne4, ends in stalemate -- is this a win in these rules?

Post Reply