download
I decided to make a computerized version of Chinese Checkers for two reasons. The second reason is that my mother spends far too much time playing Solitaire and, since she loves Chinese Checkers, I was hoping to create something a little more exciting for her to waste her time on. My main impetus, however, was that I was playing the board game with my family over Christmas('07) vacation and it struck me that it would be interesting to try and create an AI algoritm capable of playing the game. For the rest of this description I will be discussing the process I followed to get my AI
algorithm
to its current state.
Note 1) I have never taken any classes in AI or read any articles on AI so if you think that I am going about it entirely incorrectly or that you could come up with a better algorithm than I did then you are probably correct.
Note 2) I am aware that professional programmers often take shortcuts when coding complicated functions. This might apply to the AI for Chinese Checkers by having the computer follow a different "thought process" depending on the situation it is in. In the early game there might be a set of good opening moves which the computer can pick from. In the end game, the computer might recognize that it is close to finishing and then fall into a predefined pattern to ensure that it moves its pieces into the goal in the quickest fashion. During the rest of the game the computer may rely on some sort of an algorithm to determine which move to make next. I am not interested in special cases. My goal is to create a "strategy" which the computer players can use to choose a good move at any time, regardless of the current layout of the board.
To be able to write a function for choosing the best move there were a few basic functions I needed first. I needed to be able to find all the moves currently possible for a given piece, to be able to find the distance(number of spaces) between any two locations on the board and to have some way of telling the computer what its goal is. Once I had all that, I was ready to begin.
The first idea I had was to pick the move which went farthest from it's starting location in the direction of the goal. If there is more than one play which moves equally far then it will just pick the first one it comes across. This strategy does eventually get all the pieces
across
the board, but there are three big problems. If there were no human player to keep the layout of the board different from game to game, then the computer would always make the exact same moves. And worse, the computer never actually finishes the game because once its pieces get near the goal it is incapable of determining how to move them into the goal and winds up stepping a single piece side to side forever. The third problem is that the computer tends to leave pieces sitting in its starting area for a very long time.
To encourage the computer to move pieces out of its starting area I give more weight to pieces based on how far they currently are from the goal. If two pieces can both move three spaces closer to the goal then the computer will pick the one which is currently farther from the goal. This helps the computer keeps its pieces closer together on the board(which is good for setting up jumps) and makes it less likely for the computer to block you out of your goal by leaving its own pieces in the way.
The next big change I made was to address the issue of the same moves being chosen in the same order every game. Instead of picking the first "best" move it finds, I made the computer compile a list of all the "best" moves and then pick one at random. At this point I also changed it so that the current distance a piece is from the goal is not considered in whether or not it makes it to the list of "best" moves. Instead the moves which originate farther from the goal are made more likely to be chosen from the list. The result of these changes was a computer player that feels much more alive and is also a more
challenging
opponent because the randomness of its moves actually makes it more likely that the computer has a really good move down the line. There were still two major problems at this point though. For one, the computer continued to have trouble getting its pieces into the goal. The other problem was that it still had a
tendency
to leave some of its pieces in their starting locations for a very long time. At this point I discovered something interesting (though perhaps not terribly surprising). When playing 1 on 1, I will easily beat the computer every time, but if I play a game with 5 computer opponents and myself then I often come in 2nd or 3rd place. There are two major reasons for this. Firstly, with 6 players crowding the board I do not always have any good moves to make and sometimes my pieces wind up stuck near my starting location for a long time. Secondly, no matter how good I am at seeing moves, the computer is perfect and can easily find some amazing moves in the mess that becomes the center of the board.
In an attempt to alleviate the problem of the computer leaving pieces behind, I came up with the concept of "disuse weight." Each turn on which a piece is not chosen to be moved it gets some weight added to it. When deciding which moves are the "best" the disuse weight of the piece being moved is taken into account. In this way the computer is forced to move all of its pieces periodically even if it wouldn't normally consider that piece a strong candidate for play.
The above takes us to where I am with the program today. The next thing I want to do will hopefully make the AI much stronger and also fix the problem with moving the pieces into the goal in an efficient manner. I intend to give the computer the ability to look a few turns into the future to see what a move this turn will allow it to do next turn and the turn after. This was one of the first ideas I came up with but I have been avoiding it because the programming will have to get much more complicated than what I have been doing so far and because I foresaw myself dealing with a chess problem where tons and tons of CPU time is spent looking into the future to determine a good move. There are a couple of things which made me decide that this is the right time to give the AI the ability to consider future moves. One thing was that I decided that looking more than 2 or 3 turns ahead will be nearly useless because the board will have changed significantly by then. If I am only looking a few turns ahead then it is also reasonable to ignore the other player's moves and pretend that only the current player is moving. These two things combined will cut down immensely on the amount of calculation that has to be done. I also decided that this may be the easiest way to solve the problem the AI has with efficiently getting its pieces into the goal.
This is the point where my Christmas vacation ended and I had to go back to my job and to focus on finishing my grad school applications. I intend to get back to work on this program as soon as I'm done applying.
-== UPDATE ==-
Feb. 14th, 2008
I began working on Chinese Checkers again mid way through January with the idea in my head that I would get my new AI function working within a few days. The problem turned out to be much more difficult to wrap my head around than I anticipated and it was a full two weeks before I go the code up and running. Despite the extended time it took me to complete the task, I have to give myself a pat on the back for a moment here. The very first time I played against the new AI routine the computer beat me by a good seven moves and two weeks later it still beats me more often than not. There is something very satisfying about creating a program that can out-think you in a game. Conceptually the AI routine is fairly simple to understand so I will attempt to explain it here. For each of the ten pieces the program calculates every position that piece can move to this turn. Then, one by one, it pretends that it did in fact move to each position and repeats the process from the beginning. For each turn ahead the computer looks it determines which of the possible moves is the "best" based on nothing more than how much closer to the goal the piece is after moving. The further into the future you are looking the less valuable the moves are considered. The value of the "best" move is then added onto the move prior to it (counting by turns). In this manner the computer can "look ahead" as many turns as you like but the time taken to calculate all the possibilities increases at an alarming rate and by the time you are looking 3 turns into the future the pause is a rather annoying interruption of game play. Fortunately I had already decided that 2 turns into the future is probably enough and I was right.
In addition to the new AI I also made a bunch of other changes to the program. Most notable are the following: When you click on one of your pieces the game can show you the paths from that piece to all the locations it can move to this turn. The paths can be displayed either as solid gray arcs or translucent gray arcs. The game will animate piece movement by hopping the piece from location to location along the path to its destination. This animation can be sped up and slowed down or turned off completely as you desire. You now have the ability to undo/redo moves. There is a settings window which normally sits off the right side of the screen but when you move the mouse to the edge of the screen the window slides over to give you access to its options.
Translucent paths to each location the selected piece can move.
Solid paths with red piece moving along one of them.
Settings window.
At this point I have completed everything I set out to do with Chinese Checkers except for adding network play to the game. I intend to begin working on that this weekend and the next update will be when the network code is complete.
-== UPDATE ==-
June 25th, 2008
I have finally gotten the network code to where I believe it is playable without crashing too often. There have also been tons of changes made to the code and some features added to the program. Only the most important will be addressed here.
In the above picture there are four highlighted and numbered areas:
1) Clicking anywhere in this area will make the little hand point to a different player. Whichever player is being pointed at is the player who will go first once the game begins.
2) Clicking on any of the colored circles in this area will allow you to adjust the color of a players pieces. The panel which is highlighted as number 3 in the above picture will appear.
3) This panel allows you to adjust the color of piece on the board. From top to bottom, the 3 numbers are the red, green and blue values of the color. Adjust the 3 sliders to pick any color you like. When you are done you can either click the Done button or just leave the panel open. Once you start the game the panel will disappear anyway.
4) This is the Network tab of the Settings menu. Only the upper portion of the Network tab is important. "Name" is whatever name you want the other players to see you as. "Game Name" is required if you are the one hosting the game, otherwise ignore it. This is what would be displayed in the blue area in the lower half of this menu if that area were to display anything. "IP" is only required if you are NOT the one hosting the game. "Port" is required both for hosting and joining and should probably be left alone. Clicking the Host button will start a network game with your computer as the host. Clicking the Join button (the one directly under the Host button) will attempt to join a game at the specified IP and Port. Ignore the Password field as it will not do anything at this point. Ignore everything in the lower half of the menu as it is only relevant in the off chance that I happen to have the master server running on my computer... which I never do.
And that is that. The other changes to the game are either purely aesthetic or invisible to the user. There are a couple of different things in the network code that can cause crashes, but I felt that the program was stable enough to release an update. There are also one or two less important things which I will continue to work on. One unimportant bug deals with the routes the pieces choose to take when you move them. The pieces do move along valid paths, just not always the shortest path.