Quote:Original post by Timkin
Some responses to recent comments...

Original post by Daerax

Quote:
I do not agree with that. Perhaps there would have been stalls and things might have ended up with slightly different notations like in say complexity theory, perhaps a different way of doing probabilities but I am certain that no one man has had so much impact since Aristotle. There were simply too many people approaching the notion of computing from many angles including off the top of my head: Russell, Church, Haskell Curry, McCarthy, Turing, von neuman, John backus...

Most of what arose in western engineering (particularly telecommunications and control) and subsequently computing from the 40s onward was based directly on the understanding of stochastic processes developed by the Russian-Germanic alliance of the late 19th and early 20th century. Generally speaking, western scientists and mathematicians were simply no where near the level needed to create this understanding. There is countless evidence of advances in western engineering and computing being directly based on Russian publications, or on Western scientists having spent time with their foreign counterparts, bringing back the knowledge with them.

During the latter half of the 19th century and into the 20th, there is a single strong thread of Russian mathematicians, predominantly coming from the same school at Moscow State University. The mathematics group there was pivotal to the developments of the time. Everything that came later in this area can be shown to have grown from the knowledge developed by this one group. Kolmogorov was one of those who stood out from the crowd, hence my selection of him.

I could provide examples of the direct links and the basis of my opinion if anyone is particularly interested, but I'd end up waffling on for ages, hence the omission from this post! ;)

Cheers,

Timkin

I do not not want to pollute this thread though it seems to have run a course. I do quite enjoy the history of mathematics.

I am not disagreeing that Kolmogorov played an important role, mainly that his role was pivotal. Things would have happened anyway since there was so much going on. In the area of control and telecommunications there is no doubt his role was greater but not as directly into Computing. With the exceptions of his contributions to intuitionistic logic, a branch of constructivism which people are just now noticing computer science is basically a branch of I do not see much direct influence. The current computer science is a child of early 20th century obsessoins with formalism and rigour propelled by Weiserstrass an overeaction to the poor proofs of the time. Type theory so important now - including for verification of hardware, software and for automated provers - is older than the turing machine.

In terms of giants Turing (british), Shannon (american) and Von Neuman (hungary) have most influence modern computer hardware and design. In software the legacy starts with Peano (italy) and Frege (germany). The names and location attributions are of the top of my head so i cannot gurantee spellings and exact locations.

I would be interested in the sources which state that much of modern computer technology is based in any one place.

Quote:Original post by Daerax
I am not disagreeing that Kolmogorov played an important role, mainly that his role was pivotal.

Perhaps I over-stated my original point. I was not trying to suggest Kolmogorov was the only person responsible... but that he was a key link in a chain that, had it not developed and had it not been applied, we would not be where we are today. I was trying to make the original point that Markov's work did not sit idle for 100 years.

A particular example of the importance of Kolmogorov in the chain...

Shannon (whom we would probably all agree has played a key role in the development of modern information theory and subsequently the modern computer and telecommunications industry) directly indicates that his mathematical theory of communication (published in his pivotal paper of the same name) is directly inspired by the work of Norbert Wiener (check out the acknowledgements in his pivotal 1948 paper). Wiener, of course, is famous for many things, but many will know his name from the Wiener filter and Wiener process (also known as Brownian motion). While a Wiener process is an example of a Levy process, it is actually a simple case of the more general differential Chapman-Kolmogorov equation, which describes the general class of drift-diffusion stochastic processes. The Wiener filter is the generalised filter for Wiener processes. Many would know the specialised solution for linear, discrete time Wiener processes, being the Kalman filter.

While it is acknowledged that both Chapman and Kolmogorov developed their solutions independently, both build on Kolmogorov's work on reversible Markov processes, which are recognised as pivotal to the whole field of Markov processes, particularly in our modern usage. Without Kolmogorov's extensions to Markov's original work, we would not be where we are today.

I also do not agree that 'someone else' would have developed this understanding simply because there were others working in the field. It is definitely the case that more than one person is responsible for where we are today... but as with many fields of endeavour, they can be traced back to a handful of key discoveries/breakthroughs that were necessary before we could move forward.

Cheers,

Timkin

Quote:1) single-player "campaign" type games are very scripted environments. A very small subset of the rules design wants for the game I'm working on now:
- when the player destroys this Item, the AI will counter-attack.
- When the AI squad gets to 20% of its original units -> retreat.
- AI should only throw grenades when no other AI is throwing a grenade and has not for at least 10 seconds.
- Only 1-3 AI should ever rush the player at any given time
- AI should only spend 30% of their time hidden behind cover; further no single AI should remain hidden in cover for more than 3 seconds
- When the player's units get to a Point of Interest they should stop and play a canned set of animations at a specific point to develop the plot.

Personally I see this as one of the great failures of the state of game design today.

Players are tired of scripting, it holds up a sign which reads "BORING AND PREDICTABLE" and they can spot it a mile away.

