Draughts/Checkers

[gtoal]

A couple of weeks ago, I was musing on an old photo from my student days, of a VT15 terminal attached to a PDP15, which was displaying a vector Chess game.  So I thought I would find some chess engine on the net and add Vectrex graphics to it and have a chess game on the Vectrex.  Well, I couldn't find the original DEC graphics and had to design a vector chess set myself, which I posted on the FB group for comments.  Turns out one of the group (Roger Boesch) was already working on a chess engine for the Vectrex, but hadn't started on the graphics yet - so I donated my graphics and left the creation of a game to him... and looked for another project to take on.  Obvious first thing that came to mind... Draughts (checkers).

Fortunately an old pal from my student days had written a pretty definitive draughts engine back in the 70's.  Being old it had the advantage of a small footprint, while still being pretty powerful.  It was actually originally a learning AI that played humans and played itself to improve, and the final version was encapsulated in half a dozen constants used as weights for different board evaluation factors.  This meant that all the learning code could be omitted and replaced by 6 constants :-)

I started the port 8 days ago - first from Imp (an Algol60-like language) to C, then a lot of restructuring to make it compatible with a polled game loop instead of imperative flow control.  A couple of days spent reducing the RAM footprint even farther, to allow the minimax to evaluate 12 plies, and a few days of debugging (problems caused by conversion from a 32-bit system to an 8-bit system) ... and seven days later we have a working draughts game.

The credit for the game goes entirely to my friend Ken Chisholm, from Edinburgh, and his original program, "Draft4".  (He's now on Draft5 I think, which uses a genetic algorithm to improve mid-game play).

Working on this was like being back at work after a 6 year retirement... late nights to meet a hard (self-imposed) deadline of getting it out on Christmas Day for you all to enjoy:  

                                                           gtoal.com/vectrex/chess/draft4-xmas.bin

I got it working at 2am on Christmas morning; it has not been extensively tested!

(Do me a favour and don't upload this version to any other sites - I'll make another release with a better UI etc under less time pressure in the new year.)

You select the square you are going to move from with button 4, move to where you want to drop the man using the joystick, and place it using button 4 again.  If you change your mind or get confused you can cancel the selected square with button 3.  Holding button 3 down for an extended period brings up an option to resign.

You decide who plays first initially with button 1 or button 2, and subsequent games alternate.

The display is mostly suppressed while the AI is thinking.  If I didn't do that, the thinking time would be unpleasantly long.

Have fun,

Graham

[D-Type]

Nice one Graham...12 plies! Does it evaluate them every move? Checkers doesn't have as many moves as Chess, but I guess the numbers could still add up pretty quick.

Quick turnaround too, self-inflicted "crunch mode". I remember it only too well, even though I haven't coded anything professionally for many years.

[gtoal]

Dec 25, 2020 12:00:08 GMT -5 D-Type said:

Nice one Graham...12 plies! Does it evaluate them every move? I guess checkers doesn't have as many moves as Chess, but I guess the numbers could still add up pretty quick.

The 12 ply depth is only in 'hot pursuit' mode - which works, as it tricked me into a move that let it do a triple jump on me :-)

Here's Ken Chisholm's notes on the original program:


The Draughts Program Draft4



Draft4 was the fourth version of a Draughts program I had written.



The first version was simply a one move analyser written in FORTRAN

while I was at school, the second version was the same re-written

in algol-60. The third version was an implementation written in Imp

at Edinburgh University which included proper alpha-beta tree search

with pruning and then Draft4 was a major re-write in Imp with rote-

learning by remembering boards and their computed evaluations.



It written to be very portable and so it could run on every computer

in the CS department including the PDP-15, EMAS, the Interdatas and

the PDP-7 with its GT40 display. At the time, which was the mid-

seventies, the cpu speed of a typical processor allowed for about 2

or 3 ply search with a certain amount of hot-pursuit towards stable

board positions which sometimes extended the search to about 6 ply.



Since then it now typically searches to 6 ply in general with hot

pursuit to about 12 ply.



Draft4 was written in 1975 for my undergraduate AI2 project. With

rote-learning of boards, Draft4 quickly learned to play noticeably

better standard openings and end games such as solving the double

corner problem. One novel feature of this learning version was

searching for partial board matches near the end game which worked

quite well due to the relative immobility of draughts pieces.



For example, if it is a double corner standard win on one half of

the board and a win on the other side, such as with all the same side

pieces, it is probably a win overall.



Now of course the Canadian program Chinook has solved Draughts, or

checkers as they call it, using deep exhaustive search and a very

large opening database and end game storage using retrograde analysis.



Ken Chisholm

KJC

[kokovec]

Just logged on to this forum and found a late Christmas present!
Very cool!

[D-Type]

What a great story from Ken. I bet he didn't think his code would still be used decades later for something new. Now it was mentioned, I do recall not so long ago that I heard that Draughts had been solved. Still a fun game though :-)

This is a great Boxing Day read: www.theatlantic.com/technology/archive/2017/07/marion-tinsley-checkers/534111/