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.

A Review: Starcraft II Wings of Liberty

Twelve years. Twelve years I have waited to get my hands on a sequel to Starcraft. Let me tell you how big Starcraft II is, if you don’t understand.  The original Starcraft changed the way games were accepted. The original build of Starcraft shown at E3 had such bad reception, often called Orcs in Space for the similarity it had to Warcraft, that Blizzard said it would rebuild the engine and game in two months. That is insane. But they did it. And it worked. Starcraft shipped with an intense three campaign long story mode as well as an online competitive multiplayer mode. While single-player certainly was mind-blowing(ZOMG multiple points of view, twists, and cinematics!!), the real deal was/is the multiplay. Not only was it immediately a great success with friends, nothing like battling in space for Koprulu sector dominance, it bred a whole new type of competitive video game. The title “Professional Video Game Player” became more common and tournaments were held for thousands of dollars with thousands of spectators watching whose strategy would stick through it all. That is how big Starcraft is, still played competitively today.

Starcraft II was always a hope/dream of all the players, but it wasn’t officially announced until 2007.  People got way excited and the South Koreans went crazy.  The sequel to one of the best games of all time(undeniable fact) was coming to us.  We would finally find out what happened after the Zerg swarm finished off three HUGE fleets Terran+Protoss forces.  What changes have been made to our beloved fighting units?  What time has passed?  How are our characters doing since we last left them off?  Well, the game came, and it is awesome.  Oh is it awesome.  The multiplayer is great.  They found their strengths in the original and weeded out the weaknesses.  There are a bit of people clinging to the original Starcraft for their competitive game scene, but I think they are just afraid of change.  Yes, Starcraft II gameplay is different.  But it isn’t bad.  I love the new engine, the new abilities, how the game is a bit more ‘forgiving’ with your actions, and it just looks so nice.  Nothing is nicer seeing my Hydralisks shoot spines at Cory’s charging Zealots, psi-blades fully extended, just waiting to start breaking out their scythe like claws.  Who wins that battle?  Who cares, it looks freaking beautiful.  It plays smoother as well.  No more sense of jerky unit movement or stale scenery.  The game is great.  The game lives up to the hype it caused.  There are large parts that are disappointing to me though.

My gripes on the game are mostly on core design decisions for the game that take away more than they add I believe.  I really wish they would be changed, but I doubt they will be.  Now, i’m not talking balance changes for different army units, those are coming later this month actually, but bigger changes that would take a re-release of the game probably.

My Gripes…

  • Split Game Campaign
    • Now, the first Starcraft had three campaigns included in it, one for each race.  Starcraft II originally had that planned but they scrapped that idea to make each campaign longer but split up across three separate games.  So Wings of Liberty is the Terran campaign, Heart of the Swarm as the Zerg campaign will come out later, and Legacy of the Void being the Protoss campaign will be released even later to complete the storyline for Starcraft II.  This enables them to get each campaign out one at a time giving us an episodic game rather than waiting longer for the entire thing, or so they say…  Now, this isn’t a huge deal in itself in my opinion.  But paired with these other gripes of mine, it becomes a much bigger problem.
  • Tutorialish Singleplayer
    • We cried foul over the release of separate games at first because we’d be paying for less singleplayer, but Blizzard assured us that Starcraft II Wings of Liberty would have a Terran campaign that spanned just as long as all three campaigns in the original Starcraft.  Ooooh, now this was sweet music to our ears.  A longer and more in depth Terran campaign means more story, more character development, more twists, and more cinematics!  And the same will go for the Zerg and Protoss campaigns coming to us later!  Well, this longer Terran campaign wasn’t all it was cracked up to be…Let me explain.  One thing I wasn’t expecting is that singleplayer has A LOT MORE units than multiplayer.  They kept a lot of the old units from Starcraft in singleplayer.  That is cool I think.  Firebats, wraiths, medics, and even vultures get to make an appearance.  Then there are new units that aren’t in multiplayer that show up singleplayer, predators, diamondbacks, automated refineries, and even ghostesque spectres.  So, a plethora of units in singleplayer is GOOD.  It makes singleplayer that more exciting since you can make even MORE strategies and combos.  But here is where that bonus ends.  A majority of the campaign’s levels are ‘tutorial levels’.  Tutorial levels are specially designed for the player to produce and learn how to use one specific unit.  That one specific unit will be the most effective way of beating that level, so you are a little bit forced to beat that level by building that unit and using strategies with that unit.  It makes the player feel a little tied down.  The player can’t decide what strategy they want to use since they almost HAVE to use the tutorial unit.  Tutorial levels aren’t bad, they are actually a little bit helpful, but when you boast about a campaign being just as long as the original game’s entire set of campaigns, the majority shouldn’t be tutorial levels(in any game’s campaign).  Since the majority is tutorial levels, it makes the entire storyline feel like a giant tutorial.  I was waiting for the tutorial release when I was free to use whatever units/strategies I wanted to and act like a real army commander.  But that feeling came much too late in the game, around 4 or 5 levels left, when it should come quite early or even in the middle at the latest.
  • The Total Cost vs Don’t Mess With My Multiplayer!
    • Starcraft II: Wings of Liberty is a full priced game.  A full single-player, even if too tutorialish, and a solid multiplayer, which is arguably the reason to buy Starcraft, is worth a full price.  Some games don’t even have a multiplayer and charge a full price, so Starcraft II, one of the BEST games of this year, is definitely worth $60.  Now, the next two games…will they be worth full price and do I we want them to be?  For them to be full price they each will have their own single-player, hopefully a little less tutorialish, AND their own multiplayer.  Their own multiplayer.  I don’t want them to have their own multiplayer.  I don’t want ANOTHER multiplayer when we are still playing and Blizzard is still balancing this one.  I’d much rather pay less for the next couple games and just receive a single-player addition, or even pay full price to keep this multiplayer the sole Starcraft II multiplayer.  I was never a big fan of the two multiplayers in the original Starcraft along with Broodwar.  Everyone just played the BW multiplayer almost and the old one got left in the dust.  I don’t want to keep paying for a new multiplayer and switch to different units and play styles when each game comes out.  But, we will see what the price scheme is for the next two games.  Blizzard says they won’t over charge us, so that makes me think it will actually be lower.  Still not to crazy about the different multiplayers though…

None of those gripes on their own is anything major, but I think they affect each other too much and it adds to a bigger problem when all are present.  Now we are having to deal with, and purchase, three different games each with their own multiplayer, that will split players, and, by the looks of it, each have a really tutorialish single-player campaign.  Starcraft II is a great game, but this problem just wasn’t a good design in my opinion.  It isn’t a deterrent from buying any Starcraft II game but it does cause some disappointment afterwards, and that is almost just as bad.

Video Games

“But games do matter, because they spark the imaginations of our children, taking them on epic quests to strange new worlds. Games matter because our children no longer have access to real-world play spaces at a time when we’ve paved over the vacant lots to make room for more condos and the streets make parents nervous. If children are going to have opportunities for exploratory play, play that encourages cognitive development and fosters problem-solving skills, they will do so in the virtual environments of games. Multi-player games create opportunities for leadership, competition, teamwork and collaboration—for nerdy kids, not just for high-school football players. Games matter because they form the digital equivalent of the Head Start program, getting kids excited about what computers can do. ”
-Henry Jenkins