Game AI

I am afraid I have to push the ‘Go Engines Analysis’ post to a later date.

Commercial and Academic Research in Games

Generally, most research done by academics is of some use commercially. And naturally, one would expect the same to be the case in game AI research also. Only, its not. Commercial games concentrate more on the graphics, and the user experience part of the game, when compared to AI. If there is a bold announcement from the industry stating that the next edition of their game is to have the ‘next-generation-human-like-AI’, they have mostly been huge let-downs, and miserable failures. The strongest AI, in commercial games, these days are those that ‘cheat’. Have you never wondered in-game, at least in the harder levels, ‘When did he get so much points?’,’Does his nitrous never empty?’. And sometimes just plain ‘WTF!!’

Instead, the NPCs ( Non Player Characters ) in the majority of games are controlled by finite state machines, lists of conditional statements, and the occasional A* path finding algorithm. Typically, no learning is present in either development or execution of the AI. Everything is hard-coded by the human game developers.

Academic Research into game AI hasn’t been too rewarding either. So we built the strongest Chess player in history. And we are building better ones. Has that helped us understand how people play the game? How we learn to play the game? How we interpret patterns? Also, Academic Research is mainly focussed on making AI increasingly better at the game, aiming to make it the best. Naturally, that’s not the commercial requirement. Would anyone but Kasprov want to play Deep Blue? What is required commercially is that the player’s opponents should neither be too domineering, nor too easy.

How Games interest us

According to Raph Koster, a game is fun to play because we learn the game as we play; we understand and learn the patterns underlying the game, and finally “grok” how to play it. This requires that the level of challenge always is approximately right, and that new patterns are always available to learn – games that are too simple or impossible to understand are boring.
Another theorist who has tried to nail down the essence of games and why they are fun is Thomas Malone. He claims that the factors that make games fun can be organized into three categories: challenge, fantasy, and curiosity.
The existence of some sort of goal adds to the entertainment value. Further, this goal should not be too hard or too easy to attain, and the player should not be too certain about what level of success he will achieve.
Games that include fantasy, according to Malone, show or evoke images of physical objects or social situations not actually present. The sensation of being somewhere else, being someone else, doing something else.
As for the third factor, curiosity, Malone claims that fun games have an optimal level of informational complexity in that their environments are novel and surprising but not completely incomprehensible. These are games that invite exploration, and keeps the user playing just to see what happens next.

The most interesting applications of real Computational Intelligence and Machine Learning methods

NERO, is a fantastic new concept. The player ‘teaches’ (initially stupid) bots to become ‘trained’ soldiers. In the core of the game is a learning system called NEAT. It involves using Genetic Algorithms to train Artificial Neural Networks( NeuroEvolution ). NEAT involves continually taking ANNs, from an initially random population, and then combining the best among them in the hope that it’ll result in a better ANN.
Another place where learning methods may be put to use is Automatic Content Generation. Here is an intriguing new concept. Customized racing tracks according to a player’s skill. The next Prince of Persia edition claims, custom player experience. Although it is not clear of how ‘custom’ it is to be, this sounds like the beginning of something big. So Automatic Content Generation is definitely IN.
Another instance of Content Generation, in the process of development, is a game called Galactic Arms Race, being developed by Ken Stanley, and his team at UCF, the same dude who pioneered NERO. Remember the classic, Space Invader arcade game? It seems to be something similar except, there is a large and INCREASING variety of guns you can choose from. And each gun fires differently. That is, the graphics is different. And the graphics was not coded by hand, it was EVOLVED by a custom version of NEAT.


Game competitions at GECCO

GECCO 2009, is to conduct two competitions, Salamander and Car Racing. The details of Salamander are not too clear to me, but looking at this and this, it seems, the Salamander is to learn to walk and then catch flies around the house.
The car racing controllers are tested on TORCS. (TORCS, does not have dynamite graphics, but I find it a lot more difficult than NFS, but thats just my perception. It was built mainly for testing AI conntollers). Last year’s entries were quite a variety. There was a controller based on NEAT, and there was also a hand coded controller(Although, I doubt it performed as well as the other trained/evolved controllers, score CI/ML!). The significance of a trained controller is that, provided it is trained sufficiently well on a good track, it acquires the basic driving skills. This would be a big plus for games like Trackmania Nations, which allow the gamer to design his own tracks, but does not give competing cars, leaving the gamer to look for human opponents, to race in his own track. Another aspect of trained units is the versatility. A small change in the training process and the controllers become more aggressive, trying more to push the other players off the track!!

