AI Project: Checkers

To kick this Project site off I figure I’d start revisiting some work I did a couple quarters ago at UCI in an AI project course.  We set out to experiment with some different Checker strategies and see how they would fair against each other, against us, and (most importantly) against another team developing another Checkers AI system.  It was an interesting project to say the least.  I’ve created a simple game from my own ideas, but I haven’t created a game from a preexisting set of rules before or have the game play against the human.  The game system is pretty self explanatory; moves are hi-lighted, jumps are mandatory, a piece becomes a king on the other end of the board, and you win when you lose all your pieces or when you can’t make a move.  I really wanted to build this in something other than a Java applet, since they aren’t used much these days, but it was the closest and easiest tool to use for what I needed.  The AI depth search uses a min/max and alpha/beta pruning strategy to allow the massive move set to be shortened so a move decision can be made in reasonable time, but a search of depth 10 still makes a noticeable pause.

The most interesting part of this project is the AI strategies we implemented.

  • Random
    • The AI selects a move at random.  Hardly a challenge
  • Basic
    • The AI examines all possible moves within the search depth value.  It then selects the move that allows the AI to be in the position were losses and gains will be the most beneficial.  Ideally, the more pieces it can take and least amount of pieces it can lose will increase the probability to win the entire game.  This strategy is easily countered by tricking the AI with bait, and then trapping and taking its piece.  The best choice is based on an average score derived from a couple of heuristics.
      • Taking pieces(+ for regular; ++ for kings)
      • Loosing computer pieces(- for regular; — for kings)
      • Getting ‘Kinged'(+)
      • Moving a piece from a ‘King Me’ square(–)
  • Piece Table
    • In addition to the the heuristics above for the basic strategy, a piece table is also incorporated into the score for a move.  The piece table gives each square a value and it is added into the the average score for each move.  This is the piece table used for the Checkers game.  Each number denotes a square worth value.  The higher the value, the higher the worth of keeping a piece on that square.  Notice that all ‘King Me’ squares hold the highest value of 4, these spots are very important and a player would only want to move a piece from this location as a last resort.  Squares close to the sides of the board also have the value 4, and closer inside is 3, are the least vulnerable from attacks.  On the other hand, the squares in the very middle of the board hold a value of 1.  These squares get vacated as fast as possible since they are most susceptible from attacks.  The numbers make a sort of spiral from the outside, decreasing in value as they come closer to the middle.  This strategy is very strong since it combines the heuristics from the Basic strategy to minimize losses and maximize gains as well as achieve optimal piece placement on the board to further minimize more losses and maximize more gains.  I have not been able to beat this strategy.

Overall it was a very enlightening project to work on.  I learned a lot working with massive decision trees, different strategies, implementing given rules, and classifying data sets using a range of scores.  I was quite happy with the outcome of an AI that can easily beat its creator, and with the fact that we smoked the other Checkers project team.  Try your luck playing against it in the Code/Src tab.

I have a couple of planned changes for this application’s future:

  • Simplify the button options
    • The three buttons on the GUI made sense at the time I created them, but many users have reported that they have trouble knowing which one to click when.  Combining the Resign and New Game button into a single one will free space for an AI vs AI option.  Another problem is that when the Make AI Move button is pressed the player switches sides.  They have to click it again to resume play as the original red color.
  • Allow  the player to select his color at start of game
    • Just a nice option for the player to choose.

Why should I be charged for online gaming?

