UNH CS 730: Intro to AI

Conformant Planning

2012-02-08T07:59:00.002-05:00

I'm still not quite sure what I'm going to do for my final project,but one thing that's been on my mind ever since it was mentioned inclass is the idea of an agent that has no external stimuli from itsenvironment. An example was mentioned of a Mars rover possibly losingaccess to some of its sensors, and needing to take the best course ofaction in such a situation. After my blog post last week mentioningthis topic, Professor Ruml informed me that this type of situation isknown as conformant planning.

From what I've gleaned from a few internet searches and brieflylooking through various sections in the book, conformant planning isbasically the idea of coming up with a plan to reach a goal statecompletely independent of the staring conditions (world/state). Itappears that one way to tackle these types of problems is to dealwith them as search problems in a “belief space.” A belief spaceis simply a space of possible worlds. How to go about actuallygenerating and considering certain worlds over others is stillunclear to me, so I'm going to do a lot more research on this beforenext week's blog post. Hopefully I'll know enough by then to knowwhether I would want to do this as a final project. As of now I'm notsure how realistic a task it would be for me to hope to actually codeanything that implemented conformant planning in any type ofreal-world scenario, but perhaps for the final project I couldimplement some simpler examples of it. I'll check back next week.

Reflection of Implementation of MS-1

2012-02-08T07:29:00.005-05:00

On Sunday, the first milestone was due. I have decided to write a reflection of my code, as I spent a great deal of time writing and am still very unsatisfied with what I turned in. It was not for lack of effort, I sunk approximately 20 hours of work into a product that I was ultimately unsatisfied with.

Throughout my degree, most of the programming focus has involved object-oriented languages. Stress has been put on creating a good design, and efficiency has always been shoved off as a second thought. Thus, while abstracting classes for this first program, I went way overboard. I chose to implement a “VacuumWorld” class, which was composed of a “Space” array, which contained a “State” and a “Command”. I have quickly realized that this was not a very smart idea, as copying such huge objects during node expansion definitely decreased the efficiency of my program. In order to copy the “Space” array, I was required to copy each object element within the array. Also, each getState() call I performed was causing unnecessary overhead, as calling functions is NOT free. Thus, the milestone often spent some time spinning before producing a result, even on small input worlds. Simply put, node generation and program bloat were killing the efficiency of my program. I would love to see how Java HotSpot ranked my “getCopy” function in vacuum-world, as it was definitely an over-used section of code.

Overall, I believe I have learned that the old engineering saying, “keep it simple stupid”, or K.I.S.S., applies to keeping program bloat down, and is particularly important for Artificial Intelligence programs. However, this lesson comes at a great cost, and I have since started rewriting my program entirely. This time around, I am using BitSets to store the world, as they are small, easy to copy, and relatively cheap by comparison to my original idea of abstracting everything I could. I spent too much time trying to implement clever object oriented programming patterns in my code, when in reality the world could be represented using a much smaller data structure.

I have also learned the lesson that, while evaluating a program for efficiency, to try to think earlier on how to maximize throughput, as to avoid having to rewrite a bunch of code. I was not naïve while starting the program; I knew there was certainly a time and space element attributed to the problem. However, I did not put enough weight on designing an efficient program, and just jumped into my comfortable object-oriented lifestyle. Good news though; the new version of my code is running much faster; so at least I learned some lessons that have led to real improvements; and have decided to spend more time on my design with more emphasis placed on efficiency. I believe Java can be used efficiently for this problem, but I also have learned the hard way how inefficiently it can be used.

Final Project Idea

2012-02-07T22:58:00.002-05:00

So I know a lot of people have beenpicking games for their final projects, and I have decided I mightnot mind being unoriginal. I have been working on a project alreadywith my buddy from Oregon. We have been developing Bombermanin javascript. The idea is that you will be able to play bomberman inyour browser against other players who connect to some servers wewill have also written the code for. This multiplayer aspect is whatshould make the game interesting to people. That and it will be freeto play.

I wasthinking, however, since multiplayer is a large part of this game,could we add bots to the game? Being able to add AI characters to thegame could add a lot to the playability of the game, but it will alsomean a lot of coding for us. It might also mean we could test ourgame a bit easier, but I don't doubt that adding “good” AI to thegame will be a large project. I am just unsure as to whether or not Icould implement “decent” AI without needing to do an unreasonableamount of work.

