------------ |Sea Wars II | |Will Stokes | |AI Summary | ------------ How The Game Works: ------------------- This project is about AI, not about making games, so I won't elaborate on how the other subprograms of Sea Wars II work. Here I'll simply give a small summart of what each program does. This will be followed by an in depth explanation of CSEL.85p, the AI of the game. BATTLESH.85p -This is the program you first run. It makes the board, has the computer place its ships (so yes, there is a little 'AI' here I suppose), and has the overall while loop from which the Person-Selection and Computer-Selection routines are called. CSEL.85p -This is the AI itself. In a nutshell, csel stands for computer selection program, in which the computer first picks a square to shoot at, and then actually does. DMAP.85p -This is a very simple small program. It just draws the map. MMM.85p -This is the messanging program. Basically, look at it at the source code and you'll see it uses two global variables. (If you don't know what I mean by global, just understand that they are created in another program, and tested in MMM.85p). MSG decides what message to display (e.g. Hit or Miss) and MSG2 decides if a ship has been sunk. PICK.85p -Small program that draws selection square, takes input, moves selection square around, and stops running when you press enter to fire. It saves the current position of the firing square in variables X and Y. PICK2.85p -Very similar to PICK. This programs allows you to position your ships. SPOT.85p -This draws the stupid x's in the intro scene. USEL.85p -This is the user selection program. Pretty simple as well, just uses the PICK program to get a spot, then checks to see if you can acutally shoot there. Also generates messages and writes to board matrix. CSEL Explanation - The core of the AI ------------------------------------- The AI does not have learning, nor any form of neural net, or many of the snazzy things you have heard about in movies and books. See, there are two types of AI: Type 1.) These AI's are "smart." They preform logical calculations, and make logical decisions. They are not brute force, rather, they are clever and sometimes use matematical probability and discrete math to find the best possible move/decision to make. Type 2.) These AI's are like IBM's DeepBlue computer. With an awesome amount of hardware and power (not to mention speed), these AI's litterally work out a problem the brute-force method. For example, DeepBlue looks ahead several moves (I believe 5-7 but I may be wrong). To do this, it actually calls a recursive (or so I would really hope) procedure and drills down every possible path. It them compares the results and chooses the one that will genearate the best outcome. Since humans have a hard time looking that far ahead, for every possible move, it beats them. Darn computers! Sea Wars II uses a type 1 approach because: -Calculators have hardly any space to write programs -Recursive programs in basic? Unfortunately there is no such thing as a locally defined variable, so the only way to do this would be via arrays. -type one just makes more sense, it's Battleship for crying out loud -type two takes a LOT of processing power. My 85 runs at 5-6mhz, but then again it is turboed, but still, type two would never be possible on a z80, especially with my time constraints. =P So assuming you understand all that, here is the basic strategy the AI uses to choose a spot: --------------------------------------------------------------------- 1.) First the AI First scans (via two for loops) for board entires with value==6.6 means there has been a hit, and it has not been investigated much,if at all. 2.) If no board entries were found with a value of 6, it then looks for the value 7. 7 also refers to a hit, but it also implies more searching has been done around that spot. 3.) If parts 1 and 2 failed =(, the AI then "randomly" picks a spot to fire. However, the random routine is actually sorta smart. Say we have a checker board --------------- | | | | | (Note: the actual game board in Sea Wars II |---|---|---|---| is an 8x8 grid, not 4x4) | | | | | |---|---|---|---| | | | | | |---|---|---|---| | | | | | ---------------- We could shoot every single space, which would take a long and be quite dumb, or we could shoot like this: --------------- | X | | X | | X's refer to shots. As you can see, that ? mark |---|---|---|---| is a space we have not shot, however, since no | | X | | X | ships are 1 unit long (the smallest are 2 units long) |---|---|---|---| we know there is no ship there! We have just avoided | X | ? | X | | shooting half of the field!!! This means we can |---|---|---|---| "clear" sections of the board in twice the time!!! | | X | | X | ---------------- We use the technique to shoot in alternating ever-other-unit in both the row and column dimensions. If you are confused, look at the code =) 4.) If we did fid a board entry with a 6 or 7, then we did not use step 3. Since ships are not one unit long, and we assume a hit is "removed" from the board if the ship is sunk, any hits that remain mean that another ship segment is very neary by and thus we must shoot around that spot. The first case to look for is a series of hits... ?XXXX? or ? X X ? In either case, X's refer to hits and ? marks refer to spots we have not shot at. In both cases, we look for such a situation, and if it does exist, we shoot along the series of hits on either side, that way sinking ships very quickly! If neither case exists, that is, the current hit that was found is alone (extending in no directions with other hits), we use the following strategy: For example: 1 2 3 X refers to a hit and the #'s refer to surrounding spaces. 4 X 5 Since ships are never on a diagonal, we can rule out spaces 1,3, 6 7 8 6, and 8 (for this ship. We cannot say there is nothing there by by any means. We just don't have any reason to expect a ship segment to be there based on the X in the center sense they cannot be connected to each other.) So we must investiage 2,5,7, and 4. Right now I do this in an ordered fasion. I believe I do that in simply that order. That is, the AI tries to shoot those spaces in that order (by looking at which are available, that is, not shot at before). If none are available, then obviously the X is completed, so I "remove" it by replacing it with the value 8. The last part of the AI involves ship removal. If we sink a ship (it tells us if we have), then we should remove it from the board by replacing it with an 8. We also remove the space just next to it if there is only one 6 or 7 value adjacent... For example: 0000 6680 0 refers to a miss. 8 is the spot we just hit and 0000 found out we sunk the ship. In thise case, we will also make the 6 just to the left of it an 8, since a.) there are no other 6/7's around it b.) ships are >=2 segments long. Finally, we always replace all spots with a 7 along that one direction if it exists. This places priority on other hits (if they exist), which refer to ships that more likely have not been sunk just yet.