And now..,
The crux of the matter. If you were to host a contest, which game, do you think, considering the expanding scope for computational intelligence in games illustrated by the examples above, would be a good bed for innovative application of CI/ML?
Remember, its a time bound contest. The participant should have enough to time to experiment.

Advertisements

The Game of Go

Game of Go
Game of Go

It is amazing how simple rules can result in breathtaking complexity. This post is about such another game :

Go

Chances are, you have already seen people play the game. I had seen it first in ‘Fist of Legend‘, Jet Li’s adaptation of the ‘Fist of Fury‘.

It is so old that it was mentioned in the ‘Analects of Confucius‘( 479 B.C ). In fact, the American Go Association cites this is as one of the top ten reasons to play Go.

When you play go, you are doing something that billions of people have done for thousands of years. Many centuries ago, people were doing the exact same thing, in the exact same way.

What an absurd reason to give a promising player to choose the game!!!

Crisply, the rules as specified here:

  • Go-board(Goban):19 x 19 intersections.
  • Back and White play alternatively.
  • Black starts the game.
  • Adjacent stones ( of the same colour ) are called a string.
  • Liberties are the empty intersections next to the string.
  • Stones do not move, they are only added and removed from the board.
  • A string is removed if its number of liberties is 0.
  • Score: Territories(number of occupied or surrounded intersections).

Plain and simple. There is also a large set of terms associated with the game which you will nedd to know if you are playing / coding a player. All of them, Japanese. I strongly agree with the subject of this post, so try to play a few games before you get coding. I would suggest GNUGo, with Quarry to make a good beginning.

However, Computer Science considers a human level Computer Go player an open problem. It belongs to the same class of problems as the ` P = NP ` and ` The Church Turing Hypothesis `.

A comparison with Chess, ought to bring more light on the subject.

  • Computer Chess Programs have defeated Chess Grandmasters, and have become so good, that are now competing among themselves for Chess Supremacy.
  • An average Go program, on the other hand, are routinely trounced by Asian school children.
  • At any stage of the game, Chess, on average, has 37 possible moves, decreasing as the game progresses. ( Lesser coins, lesser moves )
  • Go, on the other hand, averages 250 possible replies per move.
  • There are terms in Go, look here, each of which needs a representation in the program.
  • Chess has very little such terms, en passe, fortress, and the like, and provides lesser challenge to a programmer who has little knowledge of the game.

If you cannot truly assess the complexity of the problem, here’s one more trivia, Go, is associated with the number 10700. This number is almost definitely an overestimate considering that the estimated number of particles in the Universe, when I last checked, was 1091!! However, more reasonable estimates aren’t too far from this number either.

A brief Intro on how computers play ( board ) games:

Computers, play games by searching in a state space tree. Many use a theorem called the Minimax Theorem. Chess, Go and most other board games are said to be complete-information deterministic games in that both players know everything there is to be known from the beginning to the end of the game. There is no role for chance here. In 1928, Von Neumann proved that such games are always zero sum. In non formal terms, a zero-sum game is a game in which one player’s winnings equal the other player’s losses. It is pretty much like cake cutting. So a good move means that the opponent has got only worse moves, all of them in all variants leading to favourable positions which are therefore unfavourable for the opponent.

An example of the minimax algorithm should be very useful here :

Minimax Example

Minimax Example

Consider a two-player game, where each player takes alternate turns ( which is the vast majority of the board games today ). Now as shown in the figure, you have three options, to each which your opponent has three options in reply. The tree’s root indicates that you’ll choose the move that lands you in the best position possible when you are to play next. The numbers in the circle indicates your position after that move. Level 2 is your opponent’s move. Initially, the tree is constructed with empty circles, and evaluation is done from the leaf to the root.