TheAI characters would need a lot of spacial awareness. They would needto know about the surrounding walls, where the player was, where theother AI characters are, and where the bombs were. They would need toknow the best places to place or kick bombs without killingthemselves. They would then need to combine these multiple levels ofawareness into a useful form of intelligence, meaning that they wouldnot place bombs and trap themselves in corners, or get stuck on abomb while walking towards a player in an attempt to attack him. Iremember playing against the “computer players” on Bomberman64and they were merciless. If I could, I would want them to be able tocounter player bombs as well as try to trap and kill the otherplayers. It was almost as if the AI in Bomberman64 could sense whenyou were most vulnerable, and they would strike at you then. It wouldbe amazing if I could get anywhere close to the AI in that game, butI'm not that hopeful. I just hope that some of the algorithms andprogramming tricks and methods we learn in class might help me tocreate a more intelligent computer player.

Again,I don't know if the scope of this project is doable, but I havehonestly considered it and now it's sitting on the top of my pile ofpotential ideas.

Genetic Algorithm Final Project Idea

2012-02-07T22:34:00.000-05:00

In thinking about what I want to do formy final project I've been kind of stuck. Then recently I thought toperhaps try and combine it or draw inspiration for it from myinterest in computational mathematics. We talked briefly aboutgenetic algorithms in class and how there has been some success increating algortihms which create other algorithms by fitting piecestogether to end up with an algorithm which does somethinginparticular. I have also done a little reading on this in the past.This got me thinking about if it would be possible to try and write agenetic algorithm that could write an algorithm to solve some commonnumerical linear algebra problem.

Consider QR factorization, where an MxNmatrix A is factored into an orthognal MxM matrix Q (orthogonalmatrices are nice in that transpose(Q) = inverse(Q), transposes beingsimple to compute, inverses are not so) and an upper triangular MxNmatrix R with the properties that A=QR. QR factorization has severalapplications in computational mathematics including solving systemsof equations in the form of Ax=b (although this is less effectionthan simple LU decomposition) and solving least squares problems forinconsitent systems.

Everything is already completelydefined for us, we know exactly what the solution must look like, weknow and can readily define for a computer all of the actions that wemay perform on matrices. In addition to this we already have ahandful of algorithms for solving this including ModifiedGraham-Schmidt and Householder reflectors, so we know what analgorithm that does this might look like. Perhaps it would be aninteresting idea to even see if a genetic algorithm could beconstructed that could take the pieces we already know are used inthese algorithms in there very basic forms and then end up with thealgorithms we already know.

