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.               

The Future of RPG's

             As any of the avid game players may have noticed, the art behind RPG’s is dying.  They are all about lots of quick rewards.  Literally, click this, then click that and repeat 100 times.  It’s only addiction is the constant state of achievement, and the fact you always feel the next is so attainable. 

In a previous post, I discussed possibilities of how “Fun” can be defined in video games.  While RPG’s depend on the feeling of rewards, I would ask that more RPG developers and designers start putting that as #2 or #3 on their list of things to cover.  What the future holds in RPG’s is something that todays world is far more equipped to deal with.  Players that can leave lasting effects on the games.   In RuneScape, You mine ore from a rock, until the rock disappears.  A minute later, the rock reappears.  What if it didn’t.  What if mining for ore literally expanded the map?  What if your character could walk around somewhere, and randomly start mining.  Find gold, and start a settlement.  What if your military people could control X number of NPC military  soldiers and take over villages, or clear out forests?

In games, the What If’s can be a painful thing to live with, as there are so many.  Seriously take a look at this though.  What if you could damage things like buildings and bridges.  What if there was a finite amount of gold in the world.  What if the monsters learned?  In a later post, I’ll be discussing how to build a dynamic hard coded (interesting phrase no?) spell casting system can be linked with an effective AI that builds your world, enhances your monsters all without human interaction.

So the idea of mining literally modifying the map.  First off, you need a living map, or supporting a constant state of change.  Second, your map must be true 3D, not just a height map based on a black and white image.  These are tough tasks, that do exist in the world, and will require some heavy proofs.  Build your bridges, your houses, your mines and your mountains from stretching a single piece of ground and reshaping it.  Then it will only take one modification system to handle manipulating it.  Houses are simply predefined modifications.  Mines can actually grow.  You can knock someone’s house down.  Naturally, you can give materials different strengths, indicating its more difficult to damage or work with.

                Then you can create a real bounty system, and have NPC’s and PC’s hunting players who damage certain property, like the entrance to the goblin cave, or a bridge out of town, or someones house.  This is one of those systems that once it’s built, it becomes putty in the hands of the rest of your programs, AI’s and players.  Build real societies.  But make an evolution.  Don’t just write another click this, click that application.  Be the next wave.

Proof of Concept

     In my years of experience, one of the biggest problems I've found is a disconnect between management and programmers.  One that says that both sides really know what their doing.  As soon as a programmer says a timeline looks good, they are telling management that they decisively know everything that needs to be done, how it will all work together, but in truth they do not.  Most don't.

     Most all programmers don't realize they deceive management, but its true.  I'm guilty of it, everyone I know at various companies, including Microsoft does it.  The problem is that we think we've built something like this before, so we know what needs to be done.  While our past experience does give us clues to how things will pan out, when is the last time that a request came down from management to "rebuild" something EXACTLY like what you have done.  The point there, is that all these projects may be like something that previously existed, but they always have some new, often strange, way of doing things.  Some new feature, or method of control.

     The problem that we face, and often blame feature creep entirely for, is once we start building something, we come to a cross roads; either we go back and rebuild part of it to work with some odd portion of the project, or we need to hack a small portion of the project to make it fit into the whole.  The reason this happened, is because we are facing something we were not prepared for.  Despite the fact we had an idea of how it could work, once we are here developing it, it almost always deviates from that original plan, some of it being made up as we go.  If we really had our head wrapped around everything it would take when we submitted a timeline, we wouldn't be surprised by this;  our original architecture would work fine for all this.

     So how can we fix this?  With Proof of Concept!  Why yes, its the magical solution that solves every problem!  ;)  Or not.   Proof of Concepts are the key here, but I want to emphasize that no amount of experience can fully prepare you for the future.  Respect that, remember it and apply it.

     To really understand what is involved in the project, start stepping through the requirements, and existing design.  Create a list starting with the most basic abilities to be used.  Even if you've already know them really well.  Then start adding on the layers.  "Show a text box" > "Limit the amount of character" > "validate they are in a phone number format" > "Check if the number exists in the database" > "geocode the region for the number" etc...  And as you start to look at this list, find anything in it that you have not built before, and go build it.  For instance, Validating a phone number format, when you start considering that, you have to ask yourself what formats are acceptable.  Well, there are many, and other countries.  So, the requirements either need to list what type of phone number's are acceptable, or you need to accept all of them.  That's immediate feed back on the requirements, and if you waited until you hit that point to start asking these questions, you may already have database options limiting against what you need, and other parts of the project that already work with one style of phone numbers.  You wouldn't know this until you actually address it.  and by then, having to go back and change everything leaves a lot more openings for errors to occur.

     So, always outline a list of what approaches you need to use in the project, including how things interact.  This will also help for feature creep.  When someone says, "now I want you to add this", you can break it down, and see if you have any proofs existing to cover it all.  Chances are, that you do not.  And chances are, it might require changes to the architecture or hacks to make it fit.  This makes the things you do much more clear.

    

     Argument, "Management would never let us spend that much time defining something out".  You are possibly correct, but that is only because of the first sentence about the disconnect between management and programmers, followed by the idea that they don't know what they are doing.  (given the paragraphs that followed it would be easy to assume I was leaving management blameless. :) )

     By demonstrating to management that using proofs will make timelines far more accurate before the project even begins, is a huge value.  How many projects have you been on where everything was on time, and under budget?  While a few might get through like that, in general, that is not how it works.  Things get pushed out with bugs, pushed out late, or dropped altogether.  Often a combination of all three.

     Yes, this will take more time up front.  but, as time goes on, and this practice is adhered to, everyone will start gathering more proofs, more practice, and the proof of concept stage will get smaller and smaller.  (depending on what is being requested)  Eventually, the companies become very streamlined, and the proofs help shape exactly what areas the company has real experience in.

     Also, a proof can be used as a reference to say, "it can work like this", or "here is another option to try for it"  Also, proofs help shape additional questions, like "What phone number formats?" and "What security levels?"

     Again, I don't expect every company to just jump up and start acting on this. but do take a serious look.  Watch when projects fail.  Watch when those cross roads reach you.  Once you start keeping track of it, it becomes more clear, and you'll see why this practice, or something similar is absolutely necessary in the real world.