Some evaluation function, say f(x), evaluates the board position and returns the values at the leaf level. You take the minimum of the points your opponent’s move left you and put it in the corresponding higher level. Then, you take the maximum of all the points your move will leave you and put it in the higher level. What has happened? You are left with a guarantee that you’ll get at least +1 no matter what your opponent’s response is. IN simpler terms, you have maximised your minimum profit. And hence the term minimax.

** A minimax tree is generally more than 2 ply( 1 ply is a single player’s turn, turn itself being an ambiguous term, to be used across multiple games ) deep.

Here is more on zero-sum games. A wiki minimax example.

Here is an article that shows why MInimax Theorem is not always practically optimal.

Many optimizations have been made to this approach the prominent of them being, Alpha-Beta pruning.

Naturally, it is important how deep your tree is. The evaluation of the game state is also just as crucial if not more, in the grand scheme of things. A good evaluation function can reduce how deep you need to look.

All of the most famous Chess engines of our time use this technique. For a game like Chess, with an average branching factor of 35~50, specialised hardware with pre-calculated open-game and end-game tables is enough to beat a Chess Grandmaster. In fact it even defeated the highest graded Grandmaster in history.

Such an approach becomes immediately inadequate in the game of Go. No hardware can search in such large a state space. Also, an accurate evaluation function is also very difficult to arrive at. Well, then how do today’s programs approach Go?

A look at the current Computer Go Scenario :

The most powerful computer Go programs in the world today are :

  • GNUGo
  • MoGo
  • CrazyStone
  • Go++
  • NeuroGo

A rough analysis of these five should be of great interest. Updates on this post and further posts will be regarding this.


Bookmark and Share

The Game of Life

This is not an article on philosophy.

This is about a zero player game called, Life.

Considering its a zero – player game, who would want to play it???

Gosper's Glider

Gosper

But before that, let me just give you a brief intro on what it is and how it is played. It is what one would call in computer science terminology as a cellular automaton. Cellular automatons are studied primarily by biologists, mathematicians and Computer Scientists.

In the second year of our computer science course, we had a paper on Thoery of Computation. And “automata”

was the most uttered word in the class. The paper was complete theory and did not seem to give any scope for fun or enjoyment, unless you were a nerd, or a mathematician.

It was in Robert Kruse’s, Data Structures and Design, that I first came across Life. So here’s the deal.

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbours comes to life.

The initial pattern constitutes the ‘seed’ of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

Simple. Very basic indeed, simulations of how Life may exist, overcrowding, loneliness, all only too familiar for us humans. Simplicity is always a defining characteristic of an automaton. So there would be starting population, and once the sequence starts, it continues, without any intervention.

I see no further point in explaining in theory about stuff that you really can enjoy once you see it for yourself. I’ll direct you here to a Java Applet at Math.comhere Somewhere in the page is a link to a Java applet. I had also seen an online Flash implementation, as an active essay, which I am unable to retrieve now. Anyway, Go ahead. Experiment. Try your own signature, and see what it results in. How about if you draw a smiley, what happens??? Chances are most likely that the population eventually dwindled into nothing or it stabilised, i.e.., split up and formed gangs, stopped interacting with other gangs, and eventually settled down.

When John Conway published his ideas in Scientific American in 1970, he had conjectured that there could not exist initial populations, that would neither die off nor stabilise. He offered $50 as prize money to anyone who could prove or disprove his conjecture. A team from MITlead by Bill Gosper won the prize. Gosper disproved Conway’s idea by developing an initial population, called the Glider Gun, which generated a glider after every 30 generations. Thats the picture at the top of the page. Eventually more and more initial populations were found that had traits similar to the Glider Gun. Many of them were more or less.., Guns. After every X generations the population would produce a unit that would fly away, and live an endless life. I have provided a link at the bottom, in case you are interested.

Glider

Glider

Gosper’s glider was a hit. So much that, this symbol called ‘Glider’, to the right was proposed to be adopted as the symbol of the hacker community. “The Hacker Community” I am referring to here is not the one that goes around busting the Internet. Any enthusiastic coder, who tweaks a software.., could be roughly called a programmer. I am obliged to give a reference here.