One difficulty I can think of right offthe bat is what “ideas” will the genetic algorithm have to knowabout (beyond just what operations it can perform) in order to find asolution. I think there are some obvious things it will need to knowhow to spot in order to be successful, specifically how to tell whenvectors are orthoginal and how to tell when matrices are orthogonal(obviously because it's needed to define the desired output of thealgorithm). However I don't know where the boundry is between givingit more “ideas” to work with and put together as pieces of thepuzzle, and just writing the algorithm itself that you want it toconstruct. There's also the problem of rounding error, which is onereason there's so many ways to do QR facorization, the need to morenumericaly stable methods. For example, how close to zero does the result of twovectors being multiplied together need to be in order for thealgorithm to accept that they're orthogonal?

I think this may be a way biggerproblem than I could complete for even a final project, but it'sstill something interesting to think about.

class scheduling

2012-02-07T21:31:00.003-05:00

on monday, we talked about problems involving searching a space of states to find one that doesn't violate certain restrictions. The methods of solving these problems could be applied to the problem of selecting courses in college. Students often find this problem to be nearing the limits of their abilities/patience, so a computer would be able to save a lot of time and prevent a lot of stress.

class selection is within the scope of this type of problem. the state space is the space of all possible class schedules for the rest of one's college career. it can't be limited to the current semester, because a certain selection of classes for one semester may not have any scheduling conflicts, but it might waste too much time with classes that aren't necessary, leaving too little time to satisfy other requirements for the major. restrictions include core major requirements, major electives, prerequisites, general education requirements (with special restrictions depending on your major), writing (and programming) intensive requirements, time scheduling (including labs, which have multiple possible time slots), etc.

in class, we talked about eliminating possible choices for certain variables when a choice is made that affects that variable. when that variable is completely wiped out, that means there are no valid solutions with the current choices. in the problem of class selection, the variables are the classes that are chosen. when a class is selected, certain possibilities for the other classes that can be selected are wiped out, for example classes that have the same lecture time.

class selection is not a straightforward example of this type of constraint satisfaction problem. all solutions are not equally good. among solutions, those with lower credit hours per semester, a higher degree of appeal to the student's interest, or more convenient schedules (to name a few) are preferred. this means that the program would have to (somehow) combine techniques for constraint satisfaction problems with techniques for determining optimality.

one way that this could be accomplished is to calculate a value representing a schedule's desirability whenever a valid schedule is found, and to keep a copy of the current most desirable schedule. the problem with this approach is that it requires searching the entire state space to find every possible valid solution. To prevent this, the program could calculate an upper bound on the desirability of each partial schedule, and only continue to expand schedules whose desirability is greater than a minimum acceptable desirability, which is a parameter that could be modified. The program can return without searching the whole space if a valid schedule is found that is desirable enough.

Constraint Satisfying Vacuum World

2012-02-07T20:23:00.004-05:00

At the end of Monday's class we were discussing Constraint Satisfaction Problems. Professor Ruml pointed out that depth first search is actually quite efficient for this sort of problem. This stems from each problem having a deterministic nature, and a finite number of states.

Consider the queens problem. You have n queens to place on a chessboard. Place one of the, you have n-1 remaining. The depth of the tree will only ever be n. That’s kinda cool, and really convenient. There is no need to do any complicated algorithm, and you don’t need a fancy heuristic. I am ignoring the complex code that comes with backtracking and finding the most constrained variable.

Alright. Now think about the current assignment. We have a map with dirt on it and a vacuum that needs to make the dirt go away. So looking at the problem I thought: “What if we have a clean world and a robot that needs to put dirt in certain squares?” (There’s a constraint here where the bot needs to end in a certain square as well.) So does looking at this problem in this backwards manner make the problem a constrain satisfaction problem? Let’s define a map for ease of discussion:

_*__

__*_

____

__@_

Well: what are the constraints? The bot starts in one of the two locations. Let’s say the bottom one for an example. So the bot needs to deposit some dirt. Then the bot needs to go N and W and deposit dirt again. Finally SSSE and we’re done. So to translate into a simple path: DNWDSSSE. Now, do some string manipulation S becomes N, E to W, etc. Finally reverse the path: WNNNVESV.

Yes, this problem can be approached in a CSP manner. I glazed over a lot of details here like how to backtrack and find paths. Moreover, I did not find an optimal solution. Had I started in the topmost dirty block I would have come up with one of two optimal paths. But this does not always work. Consider:

*_*

_@_

__*

The “Topmost start” heuristic does not work here. A “farthest from bot” does not work. So any simple heuristic is out of the question. You can quickly conclude (I hope) that this problem gets very messy very quickly.

So what have I concluded: To approach Vacuum World in a CSP approach is far more complicated than in the manner required for the assignment. No doubt it will lead to many headaches, and will not guarantee a faster answer, or an optimal solution. It is a good brain exercise.

Blackjack

2012-02-07T18:25:00.001-05:00

As of late, I've been playing a fair amount of online blackjack (not for money, mind you), and in doing so I've learned a bit about the optimal strategies to apply to various blackjack rule sets. After signing up for AI, I've begun to look at this and other things I like to do or problems I encounter with the mindset of "How could I get a computer to do that?". As a result, I begun pondering the notion of a program which could not only play blackjack effectively with the standard rule set (1.5x blackjack payout, splits allowed up to four and on any pair of face cards, and surrendering allowed ), but which could do so optimally, even count cards and adapt to non standard rule sets (different blackjack payouts, different splitting rule sets, multiple decks, etc.

I don't know much about counting cards outside of what I learned from watching the movie 21 (see: nothing), but the concept still appeals to me.

The basic function of such a program would be simple to implement on an efficient level, relying simply on a lookup table of probabilities to see when to hit, stay, split, double down, or surrender, but could span to enormous levels of complexity at higher levels of operation.

The main reason for this complexity is that, given the nature of blackjack, winning one hand may in turn result in the following X many hands to favor the dealer. As a result, dependent on which cards have currently been played and which still remain, it may be ideal to surrender or stay on a hand for which it would be immediately favorable to hit according to a simple lookup table of probabilities.

What I believe would therefore need to be done in order to optimize the outcome of such a program is for not only the probability of the possible immediate outcomes to be calculated, but for those outcomes to then be expanded in order to determine all possible resultant hands, and for that frontier to then be repeatedly expanded in order to determine the weight (probability * payout) of said resultant hands. If then it is determined that the total weight of all hands resultant from hitting is less than the total weight of all hands resultant from not hitting, the program would then make a decision to either stay or surrender.

This decision also adds complexity to the problem, though it may not seem like it. The reason for this is that, while it is typically advisable to surrender only under the following circumstances (as surrendering also forfeits half the player's bet):

Player's hand is a hard 15, Dealer is showing a 10 or Ace
Player's hand is a hard 16, Dealer is showing a 9, 10, or Ace
Player's hand is a hard 17, Dealer is showing an Ace

To stay additionally implies in a fair number of cases that the dealer will hit, which again forces the program to determine what possible changes can result in the deck from this action. Finally, as the dealers hand is only partially partially observable (one of two cards showing) during much of the game, becoming completely observable only once the player either stays or doubles down, and thus surrendering would also force the program to keep track of the number of cards for which observability is lost, as this would be the number of cards which could be either in the deck or in the grave.

Smarter Algorithms

2012-02-07T18:18:00.004-05:00

Between talking in class and reading the book my head has been buzzingwith search algorithms. I started thinking about what makes a good searchalgorithm and what trade-offs can be made in order to make one better. It iseasy to see that by combining different parts of simpler searches you can makemore complicated but more effective searches. This is even more apparent afterreading some of the sections in the book (namely Ch 3 and 4) where it talkedabout algorithms such as iterative-deepening A* (which is a variation ofiterative deepening that uses an fbound instead of a depth bound) which shows how combining two algorithms can beused to good effect. The book also brought up an interesting algorithm calledbi-directional search where you expand from both the goal and the start stateand try to find a state in the middle where they meet. This can only be used invery specific situations and is rather complex, but if you can create a goodalgorithm to work in both directions it could make for very efficient results.

One of the other things I started thinking about was an algorithm thatcould be aware of itself. By this I mean that it could understand that it hit acertain part of the search or that the current search type was not working inthe problem and change itself (switch to an entirely different algorithm,change the heuristic, etc.) so that it could better handle the problem.

Take into account a very complex problem where a certain heuristic is nearperfect but only in some specific cases of the problem. Say that theenvironment was only partially observable so it would not be known from thestart whether it was in one of these special cases or not. The program couldthen start by trying to expand states until it could decipher whether or notthis heuristic could work and then switch to a different algorithm (such as A*)that utilized the correct heuristic.

Other algorithms could perhaps be made for situations with extremely variedsolution lengths so that in the beginning it could expand without worryingabout space for a faster solution time until a certain threshold was met, then itcould switch to a space saving algorithm like beam search.

I feel as though these would mostly be made on a problem to problembasis, but it is still interesting to think of these sorts of things as we moveforward.

Final Project Ideas - Games and Neural Nets

2012-02-07T09:36:00.000-05:00

I've spent the last week wracking my brain for some original final project idea. A lot of my classmates seem like they are going to program a game, which is a great idea, especially if it is a simple world that would give them a chance to develop more sophisticated AI opponents. Programming some simple game would definitely be interesting, but the game would have to be carefully chosen to limit the game space and problem. Some games that come to mind are Connect Four, Mancala, Go Fish, and perhaps Uno. These games are fairly simple and have clear goals that could be calculated by a heuristic. I would rather do something more interesting, like Risk, but after attempting to code a non-AI chess game, I understand that getting the actual game coded is half the battle and would rather spend more of my time on the AI.

My other idea is to create a neural net and train it to recognize alpha-numeric characters. For those who don't know, neural nets simulate networks of neurons in our brain. Each neuron is represented as a node with multiple inputs, each with a different weight, and one output. When given input, the node adds up the weighted input values and only outputs a signal if it exceeds a specific activation level. These neurons are connected together in layers, with the base layer accepting input, such as pixels in a picture, and then consecutively smaller layers that accept input from layers below until one output is reached. Initially, each connection is given a random weight, which is then adjusted to "train" the net to exhibit certain behavior.

Training can be accomplished in several different ways. Supervised learning uses a function to give the network constant feedback about it's solution to a problem compared to the known correct solution. It give the net a set of training examples and the teacher adjusts connection weights so the net matches the correct answer to the corresponding problem in the examples. Unsupervised learning is similar, but the net adjusts its own weights to correctly learn the training examples.

The most common use for neural nets right now seems to be character recognition and language-associated tasks. I have read about a university building a net to conjugate English verbs. They trained it first with irregular verbs (be, being, been, etc) and then trained it with regular verbs. By the time it was proficient with regular verbs, it had mostly forgotten the irregular verbs, but a refresher course soon had it accurate conjugating both types. I think that character recognition would be a fine goal initially.

For a little more information, here is a small neural net tutorial a guy from AI Junkie created: http://www.ai-junkie.com/ann/evolved/nnt1.html.

On Data Structures and Code-Tweaking

2012-02-01T19:25:00.001-05:00

For those who have taken Algorithms atUNH, they know that we spent a good deal of time in the beginning ofthe semester going over data structures. This is because datastructures and algorithms are deeply intertwined. This means that agood algorithm with a bad data structure may run a lot slower than abad algorithm with a good data structure. This is not always thecase, as different algorithms rely on their data structuresdifferently, and a linear time algorithm using a linked list willvirtually always be faster than an exponential one that uses a hashtable

I mention this because we touched onthis briefly in class, and it got me thinking about just how muchspeedup we could achieve. I remember in Algorithms, my Djkstra'salgorithm seemed a bit slow to me, and the concept of Fibonacci heapsarose in class. While I did not go so far as to implement a Fibonacciheap, I did make some modifications to the heap I was using, and Isaw what I would call significant speed-up. This idea has beenre-appearing in my mind, and I've been nitpicking the currentassignment, trying to find little things that might speed it up evenmore. I haven't gone so far as to decide to write it all inassembler, but I have been paying close attention to my datastructures and any pieces of code I think might be called a lot ormight take a lot of computation time.

I also remember hearing a lot aboutcomputation time that we consider insignificant because it is aconstant factor. It certainly depends on the problem, whether or notthe initial computation time is considered a big number. One secondof load time looks small to a problem that takes a minute to solve,but not to one that only takes about three seconds. And if we couldsomeone cut down on the load time, that would mean a speed-up overall the cases, which is good right? But what if we had to decidebetween a longer start-up time and an algorithm with a better Big O,or an algorithm with a shorter load-time, but a worse Big O runningtime, meaning it runs slower on larger problems. A really neat ideawould be to use both and decide when the data was large enough toswitch to the one with the better overall time complexity. I justthink it's interesting, and a bit fun to think about tweaking thesethings and deciding if it will be worth the extra work in the longrun. I know I am already thinking about them, but I'll just have tosee if my extra work is worth it in the end.

Initial Final Project musings.

2012-02-01T12:53:00.001-05:00

My initial thought on my final project is that I would like to tie it in to a project I've had in mind for a while: a print run detector of Magic the Gathering packs.

The goal of a print run detector is to analyze a pack of Magic cards (which is 15 cards), find the subset which is common (9 cards or so), and test all probable sequences of that pack against all probable sequences of previously checked packs. The purpose of this is to determine the order that the cards are printed in, by finding the subsets of cards that appear next to each other in multiple packs. The results would naturally become more accurate after analyzing more packs.

The main problem I can see with doing this is that there is an absolutely enormous amount of data that has to be stored and checked in order to determine if any given sequential subset has been seen before, or if it hasn't, if it is likely to be seen again (depending on how many packs have already been looked at, for instance). I think that some sort of heuristic could be found or developed in order to reduce the amount of data that has to be searched and stored.

This is a project I have been thinking about for a while, and would love to be able to tie it in to my AI final project.

-Dan Pelcak

Game AI concept

2012-02-01T11:46:00.000-05:00

As somebody who has effectively signed his life away to the pursuit of game design, I was certain fairly early on that my final project for this class would be something to do with video games. That is, after all, one of my primary reasons for having signed up for this class. What exactly this final project will entail is still up for debate, and may only be related to game design indirectly, but here's what I've considered so far:

I currently have two platformer style games which are stagnating due to an abundance of course work. In one of these games, beyond the primary mechanic of platform/wall activation/deactivation, the player can move throughout the game map according to the physics constants I have defined for the game.

My goal for my final project, at least as of now, is to develop an intelligent enemy AI which can chase and attack the player in both dimensions. What would make this difficult is that, given the number of potential nodes on a single map coupled with the effects of gravity and other physical constants, the AI would need to account for an extremely large number of possibilities in a very short time. Additionally, the AI would have partial visibility, in that they would have complete observability of the map at all times, but only of the player when they are within the AI's line of sight. When outside of the AI's line of sight, the AI would need to predict the player's course of action, knowing their goal, and act accordingly in order to continue the chase.

Some Very Early Project Ideas

2012-02-01T07:58:00.000-05:00

We've been told that in this class we're going to be dealing mainly with deterministic systems that involve single agents and where the worlds are fully-observable. So for some possible project ideas, I would consider studying AI problems that deal with some combination of attributes from these.

The first thing that struck my fancy was the mention in class of systems that involve worlds which are hidden to the agent. It seems as though it would be a fruitless endeavor to have an agent that has no input from its environment, so I would be very interested in researching applications of such problems and the algorithms that go about solving them. I could not pull up too much on the topic after a few google searches, but I hope this is just because I'm too tired to think straight and am not searching for the right terms, and not because there is not a lot of research going on in this field.

Another possible project idea: I've always been fascinated by the question of what is really behind self-awareness/consciousness in human beings, and the potential of recreating this in a non-living thing such as a computer is a very interesting idea to me, and one that I'm not convinced is possible. I know this class is not focused on this aspect of AI at all, so perhaps I could find a way to tie in current research in neuroscience on consciousness to current research on the more computer-sciencey side of AI. Not exactly sure how this would work, but maybe there's a way.

Systems that involve multiple-agents sounds like another interesting topic idea for a project.

For now, these are very general ideas so I'm going to keep thinking.

Assignment One So Far

2012-01-31T23:44:00.001-05:00

Since I've spent all of the time I havededicated to this class so far to working on the first assignment,I'm going to write about my experiences with that so far and thoughtsgoing forward. First off, I'm writing this program in C. So, noclasses, objects, constructors, destructors or any of that. Justfunctions and structures.

One thing that really surprised me washow quickly depth first was able to produced a sub optimal solutionby giving it a full closed list, whereas without one it is extremelyslow, even with cycle checking. Running it with the validator oneither of the “hard” worlds it came up with a solution in 0 or 1seconds. Now, the path that it found in this time was extremely suboptimal to say the least. The cost for the plan it generated forhard-1.vw was 539, where the optimal solution was 59. I think thiscompletely blows away the whole linear space benefit, but it wasinteresting to see the memory / time tradeoff.

I have at this point also implementedthe depth first search with iterative deepening. However I don'tthink this is working quite right yet because the solutions I getwith it aren't optimal. The solutions it finds are clearly betterthan just using depth first, however something else is clearly goingwrong. The solution I get for small-1.vw costs 35, where thereference solution gets it in 24.

A less relevant but still ratherinteresting problem I ran into was with writing a hash table. Myfirst instinct for this program was to store the state as a 2D arrayof chars. However I ended up deciding to just store it as a string,mainly to simplify storing it in a hash table and writing the hashfunction. The hash function itself I found very interesting. Afterdoing some research it turns out some of the best hash functions areimplemented by multiplying the hash by a seemingly random constantthat is often prime, but not always and no one seems to have a verygood explanation for why these constants work so well. Theimplementation I chose, which seems to work quite well is talkedabout here: http://www.cse.yorku.ca/~oz/hash.html.It's the first one listed, only with the change from addition to XORthat is mentioned. So basically as the page says hash(i) = hash(i –1) * 33 ^ str[i].

I feel as though so far I've spentquite a bit of time putting the whole structure of the programtogether and working out kinks here and there and I think there'sreally a big part of the down side to C. However I am hoping thatthis will translate into overall performance benefits going forward.

AI on its own

2012-01-31T22:45:00.001-05:00

I’ve loved video games ever since I got my hands on thecontroller of the original Nintendo. I always wondered as a kid how someonecould make something in a game that could react to me and even outsmart me, butas I have come to realize over the past few years that most game AI pales incomparison to something that needs to complete a complex function in reality.

Lately I have been thinking a lot about how incredibly complexAI needs to be to handle a real situation without help. There are an infinite number of thingsthat can happen and some robots would need to be able to handle just about all ofthem. This is especially problematic in environments we cannot readily assist orcommunicate with it. Space is a prime example of this. Unmanned ships are an especiallyimportant part of space exploration and possibly even future travel.

It is impossible to think that a robot could ever be indestructible andequipped with indestructible sensors for every situation, and thus must besmart enough to handle situations that it would not even be able to directlydetect. This would mean that it would need to assume some sort of probablesituation and deal with it that way and perhaps change its beliefs if its solutionwas not working. Would assuming the probable situation be the most helpful tothe robot though? Say there is a chance that executing the solution to theprobable state would cripple the robot if it was in an extremely rare situationthat could also be possible. These sorts of things need to be analyzed inreal-time and would occasionally depend on the speed of the decision. Beyond thisthere are the possibilities of sensor failures or total information blackoutsthat need to be dealt with.

In an environment where almost anything could happen how doyou even approach the creation of an artificial mind that could handleeverything that is probable never mind possible without human input? Obviously not an easy questionto answer, but something I hope to learn more about as this class goes on. Lookingat the book my best bet would probably be Ch 13, so when I some free time popsup I’ll probably read that.

AI Musings

2012-01-31T21:40:00.002-05:00

AI Musings

In my considerations for the current assignment I am tearing my brain appart trying to find an efficent algorithim. And then I realized that if I am going to take the 730W course, I need to do a blog entry. So I thought I would blog about my current idea for an algorithim.

"But wait Jonathan.... This is a contest. Don't tell them your plan." I suddenly heard myself yelling in my mind.

So I'm gonna keep that to myself, and instead propose some questions. (Both applicable to the current assignment, and good considerations whenever working on any code.)

1) World state. Do I (Can I) know the exact state of the world? IRL: No. But I know the world state as I observe it. In the case of the assignment I think we can observe the world state with acceptable precision. I think.

2) (Assume we can know the world state.) So if we have this perfect knowledge can we then have a perfect knowledge of what we are looking for? If so, the ability to produce an inteligent path should be much easier. Right? Is this legal? I don't see why not. If we're playing with an ideal world...

