@DATABASE FourInaRow.guide @MASTER FourInaRow.guide @$VER: FourInaRow 3.0 Documentation (95.08.13) @AUTHOR "Ola Lundkvist" @(C) "Wizo" @NODE "main" "FourInaRow 3.0" FourInaRow 3.0 (93.08.27) ------------------------- @{"  Disclaimer   " LINK "Disclaimer"} @{" Distribution  " LINK "Distribution"} @{"   Shareware   " LINK "Shareware"} @{" Instructions  " LINK "Instructions"} @{"     Menus     " LINK "Menus"} @{"    History    " LINK "History"} @{" The algorithm " LINK "Algorithm"} @{"    Author     " LINK "Author"} @ENDNODE @NODE "Disclaimer" ---------------- This software is provided as is, and the author cannot be held responsible for any damage caused by this program. However this does not mean that this software is not carefully written and tested. All code is 100% systemfriendly, so nothing could possibly go wrong. @ENDNODE @NODE "Distribution" FourInaRow is ShareWare and is Copyright © 1993-94 Wizo. This means that you are allowed to spread this or include it on PD-series provided that you don't charge more than a small copy fee of maximum $5 / DM 6 / SEK 25. It's absolutely forbidden to charge more for a disk with this program on it without my personal permission. This may also be included on CD-ROM (for example AmiNet CD-releases) as long as it's not part of a commercial release, ie contains only Shareware/PD/Freeware etc. Magazines with cover-disks/CDs may include this on their disk/CD provided they send me a copy of the magazine (and disk/CD) in question. Other sorts of distribution is not allowed without my personal permission. The program may not be distributed without it's icon and this documentation. Modified versions of the program, it's icon, or this documentation may not be distributed. Distribution of the files in packed or archived form is of course also allowed. That should cover it all, if it doesn't @{" contact me " LINK "Author"} for clarification. @ENDNODE @NODE "Shareware" If you after trying this game out (for no longer than two weeks) find that you wish to keep it you should do as follows to become a registered user: 1 If you have written any useful program(s) / fun game, wether it's PD, shareware or commercial, you should send @{" me " LINK "Author"} a copy of it (fully feautured). Then you will become a registered user of all my software as well. 2 If you haven't written any software of your own either: a You're a student or don't have a job so you can't afford to pay anything for this. Therefor you are allowed to use it absolutely free, but please take a hint from paragraph 3 below. b You have some kind of job and therefor you can afford to pay for this. You can decide how much it's worth. I would suggest $5 - $10. Cash in US$, DM, £ and SEK (Swedish crowns) accepted. Cheques only in SEK. Gifts instead of money are also welcome. 3 Not doing anything of the above, but sending bug reports, nice ideas for improvements, or in other ways helping me out in developing my programs may also gain you the title of registered user. Becoming a registered user means registered for all my other released shareware software as well (currently @{" BlackBox " LINK "BlackBox.guide/main"} and @{" Tangle " LINK "Tangle.guide/main"}). So far none of my software is crippled, since I personally don't believe in crippleware. Therefor registered users will receive no new version if it doesn't exist. As soon as they will be available however, registered users will be notified or receive updates by email (If you want me to mail you a disk, you either need to register by method 1, or donate at least $10). New versions will probably be uploaded to AmiNet as well. If you feel you can't afford to pay for this you need not feel lousy, but sending a simple comment by @{" email " LINK "Author"} you could afford, right? @ENDNODE @NODE "Installation" Installation ------------ No installation needed really. Just put the executable and the icon anywhere you like. You need AmigaDOS 2.0 or later to run FourInaRow 3.0. If you don't have AmigaDOS 2.0 or later, you will have to do with version 2.1 of FourInaRow (should be included). This version contains less features and it's impossible to interupt the computer while it's thinking. However, the playing strength is the same. If you have version 38 or later of ReqTools.library it will also be used. ReqTools is Copyright (c) Nico François. (The library isn't included since you probably already have it, or you could get it from anywhere.) FourInaRow will run from Workbench as well as from CLI/Shell. OBS! If run from CLI you should set the stack to at least 8000. @ENDNODE @NODE "Instructions" Instructions ------------ The goal of FourInaRow is to get four bricks in a row horizontally, vertically or diagonally. There are two players (each player can be either human or computer), one is yellow and the other is red. You can see who is yellow and who is red in the upper right corner of the screen. Each player alternate drop a brick in one of the columns of the board. The brick will appear in the bottom of the column. The game continues until one player has four in a row or the board is full. You can see whose turn it is to the right. If it's your move just click your left mousebutton in the column where you want to drop a brick. You can also enter the figure associated with the column on the keyboard. A brick will appear and it's the other player's turn. If it's the computer's turn you will see it's thinking progress and then it will make it's move. You can see various other messages to the right: Eval is a value the computer uses - the higher it is the better it think it's position is. Level and search depth indicates how strong the computer plays, more about that later. You can also see where the last brick was played. At the bottom you can see how much time each player has used. @ENDNODE @NODE "Menus" THE MENUS --------- Notice that many of the menu choices has keyboard shortcuts Game New - Starts a new game. Undo move - Will let you undo any number of moves. (Requires RegTools.library (version 38)) About - About this game. Help - Online manual. Quit - Exit this game. Players Changeside - Whoever was yellow will be red and vice versa. Yellow is human - Yellow will be played by a human player. Yellow is Amiga - Yellow will be played by the computer. Red is human - Red will be played by a human player. Red is Amiga - Red will be played by the computer. Eval (You can ignore this whole menu.) Normal \ These are the two eval methods to choose from. Differential / Always choose differential - it's faster. Endgame inc searchdepth - See level menu below. Trace (numerical) \ Both these are of no use really, they will show Trace (graphically) / the computer thinking, making it very slow. Level - Here you can set the level from 1 to 10. The level can also be set by the slider gadget to the right. The level controls the search depth. The greater the level the better the computer plays, but the more time it uses. Increasing the level one step will increase the time for each move with about 5 times. At start level is the same as search depth but if you've set Endgame inc searchdepth, the searchdepth will increase as the computer needs less time for each move. This will give closer to using constant time for each move, and will make the computer play better at little cost. You can see both level and search depth to the right. You can select most items also when the computer is thinking and get immidiate action and the computer will cancel it's thinking. Changing level while the computer is thinking will not stop the computer thinking and it will take a little while before the search depth changes. @ENDNODE @NODE "History" History ------- This program is based on code written by me (Wizo) and Mikael Fröberg in a course in algorithmics we took this spring (93). One of the lab tasks was to write a simple program which played four in a row, based on some @{" algorithms " LINK "Algorithm"} we studied. So we did, and then I took the code home to my Amiga (500+) and compiled it. It worked fine except that it was dead slow. (It was still fast enough on the SUN Sparcstations at school). However at the end of the lab I had figured out a good way to improve the speed, so one day I started working on it at home. Soon I had a version (1.0) which was about 30 times faster than the original. Most code is rewritten, only the basic idea remained the same. And then of course I had to make a version (2.0) with a simple GUI to make it more playable. Now a year later I have made a new version (3.0) with improved GUI. It contains more features and looks a little nicer, and it's 2.0 and later only. For those who still only have 1.2/1.3 there is a version 2.1 of FourInaRow which is a slighty improved version 2.0. And if someone is interested I have actually made a windows version of FourInaRow (Just because I needed to learn a little about programming in windows for a job I had. Of course I think windows (and microsoft) sucks.) The windows version is also called FourInaRow 3.1 and is almost identical to the Amiga version (3.0). FourInaRow version history: 1.0 First version with my improved algorithm (machine independent) 2.0 Added a simple GUI 2.1 Some optimizations 3.0 Improved GUI Some more feautures Requires Kickstart 2.04 or later Added AmigaGuide documentation FourInaRow for windows version history: 3.0 Port of 3.0 3.1 A little bugfix @ENDNODE @NODE "Algorithm" About the algorithm ------------------- The program uses a simple minimax routine with alpha-beta priming. For you who don't know what that is here's an explanation: The program tries all moves for a couple of moves ahead and then examines the board trying to estimate the position with an eval value. Then it goes back one move and tries another last move and evaluates the board again etc etc. Every second move it tries to make a move which maximies the eval value and the other moves it tries to minimize the eval value. Actually it doesn't examine all moves because the alpha-beta priming means that it sorts out certain moves (ie branches in the search tree) that can't possibly affect the result. Evaluating the board is done by looking up a table row for row, column for column and diagonal for diagonal. Four in a row is worth 10000, three (not necessarily in a row but with possibilites for getting four) is worth 100 (one possible way to get four) or 200 (two possible ways to get four) and two is woth 10-20. The value is positive for the computer and negative for the human. After all these moves are tried it makes the best one. The differential eval method works a little bit different. Instead of making a couple of moves (depending on the search depth) and then evaluating the whole board it evaluates the differens for each move that is made. That is - it only needs to check one row, one column and two diagonals for each move made. It isn't hard to realize that this means a heck lot less calculations. Well this is a very brief description, but it's actually very simple so anyone with a little knowledge about programming, minimax- and alpha-beta routines could easily do this. Then of course my implementation with a precalculated table makes it quite fast. But if you know of any better/faster methods I would like to know. About the only improvements I can think of now is making the computer calculating while the human player is thinking. With the differential eval method I have used that would be easy to implement, maybe I will do that sometime. And then there is a couple of things to make it a little more intelligent. For instance having two (or more) possibilities to get for in a row if they both need playing in one particular place, isn't any better that just one possibility (see below). . . . . . . . X O O . . . . X X X . . . . <- X will get two four in a row if he gets to play here O O X . . . . but that doesn't increase his possibility to win. O X O O O X . X O O X O X X ^ | Things like this is currently not taken care of by the program. The problem is that taking care of cases like this takes a lot of time. As long as one only look at small local parts (like one row) at one time it's possible to make a fast routine like those I have made. But the above case takes comparing of several rows, columns and diagonals. The way I see it this "improvement" of the program will make it so much slower that it will play worse than now, given a certain allowed average time per move. Again if you have any ideas, which might improve the program without making it that much slower I would like to hear them. (I haven't thought about it that much myself because I think it's impossible to find any good solutions.) This program is (of course) written in C using Lattice/SAS C 5.10. Apart from this version (as mentioned before) I also have a Windows version written using Visual C++ 1.00, and a version without the GUI which will compile with about any (ANSI) C compiler in most environments. @ENDNODE @NODE "Author" "Author" If you wish to contact me here are a couple of addresses: Email: d1wizo@dtek.chalmers.se URL: http://www.dtek.chalmers.se/~d1wizo (Here you should be able to find my current address and of course the latest versions of my sotfware.) Smail: Ola Lundkvist Gibraltarg. 84:527 S-412 79 GOTHENBURG SWEDEN (Above address is temporary and will change within a year.) Alt Smail: Ola Lundkvist Ekv. 8 S-360 44 INGELSTAD SWEDEN (Will Always work, but it will mot reach me that fast.) Comments, suggestions, contributions, bug-reports or whatever - please feel free to send it to me! @ENDNODE