[ A similar, but not related concept is the Collatz Sequence. A simple rule indicating what one particular number would mutate into next. The sequence of numbers end, when you reach one. The conjecture is that from any number, on applying the rules, it always ends in the same pattern => 16-8-4-2-1 ]

It only gets more interesting. This, “Game of Life is said to be Turing Complete“. A Turing machine is essentially an infinite tape with a pointer attached to it. But, amusingly, you can do EVERYTHING using a Turing machine that you can do using a modern day computer. It may sound , a little insane perhaps, when I say that a tape can simulate a PC. I restate, this Game can simulate your PC. Look at it this way. You would believe it if I say that AND, OR and NOT gates could simulate a PC. Naturally, that’s what PCs are made of right? Maybe it would sound a little more sane or credible to say that the game can simulate all of these gates.

Hash Life

Consider implementing the Game of Life using say, Java. Most normal approach is to keep two copies of a 2D Boolean array and juggle between them as the current population. Bill Gosper also developed an algorithm for a much faster implementation of Life called Hash Life. There are various places where one could tweak the original approach, but Hash Life remains the one of the fastest algorithms known. I hear that there are only 200 or so implementations of the algorithm all over the world. Maybe one day, I could implement one on my own…

In retrospect, John Conway’s implementation was using using stones and pebbles.

A crazy Proposition

I have been recently getting more interested in Evolution, physiology and Genetic Algorithms. And I started wondering if one could evolve an initial population that would keep multiplying. It seems utterly non-sense in one sense in that the “World” is utterly chaos. How do you judge the fitness of populations? How would one implement a cross-over?? Anyway, just a crazy idea. I just wanted to put it down, in case, somebody stumbles upon it and gives me a hint.

Further Reading:

A new kind of a Game

It doesn’t look visually enticing, but I am pretty sure its darn good. No, I have not played the game yet.

NERO

Now, I wasn’t expecting to write a post on a game, any time soon. Not even on DotA. But this is just too good a game for me to resist. I have been quite intrigued by the concept of Evolutionary Computation. One lazy Sunday, I started looking for more stuff on Evolutionary Computation. I found a lot. Particularly, a post-doctoral researcher’s blog. Julian Togelius. He’s published a paper on solving Sudoku using Genetic Algorithms. Serious stuff that! One of his other papers have been judged as one of the top ten AI game innovations of the year. This dude was one of the organisers of a Simulated Car Racing Championship atWCCI 2008. It seems there are not a lot of games available that actually use the latest Learning Techniques.

It was very funny in the beginning when I looked at the games’ graphics( WCCI ). Not a ‘Need for Speed’ then. On further reading, I found more on the rules of the game. From a programmer’s stand point, I thought, not very easy to program a controller. All the various cases. How could it adapt?? Perhaps learn?? Neural Networks then?? Neural Networks are to put it very very simple terms, like a brain. ( Please note that this is a gross over-estimation, it resembles the brain only in that it can learn new stuff. It is not even close to the functioning of a brain ). Perhaps neural networks would have been the answer if the same question had been put forth a few years ago. Today, ANNs alone will not suffice!!

Genetic Algorithms are now used to train Neural Networks. OK. Imagine you are given the job of teaching something to someone. If you couple GA with ANN, it’d something like, you just have to tell the person, how well he has learnt the subject, and he’ll keep improving all by himself. ( Of course, this is another gross over-estimation. If this is very non-technical please refer to one of the links given in the side )

It just got more interesting after that. I learnt that one of the Car controllers was evolved using rtNEAT( real time NeuroEvolving Augmenting Technologies ) developed by Kenneth O Stanley at University of Texas at Austin. NEAT not only evolves the best neural network of a given structure, it also evolves the best structure for the purpose. Fantastic stuff. As I kept reading, link after link. I get here. The page gives a detail overview of how NERO is played and how it is being developed. Please do read it. Its an interesting read. You’ll start wondering what kind of games will be the next big trend.

