Solitaire in Action!

[hatchcliff]

This Action program solves the board game solitaire:

 

Action Solitaire.ATR

 

I wrote several versions of this in different languages in the 1980's when I was learning about recursion and game theory, but this one is my favourite because it was the first that actually succeeded in solving the game - by searching millions of moves over the course of several days.

 

I liked Action because of its speed and structure, and I certainly think it deserves its place in 8 bit history. I hope this solitaire program qualifies as an interesting piece of retro-software and illustrates some of Action's strengths.

 

There are two program files on the ATR disc image:

 

SOLIT.ACT contains the source code. It can be compiled and run using the Action cartridge. My 800XL, 65XE and 130XE can all compile the program from the editor buffer, but it is close to the maximum size that can be handled this way and, depending on the configuration of your machine, you might run out of code space (error 14). If this happens, clear the editor and compile from disc.

 

SOLIT.OBJ is a compiled object that can be loaded and run from DOS without the cartridge (my thanks to Kevin Savetz for describing how to make these object files in his blog).

 

The program also works in emulation. I've tried it with AtariWin800 Plus 4.1, and Altirra 2.20 (which produces the closest match to the original PAL display).

 

 

When it is run the program immediately starts to search. It displays the starting position and the current search position, also the number of moves examined, the depth of recursive calls (with an up/down arrow to show whether the depth decreased/increased on the last call), and an "x" if the last position was cut (pruning all its sub-branches from the game tree).

 

The program processes about 200 moves per minute, but it spends more time updating the display than searching. In attract mode it speeds up to around 1000 moves per minute by skipping all the display routines and turning off ANTIC. In this state you just see a blank screen cycling through the attract colours (it looks as though the program has crashed, but it is actually searching in overdrive). You can check the progress of the search at any time by pressing any key (except break) to bring the machine out of attract mode. When it eventually finds the solution, the program automatically switches ANTIC back on and displays it.

 

The program works by scanning the board systematically from left to right, and top to bottom, considering moves in the north, east, south and west directions. It calls solit() to see if each proposed move is possible. If it is not, solit() returns without doing anything. If it is, it executes the move, generating a new board position which it places on a stack; then it scans the new position, calling itself to examine possible moves, and so on. After each move it checks for the solution (a single pin remaining in the central hole) and sets a flag to terminate the search when it is found.

 

A procedure called treesaw() is called to examine every new board position. If it judges that the pins are too spread out to lead to the solution it causes solit() to return without searching further. This prunes hopeless positions from the tree and roughly halves the size of the search. The spread is expressed as the sum of the sides of an imaginary rectangle enclosing all the pins. There is nothing mathematically precise about the algorithm used in treesaw(). I designed it by just playing around with pins on the board and trying to establish reasonable thresholds, erring on the safe side to avoid accidentally pruning off the solution.

 

Action has many good features and a few awkward ones too (although I believe these are all the result of reasonable design compromises). In particular, the representation of the board cries out for a two dimensional array, but these are not supported, so it has to be mapped onto a one dimensional array instead.

 

I recall thinking that Action's lack of support for automatic variables would be a problem in the recursive application, but although it means that some extra code is required to support the stack, there are advantages in working this way. In particular, all the stacked variables are retained as the recursive calls unwind (and not discarded, as would be the case with automatic variables). So the whole solution remains available for reference when the search has ended. The program uses this feature to replay the solution in an endless loop.

 

I always knew that game trees tend to be large, but I was surprised to find that solving such a simple game involved searching millions of moves. Later I discovered that this is a bit of an illusion because in solitaire there are often many different routes to the same position - so the tree contains duplicates and the program spends a lot of time searching these repeatedly. It would be possible to reduce the search by a factor of 10 by extending the pruning algorithm to recognise and reject duplicates.

 

One thing that really impressed me was the speed with which Action raced through the moves (about 100 times quicker than Basic) - and my sense of awe only increased in subsequent years, as successive platforms ran the program quicker and quicker. My current PC, running C, solves the game in less than 10 seconds; and with improved pruning, less than 1 second. However, such extreme speed conceals what's going on, and in my opinion these programs have none of the charm of the Action version - but this is pure nostalgia, I know.

 

Best Regards to All

 

Cliff

[ascrnet]

Thanks for sharing your new experience in action!, Each time I like this programming language.

 

regards

[hatchcliff]

Thanks for your reply - I’m glad you liked the program.

 

Actually, it’s not very new - I wrote it in 1986 and just added a single comment about the runtime library before posting it.

 

I never found a way to share it in those pre-internet days, although I did manage to publish a Sinclair QL Basic version in Personal Computer World. It’s a pleasure to share the Action version now through the forum.

 

Looking at the program again after so many years reminded me of a question I had:

 

Why does Action have Peek and Poke functions?

 

Does anyone know the answer to this? They appear to be redundant because the language has very neat syntax for declaring variables that reside at specified memory locations, like this:

 

BYTE sdmctl=$022F

 

So any location can be accessed as an ordinary variable.

 

