Hello everybody. Here is version 1.10 of my Othello/Reversi game Stello (ST-Othello or Super-Othello or whatever you like best). Files: README (short description of stello) STELLO.PRG (Othello for 68000) STELLO30.PRG (Othello for 68030) STEENG.RSC (english rsc.) STEGER.GER (german rsc.) STEDAN.RSC (danish rsc.) BLACK.LIB (black opening lib) WHITE.LIB (white opening lib) DISCS\*.BIN (different discs) BOARD\COL2\*.IMG (pictures for 2 colors) BOARD\COL4\*.IMG (pictures for 4 colors) BOARD\COL16\*.IMG (pictures for 16 colors) DOC\REGISTER.TXT (Send this to me please) DOC\STELLO.TXT (you are reading it) DOC\WHATSNEW (what is new in this version) GAM\BADPOS.GAM (set response time to infinity and wait) GAM\PLY22.GAM do GAM\END.GAM do GAM\WOW64.GAM do History: 5 years ago. Beeing very interested in game theory, and the game of Othello, i had (in vain) for a long time searched for a good and strong implementation of this game for the Atari computer line. Not succeding i said to myself, why not write one myself. Had i known how difficult and timeconsuming it would be, i would probably not had started. Anyway i bought a book called advanced Pascal in which there was a tiny othello game. It was quickly adopted to my atari computer, and of cause then i played some matches against it. What a bommer!! It played so bad that i could not belive it. Looking at the source code i had to admit that i really didn't understand what was going on. I needed to learn about the fundamentals before i could make a better program. I then began to study the theory behind game playing, such as the alfa/beta minimax algorithm and many other related objects. During the next two years i developed the fundamental algorithms, and implemented it in Pascal, and where it was needed for speed in assembler. Writing in Prospero Pascal was not anything i would whish for my worst enemies. After two years of work (in my spare time) i had a working version of a Othello game which had a primitive Gem interface. The searching algorithms were quite good, but the "brain" was not working so good. Once in a while it would loose control of the game due to something that i didn't quite understand. You must understand, that while i tried to make my program better, i also had to develop my own understanding of the game. I can clearly say that it had made me a much better Othello player to write this program. In these two years i concentrated on learning the theory behind the searching algoritmes and the different techniques to optimize the minimax algorithme. (There is still room for improvement, for example it was just during the last three months that i implemented the zerowidth modifikation to minimax, and i still need to investigate the hash table techniques). What i needed was a better understanding of the game itself. Something then happend which were the major force behind the increase in playing strength during the last three years. I read an article of Paul Rosenblaum who had made a Othello program of remarkable strength. In this article he made a very good analyse of the game itself, and made some suggestions about the ways one could implement a evaluation function which could understand the features of the game. After studing his article i began implmenting his ideas and improving upon them. Eureka, my program got much stronger. Programming in pascal was not fun any more, so i switched to Turbo C, and later to Pure C. What a joy programming now was, compiling the program was now a matter of seconds compared to minutes. The last two years whent by, and i improved the interface beyond recognation and optimized the shit out of the searching algorithms. The brain got a facelift, which means that i implemented some ideas of my own, that made a much stronger player of the program. I did this by making the program avoid the inherently unstable evaluations which most othello programs do, and that really made it come up amongst the best programs in the world. So now here it is. After five years of development i will release it as Shareware. i really hope thet you will enyoy it, and that you will gratify a hardworking programmer with his modest shareware fee. Tecnicals: The search is based on the alfa/beta - minimax algorithm. It uses several heuristics to improve the search strategi. Iterative deepening, response killer table, saving the game tree (all moves are saved, as long as there is memory, the program reserves all memery except 10%, so if you have 4 megabyte it could take 3.6 megabyte for the tree of moves alone) and sorting the moves dynamically when everything else fails. This reduces the brancing factor to between 3.0 to 4.5. It really depends on the position. In the end game the banching factor is between 1.8 to 2.4. The evaluation is based on several independent components, such as mobility, stability and corner and edge disks. The program is capable of solving most endgame positions when there is only 16-14 moves left (depending on computer and position, some positions can be solved when 20 moves are missing). It does so by using the highly optimized search algoritms, which in the end game is improved with the recursive zerowidth alfa/beta-minimax algorithm. On a TT the endgame routine searches the game tree, with 15000-20000 nodes per. second. A TT has a clock of 32 MH. A instruction neads at least 2 clock cycles to complete. This gives 32000000/(20000*2) = 800 instructions per node. For every node the program has to sort the moves, make at least one move and evaluate the move. Then call itself recursively to do so for the rest of the nodes. Doing so in just 800 instructions is, in my own opinion, rather good. The speed of the normal search is 1500-4500 nodes pr second. You can not really compare this with other programs, as it depends on the evaluation function. My evaluation function, dosen't just evaluate one node, but investigates the possible responds and counterresponds to be sure that the position is approximately stable, wich really improves the playing strenght.. Playing strength: To test how strong my program was, i made a little testmatch against the program Thor. Thor is one of the best Othollo playing programs in the world, having participated in several turnements, and usally ending amongst the top programs. I made the two programs play 10 different positions against each other, as both black and white. This is 20 games in all. The play level was turnement, which means 30 min for one game. The results follow. Stello Thor Thor Stello | Black | p | White | p | Black | p | White | p | --------------------------------------------------------------- game 1. | 41 | 1 | 23 | 0 | 44 | 1 | 20 | 0 | game 2. | 30 | 0 | 33 | 1 | 7 | 0 | 57 | 1 | game 3. | 54 | 1 | 10 | 0 | 14 | 0 | 50 | 1 | game 4. | 53 | 1 | 11 | 0 | 15 | 0 | 49 | 1 | game 5. | 58 | 1 | 6 | 0 | 27 | 0 | 37 | 1 | game 6. | 22 | 0 | 42 | 1 | 19 | 0 | 45 | 1 | game 7. | 38 | 1 | 26 | 0 | 19 | 0 | 45 | 1 | game 8. | 25 | 0 | 39 | 1 | 23 | 0 | 41 | 1 | game 9. | 29 | 0 | 35 | 1 | 24 | 0 | 40 | 1 | game 10. | 37 | 1 | 27 | 0 | 22 | 0 | 42 | 1 | -------------------------------------------------------------- Total: | 38.7 | 6 | 25.2 | 4 | 21.4 | 1 | 42.6 | 9 | Stello Thor Discs p Discs P Total: | 40.7 | 15 | 23.3 | 5 | ------------------------------------- The theory behind Othello suggests that it is better to have white. This means that one would suspect the white side to win. If you look at the results you will see, that my program as white wins 9-1 !!. But even as black it manages to win by 6-4. All in all a victory by 15-5. I must emphase that this is by no means a bashing of Thor. I really belive that it is a excelent Othello player, and i admire the work that has been put in that program. One could probobly find 10 other positions where the result would be different, i can only say that these positions were the first 10 to be reached by playing the two programs against each other. My conclusions are, in retrospekt of the results, you can say that my program playes Othello at Master level. -----------Update: Match against Thor v 3.36. (july 1994)--------------- The last match was against thor v 3.33, and in the meantime the authors behind Thor have improved the program. As far as i can see it searches somewhat faster, and it dosen't anymore occasionally make a bad move. Furthermore the endgameroutine is 2-3 times faster. I made the same match with the same 10 different openings. The new result was. Stello Thor 3.36 Thor 3.36 Stello | Black | p | White | p | Black | p | White | p | --------------------------------------------------------------- game 1. | 52 | 1 | 12 | 0 | 32 |1/2| 32 |1/2| game 2. | 46 | 1 | 18 | 0 | 32 |1/2| 32 |1/2| game 3. | 24 | 0 | 40 | 1 | 21 | 0 | 43 | 1 | game 4. | 55 | 1 | 9 | 0 | 30 | 0 | 34 | 1 | game 5. | 27 | 0 | 37 | 1 | 23 | 0 | 41 | 1 | game 6. | 32 |1/2| 32 |1/2| 19 | 0 | 45 | 1 | game 7. | 26 | 0 | 38 | 1 | 21 | 0 | 43 | 1 | game 8. | 35 | 1 | 29 | 0 | 52 | 1 | 12 | 0 | game 9. | 32 |1/2| 32 |1/2| 31 | 0 | 33 | 1 | game 10. | 39 | 1 | 25 | 0 | 28 | 0 | 36 | 1 | -------------------------------------------------------------- Total: | 36.8 | 6 | 27.2 | 4 | 28.9 | 2 | 35.1 | 8 | Stello Thor 3.36 Discs p Discs P Total: | 36.0 | 14 | 28.0 | 6 | As we can see, the outcome in points is almost identical to the last testmatch. Stello wins 14-6. If we analyse the games in more detail we can see that it now is a much closer match. The disc differential now is 8 discs, where it in the last match was 17 discs. We can see that Thor really has improved. Maybe i should start implementing some of those new ideas that i have been thinking about. -----------------------------Update end--------------------------------- One of the more facinating things about Stello, and gameplaying in general, is that i can't beat it anymore. I have a complete understanding of why it makes its moves, but i don't have the same memory and processing power as the computer. In the game of Othello the computer has a bigger advantage than for example in chess or chekers, as the positions change so quickly. In a sense you could say that the computer have outmastered me. Then again i can always pull the plug. 8-). Interface: The interface is completely GEM controlled, so that the game should run in all graphic resolutions (x resolution must be at least 640), and on all Atari computers. It uses some of the features in the new multitos, such as iconification of the windows (AES 4.1), 3d look, buttom windows etc. It is possible to load a bacground picture, if the picture is in GEM-XIMG format. If you are in 16 color resolution it must be a 16 color picture of size 256x256. Some pictures are included, for 2,4 and 16 color modes. It also supports WINX. ---------------------update july 1994 stello v1.1----------------------- By popular demand (my own 8-) i have put the dialogs in windows. This means, that the program dosent hog the computer when showing dialogs. A side effect is that under normal tos it almost feels like multitasking, as the computer continues thinking while you are using the dialogs. You can now have 3D activator and indicator buttons under normal tos, 3D checkboxes and niceline menus. -------------------------------update end------------------------------- Multitasking: The first versions of my program had the normal structure of a gem program. A event_multi loop, to interact with the user, and then when you made a move the computer would begin thinking and the interface would freeze until the computer had finished claculating. It was rather irritating to see the clock stop working, not beeing able to move the windows or do anything else while the computer was thinking. I had to develop a technique to allow a sort of quasimultitasking. What i did was to implement corutines. I started by implementing a interrupt routine (timer A) to update the clock and a internal variable, that meant i didn' need to make a systemcall 1000 times a second to check the clock. Of cause i could have made a even_multi call in my recursive minimax routine, but i didn't like to mess up the nice structure of my program by making interface calls in the brain of the program. I was programming the interface and brain as two independent units. Later on when i used the features of multitos it turned out, that it was much easier to implement multitasking as i already had programmed the interface to look at the brain as an independent task. In the minimax routine i check if the timeslice for the brain has been used, if so i do a context switch to the event_multi loop, which checks if there are any messages. If there are it does the appropriate thing, and then turns control over to the brain again. In practice it seems just as multitasking. The interface and the brain has their own stack and communicates via global variables. Under Multitos the interface and the "brain" is running as two independent tasks. This means, that you cannot interrupt the brain, by for example showing a dialog in another program. It also means, that you can move the windows, update the clock, and anything else the interface will allow you. Isn't multitasking wonderfull. Under multitos the brain and interface communicate via signals and by sending messages via appl_write. That is the reason, that the brain is shown in the menu under multitos. I had to make the brain a Gem application, as the interface is wating in a event_multi loop for a message, and the only nice way to tell it that the brain has finished, was to send it a message via appl_write. I could have made a global variable, and made a event_multi call with a small timer value, but my goal was a interface that didn't use any unnecessary time under multitos. The program supports WINX by using wind_update's check and set mode. This means, that the interface doesn't stop when it tries to update the clock or the analyse window, and someone else has control over the update semafor, but just turns control over to the brain. This solution isn't perfect, but much nicer than to see everything freeze. The perfect solution is to use multitos. This must be one of the first programs on the atari computers to make a really good use of multitasking. If you have a shell, and the program "top", you can follow how the program multitasks. Help for interface: Menu "File" New game: Starts a new game. Load game: Loads a previosly saved game. Save game: Saves current game. Stop: Stop playing. Menu "Game" Computer/human: Play against the computer. Computer/computer Computer playes itself. Human/human Play against another person. Menu "Level" Plyes ahead: Computer thinks until a given search depht limit is reached. Time for one move: Computer thinks until a given time limit is reached. It tries to make inteligent use of the time, so it will somtimes respond faster when it sees, that it cannot make a deeper search within the current timelimit. Time for one game: Set the time for one game, and the computer makes the best use of this time. It means that it uses more time at stages in the game where it is importent, this is the level which should be used to play a normal game, the others are basicly for analyses. Openings lib: Turns on/of the openings lib. Menu "Move" Forward: Move forvard one position in game: Back: Move one position back in game. Move now: Interrupt thinking, and move now. Change sides: Change sides. Next best: Make next best move. Hint: Suggest a move. Meny "Options" Show move list: Show the moves, number of discs and clock in a window. Show analysis: Show some information concerning the game. Value is the internal representation of how good the computer thinks it is doing. Positive means good for the computer. When it is possible to completly solve the game, you will see this value as either "XX e" or "XX p" where "XX" is the number of disks it nows it will (when both sides plays perfect) win or lose by. The "e" means estimated and the "p" means precisely. The endgamesearch is split in two, first it tries to find a winning line, and if such a line exists, it then tries to find the line which wins by the largest margin. Nodes is how many nodes is visited in the tree. Evaluations is how many nodes that is evaluated. Time is in 1/100 sek. "d" is the current depth and current move. Move shows the current best line of moves. Reversi setup: Make your own position. Dobble click to empty the board. Left mouse button puts a black disc on the board, right mouse puts a white disc on board, and pressing Control and left mouse button clears the board where the mouse currently is. Zero clock: Reset clock. Print moves: Print a list of the currently played moves. Load picture: Loads a bacground picture. The picture format is any ximg picture of size 256x256 with the same number of colors as the current resolution. (St medium pics must be 256x128). Configuration: Here you can set some specific features, such as the border of the disc. With a dark bacground picture it is good to have a white border around the black discs. Show possible moves. When this option is set, the mouse changes form whenever it crosses a position where it is possible to move. When no moves are possible it changes to a "P" for pass. Continue playing by pressing the left mouse button with the cursor positioned over the board. Also pressing the right mouse button when the cursor is placed over the board, displayes all possible moves."Fast move" sets whether or not there are a flashing disc to indicate where there was moved. Animation turns on/off disc animation. Sound turns on/off the sound. Background picture turns on/off the background picture. Notation determinates which notation is used. 3D buttons switches between the old interface style buttons, and the new 3D buttons. (Doesn't show on Falcon and Multitos) Language: Switch the language. Currently supported are English, German and Danish. Save configuration: Saves the current configuration. Windows positions, size, backgroundpicture are saved. The settings under "configuration" are saved, and level of play is saved. Different configurations is saved for different screen resolutions, which means you can save one configuration for mono and one for VGA ect. The program determinates at startup which one it must use. Future: Current plans for Stello 2.0 is - support drag an drop protocol - load a game by clicking it - implement the zerowidth alfa-beta mini-max algorithm for the normal search (already implemented in the endgame search) - implement hash tabels if it gives anything - improving the brain (it can always get better can't it 8-) - better output for the printer - support for transcripted games - whatever you suggests The implementation of these improvements really is in your hands, i must have a satisfactory response before i can find the time to make them. A man must earn a living ;-). If there is enough of responses, i would even consider making other strategic games such as chekers, five in a row or what you most would like, see REGISTER.TXT Thanks and gretting too: Klaus Pedersen for beta testing. The players on the socker team. Helle Demant, S³ren Warberg, Lone Poulsen and Henrik Jensen for moral support. Paul Rosenblaum for his excellent articel about Iago. Sylvain Quin, Bruno de la Boisserie and Jean-Jacques Michel for producing the excellent program Thor. All my friends in Veflinge. The twins. (Nobody can party like them.) My parents and my brother. Shareware: STELLO is Shareware. The program may only be distributed without charge. For example, commercial public domain libraries, magazines, publishing companies and software companies may only spread Stello with my prior written permission. Stello may be uploaded to BBSs that do not charge for downloads. Both the program and the documentation must remain together and unchanged. The stello CFG file must NOT under any circumstances be distributed as the registered version contains your personal key details. It is very easy to register, just fill the formular in the file REGISTER.TXT, and send it to me. I will then send you a key, which will free you from the annoying register dialog that keeps popping up. Bugs/comments: If you find a bug, or have any suggestions concerning the program, you are welcome to send me a letter. My adress is as follows: Claus J. Pedersen V‘devej 42 5462 Morud Denmark Or you can reach me on internet by E-mail at atari@imada.ou.dk ---------------------------------------------------------------------- Hate has a reason for everything But love is unreasonable. ----------------------------------------------------------------------