There are currently a few payment models used for online gaming.

  • Totally Free
    • This is always the more preferred model from a customer’s point of view.  I mean hey, its free!  After buying a game, any online functionality is free of charge.  You can play, chat, friend request to your heart’s desire.
    • The most recognizable company that usually always uses this model is Valve and their multiplayer games(Left4Dead, Counterstrike, Team Fortress 2).  Valve has a key difference here when facilitating online play for its games, the servers are for the most part owned by the users.  When a user wants to play a game he can either join a server already hosting one or create his own.  This functionality drops Valve’s cost to host all the multiplayer games almost down to $0.  Valve doesn’t have to keep up the maintenance to ensure no lag or keep all the servers patched up, the users do.  Valve merely hands them the tools along with the game and says, “Go have fun!”  I think this is genius.  Not only does it keep the product’s cost down, it makes the users happy because they don’t have to pay to play, AND gives the users the tools to create and modify the game’s mechanics on their own servers.  If you want to have zero gravity when fighting zombies, you can do that.  If you only want your friends to play on your server, you can do that.  As long as the users want to play this game online, they will find ways to do it because they have to.  Meanwhile Valve can focus time and energy on making new games.  Starcraft also uses this model, one of the most popular games of all time.  I think it is important to mention that the fact that these games are targeted for the Computer platform instead of a console is important here.  You can’t host your own console game server as easily, but maybe that problem should be looked into…
  • Pay to Play
    • Conversely, this is the model that a big majority of online gamers hate.  “Why should we be charged continuously for a game we just bought?” they ask.  World of Warcraft is an excellent example of this model, racking in millions of dollars every month from its monthly subscription costs alone.  Most MMORPGs use this model because of the HUGE upkeep it takes for the environment to always be online so all the users can play together.
    • The biggest company that uses this model is Microsoft with Xbox Live.  Now, technically someone can argue that XBL falls in the next category, but since you can’t really play games online with XBL Silver(Microsoft’s free service) I am just going to talk about XBL Gold as the standard here.  XBL costs about $60 for 12 months of service($5 per month).  The features included are online multiplayer gaming(guests playing on your Xbox with you can also play), free and exclusive betas/game demos/premium downloadable content/Microsoft Game Store items, Netflix integration(if you have netflix streaming), friend list, movie rental service, and they also just added free ESPN3 through your Xbox.  Since Xbox is a console system the game servers can’t be hosted anywhere so Microsoft has to do some upkeep with their servers for most of these services; I don’t think Microsoft themselves hosts the multiplayer game servers since the actual companies who produce the games do that.
  • Pay for Premium Features
    • I see a lot of online systems use this model since it has the best of both words from the other two.  The consumer gets the free functionality to a point, but if they want some better features or items then they have to pay for a premium service.  This premium service may very well be the same functionality and price as the Pay to Play model.
    • Playstation Network uses this model.  The PSN is the free service; features include online game play(no guests allowed), access to the Playstation store, Netflix integration(if you have netflix streaming), friend list, and movie download service.  PSN+ offers these features plus some more for $50 for 12 months of service($4.17 per month); free/exclusive betas/game demos/premium downloadable content/PlayStation Store items, and a free subscription to Qore(online gaming magazine).

If quality games produced by Valve can make them free to play online then why aren’t all the other companies doing that?  “Well duh, they are greedy” you might say.  I’m not entirely convinced of that argument.  I won’t say that turning a profit doesn’t have anything to do with it, but I think that fact that console game servers are propriety(at least for now) means that we will have to pay to have other people(mainly the game companies) maintain them.  PSN isn’t some magic where the multiplayer servers don’t cost anything, Playstation probably covers that cost.  Playstation knew that Xbox already had a hold over the console multiplayer gaming with XBL so it decided to offer its service for free in order to appear as a better alternative.  Unfortunately, PSN still couldn’t offer everything for free that XBL could for a price and that is where PSN+ came into the picture.  A more concrete idea is that even for a cross platform popular game like Modern Warfare 2, the Xbox sales were almost double that of the PS3 sales.  This translates to bigger server upkeep, more cost, for the Xbox multiplayer servers.

So, why should I have to pay for an online gaming service?  Well, because gaming online takes work to upkeep the servers you play on and update the game if needed.  And that work costs money.  And if you aren’t going to do the work(or can’t), then you are going to have to pay someone else to do it for you.  Personally I don’t mind paying $5 a month for XBL.  Heck, I usually find 12 months for XBL on sale for $40 and buy one or two in advance(only $3.34 per month).  Yes I am glad that gaming on the PC is free, but I don’t see anything wrong or complain worthy with paying Microsoft to ensure I have a good online gaming experience to play Halo, Perfect Dark, or NBA Jam.