But then, will we ever be working in an ideal world? No. So? An approach that solves the problem solves the problem. So: is it cheating to apply all my resources to solve the problem? If I legitimately have the resources at my disposal why shouldn't I use them? Well: it may be too costly to use them:

>A simpler algorithim may become faster.

>A component needed to obtain said resources may be/become too expensive (I'm talking hardware and dollar signs cost here.)

>My professor wants me to do it in a way that excludes the possibility of this omnipresent knowledge. (Cost of grade.)

And therefore I conclude:

1) Assume yes. Ask anyway.

2) Assume yes. Implement Depth First, Uniform Cost and Iterative Deepening as specified. Play omnipresent card when developing my A-star algorithims and hope for the best. Ask anyway.

Battleship Final Project Pitch

2012-01-31T20:37:00.000-05:00

Battleship Artificial Intelligence could be a fun topic to explore for a final project. The problem can be described as follows:

Initial State: The initial state is an empty board. The initial state also has the notion of a first attacking player.

Actions: The only real action is to guess a coordinate pair (x,y), where x = [A,J] and y=[1,10], and shoot. The response is either a hit or a miss.

Transition model: shoot(x,y) is deterministic; the function either returns a hit or a miss.

Goal test: Checks whether or not all of the opponents ships have been sunk. This signifies a win.

