Checkers Is Strongly-Solved for 8-pieces

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mar
Posts: 1832
Joined: Fri Nov 26, 2010 1:00 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by mar » Sun Feb 19, 2017 11:17 pm

I remember as kids we used to play a checkers variant with two rows only (using standard chess pawns as checkers).
While the game is certainly interesting, I personally prefer chess.

However even orthodox chess can start to be boring at some point.

Recently I watched a guy who calls himself Jann Lee play crazyhouse and I have to say it's a very interesting variant (I would say way more than chess).
It's not as exotic as other variants which makes it easier for me to follow (bughouse is too difficult for me).

Lots of sacs, lot of crazy tactics and to me significantly more fun than chess, a way more dynamic game.

Ed Trice
Posts: 99
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 20, 2017 2:35 am

mar wrote:However even orthodox chess can start to be boring at some point.
That's why I invented Gothic Chess. I had read both Henry Bird (1874) and Jose Capablanca (1921) tried to convince the world to change chess to an 80-square board with two new pieces: An Archbishop (knight + bishop) and Chancellor (knight + rook). They both had the right idea, but I believe they did not play-test it enough. Their starting positions each had one or more flaws.

1. Not all pawns were protected in each of their versions.
2. In Bird's game, Chancellor-to-h2 threatens Cxh7 mate! So much for making the opening more diverse.
3. Capablanca's game had Bishop, Queen, and Archbisop, 3 "diagonal-moving" pieces in a row, all on the Queenside, all aimed towards i7, and undefended pawn equivalent to g7 in regular chess.

After much play-testing, I found a more fluent setup.

I have a GUI that plays the game with 5-piece tablebases generator if you have 30 days and would like to see the Mate in 268 endgame.

https://drive.google.com/file/d/0BzeUnP ... sp=sharing

Here's what it looks like:

Image

Ed Trice
Posts: 99
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 20, 2017 5:31 am

Image

A better view of the longest win with 4 checkers vs. 4 checkers and white to move.

Daniel Anulliero
Posts: 625
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Daniel Anulliero » Mon Feb 20, 2017 8:21 am

I'm just a chess programmer ( the last one Isa is only 2165 CCRL) , and I've studied Othello game too , never the checkers
So excuse my ignorance but sure you did a great work, but with chinook , the game is solved it seems and chinook has
"an opening book, a library of opening moves from games played by grandmasters; a deep search algorithm; a good move evaluation function; and an end-game database for all positions with eight pieces or fewer."
(Read from wikipedia)
So I think it's a lot useless to work on a solved game , like I write an endgame database for Othello since the Bests programs can compute 30-40 moves in a few time.
Just my personnal réflexion ..
Bests
Dany

abulmo2
Posts: 131
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: Checkers Is Strongly-Solved for 8-pieces

Post by abulmo2 » Mon Feb 20, 2017 2:13 pm

Daniel Anulliero wrote:like I write an endgame database for Othello since the Bests programs can compute 30-40 moves in a few time.
To be more precise:
Endgame databases are not computed at Othello, because it is a diverging game. Endgame database are only usable on converging games, like chess or checkers.
Endgame are easily solved at Othello, because the game has a fixed termination, unlike chess.
Richard Delorme

User avatar
Nordlandia
Posts: 2037
Joined: Fri Sep 25, 2015 7:38 pm
Location: Sortland, Norway

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Nordlandia » Mon Feb 20, 2017 5:10 pm

Ed Trice: do generated tablebases exist for Gothic Chess / Capablanca?

Image

Ed Trice
Posts: 99
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 20, 2017 5:34 pm

Nordlandia wrote:Ed Trice: do generated tablebases exist for Gothic Chess / Capablanca?

Image

Ed Trice
Posts: 99
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 20, 2017 5:37 pm

Nordlandia wrote:Ed Trice: do generated tablebases exist for Gothic Chess / Capablanca?

Image
Yes I generated up to 5-piece tablebases for Gothic Chess.

By the way, I was the one who set up the position shown on that board. That picture was taken in Iceland in 2006 on my first trip to try and meet Bobby Fischer. I showed that line of play to GM Fridrik Olafsson. The board was built by Frank Camaratta, owner of House of Staunton, who accompanied me on the trip.

Ed Trice
Posts: 99
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 20, 2017 5:51 pm

Daniel Anulliero wrote: So I think it's a lot useless to work on a solved game
By the way, my chess program, The Sniper, ended its USCF career with a 2100+ rating having run on 6 MHz and 16 MHz processors on a Mac with 512K of RAM in 1987.

There's still many unsolved questions in checkers, even if you have a win-loss-draw database. Take this position for example:

Image

My program instantly sees it wins in 97-ply (49 moves) for white. It's 3 kings + 1 checker vs. 3 kings + 1 checker, and white can't win unless the red checker is forced to move since his own checker is sunk in the dog hole.

Even when I let my WCC program search on "infinite" with the 8-piece win-loss-draw database probed in RAM, occasionally forcing it to move along the way, the very shortest win it could come up with is 103-ply, after quite a while.

Long search = still not optimal play vs. instant optimal play.

Which is better?

I'll go with the instantaneous perfect solution, something no other programs are capable of doing in checkers.

Cardoso
Posts: 275
Joined: Thu Mar 16, 2006 6:39 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Cardoso » Thu Feb 23, 2017 1:04 am

That's what I like in DTW TBs, instant play.
Also at interior nodes, in a win/loss position just returning the DTW value adjusted to the current ply is so simple.
Another really great thing I like is that you can generate a very long pv by probing repeatedly the DTW TB until the final winning position.
All you need is an initial long enough pv that terminates in a position that is on the DTW TBs , and from there you can continue appending the "best" moves found in the TBs, really really great. Sometimes you get spectacularly long pvs even when the root position has several pieces more than your TBs.
You can't do that with WDL TBs only.
What I don't like is poor compression ratio, and to a less extent generation time wich is bigger than WDL TBs.
As I said in another post my first attempt to generating TBs for the portuguese variation of the game was the DTW flavor, only later I did the WDL, so currently I have the 9man WDL (14GB) and the 8man DTW (46GB), all using the leading checker (not rank) subdivision and both compressed and with the option to load them into RAM or using memory mapped files.

best regards,
Alvaro

Post Reply