Selecting a College

    Today, I'm focusing on how to select a school.  While I'll focus on Technology, this really applies to many topics.  When I find a school that has the class coverage I want, I then seek information on the key instructors.

     I want two things in my instructors, that they do practice what they preach, and that they view what they do as a form of art.  Technology and art forms are not usually synonymous, but I'll get to that.

     First, I want to talk about practicing what you preach.  I don't want a teacher that studies and does a few practices on their own, but isn't expected to complete practical work.  There are a hundred ideal ways to build an application, but many of them are not practical with modern management.  Projects start with great aims, but change significantly and often.  Not many isolated teachers recognize that in clear enough terms to prepare their students for it.

     An easy example of the difference between knowing the path, and walking it, is to look at learning a new language.  There are not many teachers or books you can learn from that once you've mastered their courses, you can travel to the country of origin and speak the language, without people knowing that this is a 2nd language for you.  It stands out.  This is the same with programming.  You step out of college, get your first job, and suffice it to say, there are plenty of things you still needed to learn, like we don't actually do that here, or that's not really practical given the time constraints, or don't tell management you can do this in 3 weeks when you haven't actually built one before.  

     An instructor who has to work in a practical environment is something I would target.  This is usually easy to figure out, as most instructors will usually have a page describing them selves, and what they do.  If they have a job or run a company, aside from teaching, they'll probably list it.

     The 2nd target I seek, is an instructor who really sees the art of what they do.  This is a little harder to learn about the teacher, but it is really valuable to have.  Some one who doesn't understand art, sees what a picture looks like.  But an artist can read between the lines.  They can see the feeling that was intended when it was written.  This is not limited to the commonly accepted artistic fields.

     This is really about reading between the lines.  What does something mean that it does not clearly say?  Someone might look at the Mona Lisa, and see a painting of a woman, while others who look deeper, will read subtle expressions of thought that show up through it, along with many other things.

     This translates to programming as well, because the code is similar to art.  If you look at it, it tells you what the developer told the computer to do, but if you read between the lines, you'll see why.  Many developers don't use much in the way of style guides, and pretty much live off of the commonly out-dated Hungarian notation.

     The problem with this lies in the fact that when you don't commit to a stronger style guide, the styles that do show up change from line to line, sometimes even multiple times in the same line.

     In the real world, when some one programs like this, and another developer is brought in to take over, or restart the project, they often feel it would be a better idea to rebuild the entire program from scratch.  It doesn't flow well, definitions aren't clear and you usually have to dig through layers of code to figure out what part of it does.

     Someone who has experienced this, experienced it and grown from it, will be able to pass that on in classes, otherwise they are dooming all of their students to suffer the same fate, and pass the same problems through the work place.  

     If possible, find some source code, (often examples made by the teacher, or pet projects they have public on the Internet) and ask a friend who has experience to read through it, and tell you what they think of the code.  A more inexperienced friend might call the code overly formatted, but typically it will be easy to read, understand, and express itself clearly.  

     For those of you involved in programming, who commonly find yourself wanting to rebuild your own projects after only a short while, because you've learned a new trick, or want to re-organize it, I suggest you look up Microsoft's API Design Guideline.  There's a digest floating around that sums it up quite nicely.