Path cost: Each guess costs 1 move. The path cost is the number of guesses to eliminate all of the other players ships.

Most of the intelligence is involved with deciding which guess comes next. After a hit, one obviously should continue guessing around the same region in order to try to sink an opponent's ship(s). Thus, the spaces in cardinal directions should be checked with regards to a hit, as ships can only be placed horizontally or vertically. Once a hit is encountered, a depth-first search could be implemented to find surrounding places to hit. The process of forming a guess after a miss could also involve some intelligence. The state-space is finite, so the process of guessing could be more than random. Perhaps there are ways of determining regions that are most probable to contain a ship based on rectangular area, and guess those first.

This game would be fun to explore, though there is some guess-work involved in solving the puzzle. There is not necessarily a way to determine the best move if a miss is encountered, and many moves are considered equally likely to hit a ship early on in the game. When a hit is encountered, though, the guess-work disappears, and we are left with a familiar search of the state-space to solve the problem.

blokus

2012-01-30T22:08:00.002-05:00

i'm considering doing my final project on the game "blokus" which i recently acquired and suck at. since i'm a beginner, i don't know much about its strategy. rather than practicing myself, i'd like to see if i can learn things about blokus strategy by writing a program and observing the way it plays. i'm particularly interested in "openings" (strategies for laying down the first three or four pieces, before there is much interaction between the players) and how to interact with opponents' pieces when they are near or in contact with your pieces (blocking and "escaping").