Action also supports pointers, so if you want to process lists (arrays, stacks, PM tables etc.) all you need is a pointer to the start, and you can work from this to access all the members - and, of course, you can access arrays with subscripts too.

 

I used these methods a lot in the Solitaire program, and never needed to resort to Peek or Poke.

Edited March 22, 2013 by cliffh

[danwinslow]

Probably they were put in to add familiarity for people unused to pointer concepts and used to BASIC.

[hatchcliff]

Yes, I think that must be the reason.

 

It just struck me as curious. Action was beautifully crafted for speed and compactness, so it’s a surprise to find some apparently redundant functions embedded in it.

[8bit-guy]

This Action program solves the board game solitaire:

 

Action Solitaire.ATR

 

I wrote several versions of this in different languages in the 1980's when I was learning about recursion and game theory, but this one is my favourite because it was the first that actually succeeded in solving the game - by searching millions of moves over the course of several days.

 

I liked Action because of its speed and structure, and I certainly think it deserves its place in 8 bit history. I hope this solitaire program qualifies as an interesting piece of retro-software and illustrates some of Action's strengths.

 

There are two program files on the ATR disc image:

 

SOLIT.ACT contains the source code. It can be compiled and run using the Action cartridge. My 800XL, 65XE and 130XE can all compile the program from the editor buffer, but it is close to the maximum size that can be handled this way and, depending on the configuration of your machine, you might run out of code space (error 14). If this happens, clear the editor and compile from disc.

 

SOLIT.OBJ is a compiled object that can be loaded and run from DOS without the cartridge (my thanks to Kevin Savetz for describing how to make these object files in his blog).

 

The program also works in emulation. I've tried it with AtariWin800 Plus 4.1, and Altirra 2.20 (which produces the closest match to the original PAL display).

 

 

 

When it is run the program immediately starts to search. It displays the starting position and the current search position, also the number of moves examined, the depth of recursive calls (with an up/down arrow to show whether the depth decreased/increased on the last call), and an "x" if the last position was cut (pruning all its sub-branches from the game tree).

 

The program processes about 200 moves per minute, but it spends more time updating the display than searching. In attract mode it speeds up to around 1000 moves per minute by skipping all the display routines and turning off ANTIC. In this state you just see a blank screen cycling through the attract colours (it looks as though the program has crashed, but it is actually searching in overdrive). You can check the progress of the search at any time by pressing any key (except break) to bring the machine out of attract mode. When it eventually finds the solution, the program automatically switches ANTIC back on and displays it.

 

The program works by scanning the board systematically from left to right, and top to bottom, considering moves in the north, east, south and west directions. It calls solit() to see if each proposed move is possible. If it is not, solit() returns without doing anything. If it is, it executes the move, generating a new board position which it places on a stack; then it scans the new position, calling itself to examine possible moves, and so on. After each move it checks for the solution (a single pin remaining in the central hole) and sets a flag to terminate the search when it is found.

 

A procedure called treesaw() is called to examine every new board position. If it judges that the pins are too spread out to lead to the solution it causes solit() to return without searching further. This prunes hopeless positions from the tree and roughly halves the size of the search. The spread is expressed as the sum of the sides of an imaginary rectangle enclosing all the pins. There is nothing mathematically precise about the algorithm used in treesaw(). I designed it by just playing around with pins on the board and trying to establish reasonable thresholds, erring on the safe side to avoid accidentally pruning off the solution.

 

Action has many good features and a few awkward ones too (although I believe these are all the result of reasonable design compromises). In particular, the representation of the board cries out for a two dimensional array, but these are not supported, so it has to be mapped onto a one dimensional array instead.

 

I recall thinking that Action's lack of support for automatic variables would be a problem in the recursive application, but although it means that some extra code is required to support the stack, there are advantages in working this way. In particular, all the stacked variables are retained as the recursive calls unwind (and not discarded, as would be the case with automatic variables). So the whole solution remains available for reference when the search has ended. The program uses this feature to replay the solution in an endless loop.

 

I always knew that game trees tend to be large, but I was surprised to find that solving such a simple game involved searching millions of moves. Later I discovered that this is a bit of an illusion because in solitaire there are often many different routes to the same position - so the tree contains duplicates and the program spends a lot of time searching these repeatedly. It would be possible to reduce the search by a factor of 10 by extending the pruning algorithm to recognise and reject duplicates.

 

One thing that really impressed me was the speed with which Action raced through the moves (about 100 times quicker than Basic) - and my sense of awe only increased in subsequent years, as successive platforms ran the program quicker and quicker. My current PC, running C, solves the game in less than 10 seconds; and with improved pruning, less than 1 second. However, such extreme speed conceals what's going on, and in my opinion these programs have none of the charm of the Action version - but this is pure nostalgia, I know.

 

Best Regards to All

 

Cliff

 

thank you very much indeed

[Gury]

Great, thanks!

[devwebcl]

Do you have an screenshot with a solution found ?

[hatchcliff]

Here it is:

The display isn't static. It replays the solution in an endless loop until you press break.

 

[devwebcl]

nice