I have added on my links lists some of the more interesting blogs I have found during my research. Anyone interested in AI, please do have a look at these pages. I definitely plan on writing more posts on my own discoveries on the Web about AI, more particularly, Evolutionary Computing. And next time, I hope I try to convey more technically what I actually wish to convey. Cheers.

Social Bookmarking

My faith in Humanity

Or maybe, the loss of my faith in Humanity

All these days, I have been positive, that the Human Race is simply not capable of destroying itself. Perhaps now, its about time I changed my views. I had forever hoped this day would never come. Alas, it has.

My days in Japan had rejuvenated my beliefs a little. Japan was clean and green and its people well aware of their duties to the environment. And then, I land at Coimbatore, a completely balded city. Dusty and in a ruin-like state. All in the name of development. I return back to Chennai, and as always there is Coovum ever ready to show off as the most violated, polluted river on the face of the Earth. My heart cringes in despair, EVERY time I take a ride on the local trains. I can’t bear the sight of the river. The sludge. That smell. And still there are those who pass over it everyday, not giving a damn as they pass by.

It is only once in a long time that I watch TV. And call it misfortune, to add to my despair, ‘An Inconvenient Truth’ was on on HBO. The hope the man has should really be commended. The ignorance of the American people, intrigues me. Why is it that everything is treated as hoax. Why? Armstrong never landed on the Moon. The 9/11 was perpetrated by the Government. And Global Warming is a lie.

Are they frigging out of their minds?

Why? Money. Isn’t that what everything is all about.

In the US, its about increasing the profits. The fuel efficiency law in force in the country is similar to the one in India, I think. And when a talk arises of putting a more stringent rule into effect, American car makers are the first to start swearing. Ford and GM are suffering heavy losses. If such laws are forced, where would they sell their cars? On the other side of the world, Toyota and Honda are flying high. And their market has the strictest fuel efficiency and emission laws. Japan. What an irony. Won’t their markets expand if GM and Ford actually embrace a strong emission rule?

In India, its about minimising expenses / trouble. Why bother to treat the sewage? Its not my problem. Why bother to properly dispose the waste? Its not my problem? Why even bother to look for a proper place to spit? Why not spit here? Why look for a dust bin to dispose the chocolate cover?

No one cares. Why should I?

There was no ice in the North Pole this Summer. I can imagine the response of anyone who I bother to tell it to. “O < like I care >”. Global warming is not a hoax damn it. Its here. And if you don’t do something about it, F*&^, you are not going to do anything anyway. And the TATAs hailed for bring the Industrial Revolution to India, yada yada etcetra etcetra yawn…, aren’t doing pretty things to the environment either. Being an e-member of Greenpeace isn’t every satisfying.

Global Warming. Thats not the only thing thats made me completely lose my faith in Humanity. Terrorism.

Unity in Diversity

What a fantastic concept, eh! The volatility pervading this Unity makes me sick. Of what use is such a unity. The only use of this is that one can swear at the other, at the other’s society and still not be called a racist. Sometimes I think we’d be better off as twenty different countries. And I pray to God I don’t start about politicians in the Country. Gandhi would be greatly ashamed.

I came home this weekend. Saturday, serial blasts in Bangaluru, and Sunday in Ahmedabad. Local news channels in each state crying out that it is their cities to be targeted next. Aaaahhh! What are they trying to be prove??? What the hell do they want? What do they gain by killing loads of innocent civilians? Frankly, I refuse to be intimidated by a bunch of demented fools. Jihad, indeed. If only someone told them what it truly means. Are they going to kill everyone who is not a fundamentalist Muslim? And a pathetic note challenging the police five minutes before the blasts. Sniggering, they must have been as they wrote the note. What a bunch of cowardly ignorants. Just look at this all from a higher plane… What an uncivilised act.

And we are humans!

So many cellular automatons, so many simulations. No simulation could possibly predict that any civilized population would eventually destroy itself. I was convinced that the analogy drawn between the human race and any virus. And perhaps then an automaton could properly predict the ultimate fate of such a race. But such a destiny!!!!

I cannot pen on anymore. I am either so full of spite or despair, or both. Please note that I have not intended to cause any harm, sentimental or otherwise, through this page. I am simply so full of despair and been this way for sometime now that I just had to pen this down. Pardon any inaccurate detail in the page, and please bring it to my notice. I’d be forever indebted.