I don't know if it is helpful or not but I have a PacMan clone on SourceForge that you're welcome to use. The AI is based on NEAT (Ken Stanley's Neuro-Evolution through Augmenting Topologies) so essentially it exists as a GA-NN already. 8^( You're welcome to use it as a platform if you like, though.

http://sourceforge.net/projects/aipac/

-Kirk

PS - If you use it, please keep me updated on the results. You can send me a PM here or we can swap e-mail.

Quote:Original post by sion5
Does anyone have a small game that has AI based on the "conventional" way that would be willing to let me write my own AI controller using NN's? Obviously you will take all credit for the game, all im looking to achieve is a set of results to compare and evaluate for my project.

Robocode. It was practically made for this. Sorry, I haven't read the rest of the thread so I don't know if someone has mentioned it.

Read the README file, below. Most problems are solved there.

The stall you see is due to the GA running in the background. Essentially the visualization only shows the best PacMan for the current generation, and then the GA runs. For each member of the population, it has to run a simulation of the game which takes some time even in the absence of graphical updates and with some extra optimizations.

-Kirk

Quote:
AIPac
Robert Kirk DeLisle
12 Feb 2008

--------------
Plain English:
--------------

The Big Picture
---------------

A neural net controls PacMan's movements through the maze and you can control the types of inputs going into the PacMan. The default version associated with the executable has no ghosts and uses a Window around PacMan with a radius of 4 tiles. This results in four tiles in each direction around him, plus the two tiles in each direction that he occupies, or 4+4+2 (4 to the right, 4 to the left, 2 for PacMan) left/right and up/down. This gives 100 total tiles. I also have the tiles that PacMan covers removed from this set, so you get 96 inputs.

Each tile can have 3 possible inputs - 1 for ghosts (-1 if a baddie, 0 if no ghost there, and 1 if a blue one), 1 for a dot/wall (-1 if there's a wall, 0 if nothing there, and 1 if a dot is there), and 1 for a pellet (0 for no pellet, 1 for a pellet). The default version you have has no ghosts (you can control the number of ghosts in the input file), so you have dots/walls and pellets as inputs for each tile. The grand total is now 96 * 2 or 192 inputs.

At each step that PacMan takes, the neural network is evaluated. The net has 4 outputs, one for each direction (up, down, left, right). The output with the highest value gives the direction that PacMan takes.

In the absence of ghosts, the game map is deterministic so yes, PacMan will take the same path when using the same neural network. The ghosts have a strong random component to their movements, so adding these will cause some random variation in PacMan's movement from run to run.

The Neural Nets are evolved using an Evolutionary Computation process. The fitness I'm using is the score that PacMan gets for one run through the maze. The time one run can take is limited (you can also control this in the parameters file). The goal is to maximize the score that PacMan gets.

I've found it most interesting to look at PacMan's navigation early in the process and compare that to what happens after it has run for a while. No surprise that early in the process PacMan's movements are more or less random - often he just drifts one direction or the other, hits a wall, and stops. Then after it has run for a while and his score is over 1000, his behavior is much more interesting. So far the maximum score I've seen (with no ghosts) is about 2600 out of a maximum of 2840.


How to get PacMan to run through the maze
-----------------------------------------

Yes, you can opt to have the PacMan run after each generation using the best neural net thus far. To get this to work, while one of the application's windows is activated (the PacMan game maze is probably the best), press the 'B' key. After the current evolutionary step, PacMan will become active. You can turn it off - go back to having PacMan not run - by pressing the 'B' key again.

BE PATIENT after you press the 'B' key as the evolutionary step will have to complete before PacMan runs and sometimes this will take a while depending on how many inputs you have and how large the population is. Also, if you get impatient and hit the 'B' key a second time, you will end up toggling the display off so you'll be back where you started. Just hit the 'B' key once.



----------------
Original README:
----------------
AIPac was developed in order to examine (play with) evolutionary training of a PacMan controller. I've tried to develop the simulator in as open a form as possible in order to allow modifications to the maze, the graphics, etc. I may no warranty on the quality of the code. I refer to AIPac and PMAI somewhat interchangably, so be forewarned.

The files/distributions are as follows:

AIPac_README.txt - this file


AIPac_win32exe.zip:
This contains just an exectuable with the minimum files necessary to get it to work. The files are:
PMAI.exe - the executable
AIPac.param - a parameters file within which you can control the behavior of the executable. I've tried to make it self-explanatory.
Resources/ - this directory contains the graphics and mazes I used for the simulator. It should be fairly flexible to allow changes, but it may not be intuitive.


AIPac_code_win32.zip
This contains all the code used to develop the application along with the Resources listed above. I used Code::Blocks as my IDE, so I retained the project as-is. My version of Code::Blocks is 4639 which is current as of late 2007. I also used GCC 3.4 to compile the code. I'm certain you can use other IDEs (such as MSVC++), but I've opted for open source.
NEAT/ - This directory contains the code for evolutionary control of neural networks. NEAT is Neuro-Evolution through Augmenting Topologies, developed by Dr. Kenneth Stanley. (http://www.cs.ucf.edu/~kstanley/) This version of NEAT was developed by Mat Buckland of AI-Junkie fame (www.ai-junkie.com) and he has give me permission to include it with my distribution. (Thanks, fup!) I have used his code with minimal modifications, and as a result, it is a bit of a hack, especially CController.cpp file.
Resources/ - same as above. The graphics and maze maps necessary for the executable.
Utilities/ - my collection of programming utility classes used in this project. I tend to use these a lot in my projects.


PM_NoGhosts_9600Gen_2270.wmv
This file shows the best results I've gotten thus far (late March 2007) with no ghosts in the maze, using a windowing method for inputs. In this input method, the neural network inputs consist of a window centered on PacMan and extending 6 tiles in each direction. This gives a 13x13 window of the game board as input. There are 4 outputs, one for each direction. The largest output determines the direction of PacMan's movement.


-------------------
Additional Details:
-------------------

Here are some additional details related to AIPac that might come in useful. I've tried to put the details in the order of interest and those pieces that will get you up and running the fastest.

Remember that the Resource directory needs to be present. This has all the graphics, mazes, etc. needed for the simulator. You can control most (all, I think) of the details of where the various files are found within the parameters files, AIPac.param, but I recommend leaving things as they are until you're familiar with the program.

While the simulator is running, if you press the 'B' key, this will toggle displaying the current best PacMan controller after each generation. Remember that there will be a delay in displaying the best controller due to the fact that generations take a while to process.

Currently, I have the parameters set up for a rather lengthy evolution step. If you want to see some action more quickly, try changing the following parameters in AIPac.param:

Replicates - Typically I have this set to 5 which means that each PacMan controller will be tested 5 times and a measure of performance assessed across the multiples. Set this to a smaller number and things will run faster. The purpose of this is to account for the random nature of the ghosts. If the ghosts are not present, set this to 1 since that type of simulation is deterministic.

PopSize - Obviously, reducing population size will make things faster, although potentially less interesting.

AIType - I have this set to Windowed which defines a window around PacMan, as described in the readme file. Setting this to Global will be a very different type of AI. Specifically, the inputs defined in the section following AIType setting will be used rather than a window around PacMan. This will shrink the number of inputs significantly, but I've found it to be less interesting.

I've tried to be as descriptive as possible in the AIPac.param file. It should be largely self-explanatory.


If there are other questions or comments, please leave a message in the forum.


---------------
Update Details:
---------------


v0.1.5 updates
--------------

Vector-based inputs implemented. Walls are input as a window. Pellet inputs provide a distance and angle to each power pellet, ghost inputs provide distance, angle, and state (-1 = hunting, 1 = blue) to each ghost, dot inputs show distance and angle to the centroid of all remaining dots. All vectors assume PacMan as the origin.

EnforceIntersections was added to the control parameters. If set to 1, PM will only make a directional change at an intersection. If set to 0, PM can change direction at will. There's a bit of a speed up with this as well as enforcing smooth paths.

**Verify proper scoring for dots - the possible maximum score should be 284 dots * 10. (Ghosts and Pellets seem to be OK.)**
I found that at certain intersections mulitple dots are removed simultaneously due to a perceived overlap of the bounding box and dot tiles, but only one produced a score. A modification was made to count how many dots are removed for any particular PacMan location and the score adjusted appropriately. MapController::ModifyTileByPixel

The visualization delay was linked to the parameters file. Larger numbers cause the visualization to run more slowly so that it is easier to watch. This does not affect the actual GA portion, just the visual of PacMan running through the maze. The same delay is linked to the playable mode option.

A user playable option is now available. The parameter Mode can be set to Evolve to run an evolutionary simulation, or to Play for a Keyboard playable version. Use the arrow keys to move PacMan around the maze. All the other options remain the same.

**Fix the gate on the ghost cage - it doesn't redisplay and it may not be reset.**
A forced redraw of the entire maze was implemented any time the gate is opened or closed. This does not appear to slow the process whatsoever and in fact I can force a redraw at every frame without any noticable performance losses. This is a much easier fix than to implement specific drawing and erasing of the gate, or modification of the maze graphics.



v0.1.4 Updates
--------------

A few bugs were fixed. Specifically, some issues with whether PowerPellets and Ghosts were visible or not were addressed.

The ability to ignore walls or dots was added to the Windowed AI. In the parameters file the following keywords control this as follows:

DotWallSingleInput - If set to 1, the input will be -1 for a wall, 0 if empty, and 1 for a dot. If set to 0, there will be two sets of inputs - one for dots one for walls.

DotsWallsOnly - If set to 0, both dots and walls will be used for inputs. If set to -1, only the walls will be seen. If set to 1, only the dots will be seen.



v0.1.3 UPDATES:
---------------

Windows now update during the evolution step thus preventing an freezing of the application during one epoch.

The console window now tells you whether PacMan will run or not after the current epoch and has (almost) instant feedback from pressing 'B'.

Small optimizations to speed up the simulation.

Ghosts now allowed to reevaluate their direction after PacMan eats PowerPellet. Hopefully this will discourage chance collisions forcing PacMan to be more active in pursuit.

When the console window was running a spontaneous crash would occur the seemed to stem from the Windows message queue. A DoEvents() function was implemented to allow window events to be processed while the Console was active. This seems to have solved the problem.