Starting out with AI

                I remember how AI appeared before I had the opportunity to really learn ways to make it work, or even, what qualified as AI.   It was scary.  It was one of those impressive things that you have to be a genius to build.  Of course most things either seem too easy, or too complicated if we don’t know how they work.  This article is a little introduction to AI, and how to apply it in games and applications.

                The most basic purpose of most AI’s is to turn everything into a number.  Place a value on it.  Then the AI simply chooses the highest or lowest number.  The trick is deciding how valuable things are.  Let s pick tick tac toe for a starter.  AI in tic tac toe is pretty simple.  For 1, you could literally record all the possible moves, and give your AI the solution it needs to always win or tie, but never lose.  But that’s no fun, and every move is pre-programmed.

                To turn it into a metric, look at the paths needed to win.  First move, When you place your X, where will you place it.  I recommend taking a look at each space on the board, and counting out how many possible wins you can have from it.  For instance, placing one in the middle gives you 4  combinations to win.  And reduces any move your opponent could make down to 2 possible wins.  The next opponent AI has only corners and sides to play on.  By reviewing the side pieces, they realize that it would give them only 1 chance to win with it, and only reduce the opponents possibilities 3.  The corner allows for the AI to have 2 possible directions to win, while the opponent also gets reduced to 2. 

                That was a simple suggestion.  Comparing the number of possible wins a move will give you vs. your opponent.  In more complicated games this gets tougher to define.  Moving on to Chess for instance, where there are many possible moves, and many of them are very different.  In the first ten moves alone, the total number of possible moves = 169,518,829,100,544,000,000,000,000,000.  So, unlike tick tack to you really can’t just record all the possible variations. 

                So how do AI’s do it?  It’s not reasonable for a computer to step through that many moves, and that’s only ten.  And there are times where humans can identify a checkmate in 10+ moves in advance.  So how on earth is that possible?  It’s is more achievable when you place values on moves you make.  For instance.  Your opening move can have 20 possible moves.  (each of the 8 pawns can move 1 or 2 spaces, and both of your knights can go forward to the right or left.)  Each move can be measured for different things, like are there any openings to attack your king?  Is your king directly exposed?  Are any of your pieces in immediate threat?  Are any of your pieces able to attack?  Is your queen in jeapordy?  Are any of your threatened pieces leaving an opportunity to check the king if attacked?  Essentially, you write small scripts or methods that check these values, and assign threat and reward levels.  For instance, you putting their king in check is a good reward level.  Your king being in check is a stronger threat level .  For instance, lets say that if your king has an opening to direct attack, (not in check, just an opening) it adds 100 to the threat level.  If your queen is in check it adds 300 to your threat level.  If your pawn can remove an opponent’s power piece, reward level is up by 250. 

                Once you have all your comparisons done, subtract the threat from the reward level and you get your final score.  The AI will test each possible move it can immediately make and identify which of those moves have the most reward.  Then it compares the next rounds.  For the top 3 most valuable moves, and one random one and tries to test each follow up possibility.  Adding each move to a list.  Then the list is checked again for which 3 have the best score, and check again with another random one.  A chess game may easily step through 100,000 moves before it’s settles on the best possible one found after that many considerations. 

                To add difficulty levels, each move has a random value added to it.  For easy, that value could be a random from 1000 to -1000, where sometimes it would make really smart moves, but mixes it with other moves that really aren’t so great.   A middle ground AI might waiver by 250 points for the end number. 

Movement AI’s

                Movement is another great AI.  Making a path from point A to point B when there are lots of random obsticles in the way.  The most common starter AI is called A* (A Star).  Essentially, it takes every possible move you can make, (upwards of 8 at the beginning) and say which is the closest.  Then adds that to its path, and adds every surrounding possible move, and how close those are to the goal.  Then from the total list of possible moves it grabs the next closest one, until it finally gets to point B.  Then, it uses only the list for the path, and uses the same AI to make its return path.    Every step is taken by using numbers, and comparing for the lowest possible value. 

                I will mention that I only touched on some perspective ideas for how chess AI works, and there are some other problems with A* that have simple solutions regarding time.  But that’s another can of worms.  I primarily wanted to give you a simple perspective into the world of AI, and the hopefully give you the theoretical knowledge to get started with it.