Sanjeev

Japan Trip – Part 1

It’s been quite a few days now, I’ve been wanting to write about my truly mind-blowing experiences in Japan. Its great that I’m finally getting down to write it . So much has happened that I’ll probably forget most of it if I don’t put it down in words while its still fresh in my memory.
For a few months in my second year, I had been mad about WoW – DotA (World of Warcraft – Defence of the Ancients). I’d happily spend most of my saturdays blissfully enjoying game after game. It was on one such evenings —–

“Sanjeev …, room 10. Ram Kumar .., room …, please come down”

“Who wants to see me on a saturday evening???”

I couldn’t recognize the voice. You can imagine my confused reaction when I realized that it was the Dean who wanted to see me.
A visit from the Dean is seldom good. Generally it is a very organized procedure. The watchman calls out on the mic that the Dean was coming, and everyone scrambles to switch off and hide his cell-phone. There was no warning this time. I was in my shorts and bare-chested. Quite an awkward situation. I got my shirt on, and went to call Ram. He wasn’t in his room.
“I didn’t get into any trouble did I? Why does the Dean want to talk to me? I sure could use some one by side to share whatever I was into. ” By the time I had finished thinking of all the possible things I had done that could have landed me in trouble, I was already standing in front of the Dean.
“You are Sanjeev???”
“Yes.”
“Would you like to go to Japan?”

Err.,”, I thought. Either I’m dreaming or he’s crazy. I remember thinking, ‘You don’t jump in front of a black man in a buffet and ask him to hurry up.’ Chris Tucker in Rush Hour 2. No. It wouldn’t be apt to pull up that dialogue there. After a minute of stunned silence, I replied.., “Yes.., sure.” I would be contacted by a Professor from the Center for Crystal Growth. And Ram Kumar would accompany me on the trip. “Cool.”
And that is how it all began. Call me an antagonist, but I never thought that it would actually happen. I told Ram and we waited for a quite a few days until we got further information. I was once again playing DotA when the next visit came. This time it was not from the Dean. It was from a student of the professor, I had earlier been informed about. Ram was also available then. So we accompanied the dude back to the Professor’s room. Apparently he had spent some time in Japan, and was quite fluent in the tongue. God help us if we were ever to be tested for our knowledge of the language again. I had scored 75 on 450, and failed in the Level 4 exam. I suppose Ram had fared a little better. The professor wasn’t there when we got there. We waited in his room for awhile all the time dreading his arrival.
Many people entered and left the room. We just sat there not knowing who was who. The professor turned out to be a fairly built guy, with glasses and a moderately stately bearing. There wasn’t much talking. We just filled up a few forms. And then….,
“Nihingo wakarimaska??” Do you understand Japanese.
I didn’t know who it was directed at. “Hai, wakarimashita”, I replied. And I received a pat on the back for that. Wow!! Tests should be more like this. We were asked to submit the forms directly at the consulate in Teynampet, and they’d take care of all the VISA issues. Also, “ The last date for the submission of the applications is Feb 28. So you want to submit the applications as soon as possible. The consulate is closed for visitors after 5 O’ clock. ” It was 4 in the evening of the 28th of February.
Great news pro. Thanks for everything.
We did manage to get to the consulate on time. At 5. On the dot. Not without events though. We had stopped on the way to get my photo taken. The shop keeper went on a mad shouting spree when I opened the door to another room. Some guys were watching a cricket match inside. It couldn’t have been the black room. Frankly, I had other things on my mind then to even bother about his furious yapper.
Our contact at the consulate asked us to come back the next day. And he gave us new copies of the same form to be filled again. “You’re the boss man. Anything you say.” So the next morning, Viki and myself, went to submit the forms. Ram couldn’t make it. That ends the first episode. We did not receive any news whatsoever from anyone for about two months. My beliefs were getting stronger.
This is too good to believe. I mean come on we don’t even know how we were selected. Why are we going to Japan? Would there be anyone else with us? Ten days. Sponsored by the Japanese. Is it enough to know only this much??