after writing the preceding paragraph, i read chapter 5 ("adversarial search") sections 1 through 4 in the textbook. the required work all seems very doable with the exception of the development of the evaluation function. i do not think i could write a very good one, or come up with a very good set of features on which to base it, without becoming much more familiar with the game.

the "endgame" may be easy enough to investigate, but my gut tells me that it wouldn't be very interesting. when i've played, that's the part of the game that i've felt to be the least strategic; it's more about carrying out plays that were planned earlier.

Greedy Searchs

2012-01-30T15:53:00.000-05:00

Talking about searches in class sparked my memories of an AI course I took in high school and the algorithms we learned. I just refreshed my knowledge of the Greedy Search and thought I would share how it works and the implications of implementing a greedy search.

Greedy searches are designed based on the premise that a path with the best possible short-term gain each time will result in an approximation of a globally optimal solution. In other words, when traversing a weighted graph, the algorithm will choose the edge with the lowest cost regardless of what might be next. It only looks at the current situation and doesn't use any heuristics to project farther into the future. Because it doesn't look ahead, cycle checking is critical in order to guarantee a solution (in a finite graph).

Greedy searches work well in a simple search space. With larger, more complex problems requiring a more forward thinking algorithm, they churn out poor solutions that are closer to the worst case solution than the optimal solution. The inability to look past the current branching choice means they may choose the cheapest edge now and miss the overall cheaper path that would be found by exploring more expensive paths.

