hatchcliff Posted March 8, 2013 Share Posted March 8, 2013 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 3 Quote Link to comment Share on other sites More sharing options...
ascrnet Posted March 18, 2013 Share Posted March 18, 2013 Thanks for sharing your new experience in action!, Each time I like this programming language. regards Quote Link to comment Share on other sites More sharing options...
hatchcliff Posted March 22, 2013 Author Share Posted March 22, 2013 (edited) 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 1 Quote Link to comment Share on other sites More sharing options...
danwinslow Posted March 25, 2013 Share Posted March 25, 2013 Probably they were put in to add familiarity for people unused to pointer concepts and used to BASIC. Quote Link to comment Share on other sites More sharing options...
hatchcliff Posted March 27, 2013 Author Share Posted March 27, 2013 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. Quote Link to comment Share on other sites More sharing options...
8bit-guy Posted April 6, 2013 Share Posted April 6, 2013 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 Quote Link to comment Share on other sites More sharing options...
Gury Posted April 8, 2013 Share Posted April 8, 2013 Great, thanks! Quote Link to comment Share on other sites More sharing options...
devwebcl Posted March 30, 2014 Share Posted March 30, 2014 Do you have an screenshot with a solution found ? Quote Link to comment Share on other sites More sharing options...
hatchcliff Posted March 30, 2014 Author Share Posted March 30, 2014 Here it is: The display isn't static. It replays the solution in an endless loop until you press break. Quote Link to comment Share on other sites More sharing options...
devwebcl Posted March 30, 2014 Share Posted March 30, 2014 nice Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.