wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Checkers Solved
        
(Message started by: ThudanBlunder on Jul 20^th, 2007, 2:48am)

Title: Checkers Solved
Post by ThudanBlunder on Jul 20^th, 2007, 2:48am

http://chessbase.com/newsdetail.asp?newsid=3997

Title: Re: Checkers Solved
Post by ima1trkpny on Jul 20^th, 2007, 7:39am

That rather takes the fun out of it... :(

Title: Re: Checkers Solved
Post by Sameer on Jul 20^th, 2007, 8:36am

They claim it will help in fast database searches.. hmm.. Google might be interested..

Title: Re: Checkers Solved
Post by Barukh on Jul 20^th, 2007, 8:39am

What about international checkers?

Title: Re: Checkers Solved
Post by ThudanBlunder on Jul 20^th, 2007, 10:36am

on 07/20/07 at 08:39:15, Barukh wrote:

What about international checkers?

I have no doubt that international checkers is also a forced draw; same for chess. The opening advantage is simply not great enough for the first player. After all, even tic-tac-toe (noughts and crosses) is a draw.

Othello (aka Reversi) is possibly next on his list. It will be interesting to find out which player has the advantage.

Marion Tinsley (http://www.wylliedraughts.com/Tinsley.htm)

Title: Re: Checkers Solved
Post by TenaliRaman on Jul 21^st, 2007, 5:18am

My masters thesis was on reinforcement learning and i have been studying these games in quite a bit of detail. However, this result is quite unexpected (its not much of a surprise being as inexperienced as i am).

On a side note ->
I was reading the link on Dr. Marion Tinsley given above. I am completely fascinated with this guy. I am beginning to wonder whether explicit memorisation of games is the only answer to successful play (i am talking in the context of both, human play and machine play). However, its fascinating to hear Dr. Tinsley say "i just know the right move". Being a professor of mathematics, i believe he must have spend atleast some time in retrospection, trying to analyse his abilities and motivation for his gameplay. Isnt this quite a common pattern of thought amongst all good players (i mean across all games)?? It seems that learning in these cases is almost inherent, so much so that it escapes the conscious part of our mind which by the way is spending its time analysing particular games and techniques.

-- AI

Title: Re: Checkers Solved
Post by ThudanBlunder on Jul 21^st, 2007, 8:24pm

on 07/21/07 at 05:18:04, TenaliRaman wrote:

However, this result is quite unexpected.

What result? That best play results in a draw? I don't think that was unexpected by many.

Quote:

However, its fascinating to hear Dr. Tinsley say "i just know the right move".
-- AI

In checkers, as in chess, instant pattern recognition is a prerequisite for strong play.

on 07/21/07 at 05:18:04, TenaliRaman wrote:

My masters thesis was on reinforcement learning and i have been studying these games in quite a bit of detail.
-- AI

Here is an interesting paper (http://www.cs.ualberta.ca/~jonathan/Papers/Papers/ijcai05checkers.pdf). It seems to have been written in 2005 yet has an error on the very first page where it claims that it is impossible to arrive at a position with 24 kings.

But this was refuted in 2004 by Thud, Blunder, et al (http://tinyurl.com/3c7k6a). 8)
Edit: Dammit, I edited the post and the game score collapsed. The forum's functionality is not what it used to be.

Solved Board Games (http://en.wikipedia.org/wiki/Solved_board_games)

Title: Re: Checkers Solved
Post by ThudanBlunder on Jul 22^nd, 2007, 3:54pm

Quote:

I was reading the link on Dr. Marion Tinsley given above. I am completely fascinated with this guy.

Here (http://www.bobnewell.net/filez/mft.zip) is an interesting ebook about him. :)

Title: Re: Checkers Solved
Post by ThudanBlunder on Jul 22^nd, 2007, 9:07pm

http://www.guardian.co.uk/gambling/story/0,,2132455,00.html

Title: Re: Checkers Solved
Post by JohanC on Jul 23^rd, 2007, 3:16am

on 07/21/07 at 20:24:06, ThudanBlunder wrote:

Hi, T&B,
If I understand that 2005 paper correctly, they mean that the 24 kings position is never reached in their search tree. They don't need to. They don't have an answer to every possible position, only to the ones that can be reached if their program is allowed to make its moves starting from the official starting position. Each time, they have a "good enough" answer to whichever move of their opponent. For example, they don't allow the game to start with one or more random moves.
Cheers,
Johan