In the board game world, greedy searches are best used when you want to maximize short term gain and largely ignore strategic thinking. As a highly strategic game, chess is a no-go. Scrabble, however, is much less strategic and is often won by getting the greatest possible points on each term rather than setting up and scoring one big word. This search type is pretty limited in most domains, as most other searches implementing heuristics or forward thinking will outperform a greedy search.

A cousin of the greedy search is the Greedy Best-Fit Search. A best fit search is one that chooses the most promising node based on some rule/heuristic. In this case, greed is the rule. A greedy best-fit search searches a graph by choosing the node that it's heuristic evaluated as closest to the goal state (has the lowest heuristic-based cost). While this search will generally find the shortest path, it doesn't usually evaluate the edge cost and has the potential to choose a very short, but very expensive path when a better option exists. Quite a bit of it's cost efficiency depends on the node evaluation heuristic, though.

A greedy best-fit search would likely be used when a short path is desired and time/memory is low. Applications in the board game world include Chinese Checkers, where the goal is to get all your pieces across the board in the shortest time/path possible.

Welcome!

2012-01-30T10:42:00.002-05:00

This blog is for the students of CS 730W at UNH to post their weekly writing. Anyone else in the class is welcome to post or comment as well. We encourage three kinds of posts: 1) design ideas for your final project, 2) critiques and extensions of ideas from class or the textbook, and 3) ideas for applications of the ideas from class. (Other kinds of posts are good too, as long as they go beyond mere reactions to the material and actually engage in critiquing or extending the ideas.) Please be sure to make it clear which kind of post you are doing!

(I've cleared out the posts from last year's class, so I hope you weren't here looking for them...)