AI and Gaming

Hi,
It seems everyone is learning to program 3D graphics. However, very, very few folks are interested in program artificial intelligence into their games. Those that do seem to be avid C++ or other language programmers. Very few seem to be using VB.

I have been programming a long time and have been fascinated with AI concepts. Has anyone on this forum spent any time modeling/programming AI with VB?

Specifically, do you have 'agents' in your game(s) that start off not knowing a whole lot about your (player's) strategy, but over the course of the game it learns, shares knowledge with other agents to give you a better challenge as the game progresses?

The game can be graphically simple, such as 2D, text mode, etc. I am interested in discussing concepts and some applications of theory.

Regards

AI is a very language independant topic. The reason you will find most complex AI systems written in C++ is because, well, its complex. That level of AI takes a LOT of processing power, and using VB would make it run even slower. You can program complex 3D games in VB, because it is simply linking to a C++/assembly object, which is fast to begin with, and you have powerful GPUs running around that dont care how fast VB is. But, when it comes to AI, its all being done on the main processor, and taking up CPU time, which is one of VB's worst areas. Its just too slow to handle the amount of calculation needed for game AI.

Im not going to say that you cannot program AI in VB. VB is quite capable of doing any AI system that you can dream up. It may or may not be capable of doing it at an acceptable speed.

My suggestion to you is to learn to read some C++, so that you can follow the code examples that you find, and learn the algorithms presented (http://www.aidepot.com/ should be a great help), and then implement them in VB.

Z.

Hi Z,
Thanks for the link. I will look. Programming C++ not a problem. VB of course is just a preference. Besides, I think VB is far more capable then folks make of it. For example:

Z, here is a simple but challenging program for a VBer.

1. Write a tic tac toe program human vs. PC.
2. DO NOT hardcode program to play the game.
3. Provide data logging of all moves (determine encoding).
4. Give program desire to win or at least tie...but let it be miserable for losing.
5. Program framework for studying patterns of what wins, ties and loses a game. Write the code for the PC to learn...just like teaching my children to play chess. After literally hundreds of games, they are able to play good competive chess.
6. So, the more games the human plays against the PC, the smarter the program becomes until it learns to tie.

This is what I mean by AI. VB is more than capable of this at lightning speeds.

Now, the above AI engine, once complete, can serve as a catalyst for implementing AI for VB 3D games.

If I figure this problem above out I will share it. If anyone has ideas on how to implement step 5 above please share it.

Regards,
Chuck

The way I would go about solving this problem would be to use the standard game tree that is used during most Tic Tac Toe games. Basically, for each move, there are n number of children for a node, where n is the number of empty spaces on the board. You use an evaluation function of each possible next move for the computer, and select the one that is most likely to result in a win. The way I would solve the problem, then, would be to have the computer play x number of completly random games against itself. It would store these games, in a string:

Code:

---

x2o1x0o3x6o8x5o4x7

---

where each cell in the board has an index, 0..8. I would then analyze these results (in code, of course), that would construct almost a database to use when solving for the next move during the game.

This would give the computer an intelligence. TO make the computer learn as it plays agaisnt the player, just skip the first step (the random games), and have the computer play at random until it can build its database.

Z.

Hi Z,
I appreciate your thoughts on the matter. I understand your approach is to work towards a win from the starting point. I am interested in working backwards. Allow me to enhance the concept.

The AIProgram will not know what a win or loss is. It knows only when it is it's turn and whether it will play X or O. The human player, after winning against AIP, must tell the program the status: win, loss or tie. All the AIP has in its history file are two things:
1. A 9 square image pattern of each move in a game.
2. The winning pattern in which the human indicates that human is winner by virtue of X's in the 1st column (for example).

At this point, the AIP sees this as a desired pattern to achieve. However, the human plays other games and the results are that there are 8 possible ways to win. Now as you suggest, the AIP initially selects moves randomly until it begans to accumulate useful data.

At this point AIP knows the results to win, but must derive preceding patterns that lead to a win...I think 34 or 26 possible 2nd to last moves that could lead to a next move win.

The AIP must then investigate all moves prior to the last move to see what patterns led up to final win. It searches through database for all pattern combinations. It tries to predict successful preceding patterns of play.

Eventually the program, by playing 100 games with the human, works out all first initial moves that could lead to a tie or win.
It's database will eventually yield two components. 1) History file and 2) Rules for winning file.

Now imagine a variable representing state of happiness. Each time the human wins, the AIP gets sad. Its motivating goal is to be happy which is connected to its win/tie/loss record. The result is that the program is quite content with a tie instead of a loss.

The end result is a program that my children can teach to play tic-tac-toe...much the same as we teach our younger children.

Let me know if this too much rambling and I will stop. My goal of course is to write such a program eventually. You know, it is not a difficult thing for me to write code to crunch lots of data and place it into databases or flat-text files, manipulate 2D/3D graphics. But, making the PC almost human is for me the most difficult thing and therefore the 'holy grail' of my programming pursuits.

Remember the computer program that beat the world's best chess player a few years ago? The problem is that it could not play tic-tac-toe. It did not have the framework to learn.

I would like to create variations of tic-tac-toe by having the human define a different winning goal such as getting X's on 4 corners. The AIP then has the framework to play another game without any coding changes.

Evenutually, it would be interesting to write a program that couple play checkers, tic-tac-toe, connect 4, etc without knowing how to do...but yet capable of learning from a human teacher.

Thanks again for your input and that of anyone else.

Regards,
Chuck

The way computers beat humans these days is because they use a move tree, like the one i described above. The computer looks down as many paths as it can in a certain amount of time, and chooses the next best move. There isnt much intelligence in it at all.

In your case, with the tic tac toe, here is my suggestion. What you can do is, in teach mode, after each player move, you answer a question. The question is "Is this a Win, Tie, Loss, or is the game not over?". As long as the game is not over, continue to play. After each computer move, it also asks the question of the player, and play repeats as long as the game is not over. By playing this type of game, the database could be constructed, and the computer would eventually mimic winning and tieing moves, as well as avoid losing moves.

Z.

Hi Z,
I am familar with the move tree approach. I was concerned about telling the code too much about the tic-tac-toe game. I have written chess, checker and tic-tac-toe programs that played legal games...they weren't the best at winning. However, I coded the games into the program so it wasn't AI.

Pertaining to your suggestion, I think this is good. I had figured on the human telling the program only after a win, tie or loss occurred..whether it was by human or by the program unintentionally...instead of each play. But that is probably more in line with how a child learns a game.

I have worked out some other details. The center block produces up to 4 wins, the corners 3 and the remaining only 2 wins. So the program naturally needs to identify common elements in various patterns that produce a higher probability of winning.

To aid in working this out I considered a 2D grid that is adjustable from 3X3 to 5x5. This would allow user to invent knew games. The program should work with all of these games and learn to beat or tie the human.

For example: I tell computer of a new game, give it a name and set the grid size...say 5x5. I identify the symbols and who goes first. Let's say a win is a block (2x2) pattern anywhere within the larger grid. Each time human makes a block pattern it tells program human has won. Immediately after winning the 1st game, the program tries the same 'absolute' location of the 2x2 pattern. The human blocks the pattern and wins elsewhere.

The program then 'sees' that the absolute location of 2x2 is not so important but rather the relative placement of a 2x2 is just as valid. The program then tries to make a 2x2 at random locations. However, it must also track the human player.

By considering this while working the tic-tac-toe problem allowed my a lot of insight into that prevents me from biasing my code to play just tic-tac-toe.

Z, I appreciate your thoughts on the matter. I was hoping to find some useful exchange of data on the internet that was not mind-blowing and not too shallow. Let me know if you get tired of this discussion.

I want to write this program so my children can 'teach' the computer new games that they make up. Kind of a novel idea I suppose. I want to expand upon the program's capability to learn more complex 2D arrangements and plays such as checkers, more than 2 symbols, different shapes then a square inside a grid, etc. Eventually I would like to code the framework so I can teach the program to play chess in a few hours and after hundreds of games with the family the program begins to stalemate or even win.

I hope to get some time from teaching in the next few weeks and this project has become a goal. I will find time within the week to design the interface and build basic functions.

Regards,
Chuck

A very noble goal, Chuck.

A couple of things occur to me. The more complicated the game (the bigger the board for example) the longer it will take to teach the program. Using a random base for learning means that it will make stupid mistakes for many, many games before it learns. The program also needs to record win conditions for a number of games - if the game was played on a Os & Xs board but the win condition was all four corners, the game would need to know how this was different from tictactoe.

I don't really know where I'm going with this post...

Will the program carry its tactics over from one type of game to another, or will it have to be taught like a baby each time new rules are applied?

Hi Behemoth,
My first goal of course is to write my first 'no kidding' AI program that does not require hard-coding of game specific stuff.

Regarding time to teach...that may actually be shorter then you think. You see, if the game is to create a block 2x2 pattern to win, the program will try playing the same positions on the very next game. Of course, the human will play a 2x2 elsewhere. Here is where AI reasons...it must see that the 2x2 pattern worked in two different positions. So, on the third game, it will try to create a 2x2 at a random location. This aspect pattern recognition my be hard coded just like the human brain is the best machine for seeing most patterns.

Since I hope to experiment with the program it will allow one to continue developing over time against various human players or allow the human to start the teaching over. An archive of 'personalities' and 'strategies' will be saved so they can all be opened and continued upon.

You have a great point about 'cross-game' learning...applying strategy from one game to bleed over into learning new game.

Let me think about that...

Regards,
Chuck

well since I am interested in that stuff I hope you will succeed... I am interested in some basic game intelligence too
that is why I clicked the AI-Depot link and it did not work...
Here's what I found:
http://ai-depot.com/GameAI/

I guess this one is more relevant:
http://ai-depot.com/Main.html

I picked up Artificial Intelligence: A New Synthesis (Nils J. Nilsson), ISBN 1-55860-467-7 a few days ago, and, though it is a bit heavy on the maths, it seems to be a very good book for AI. It is specifically geared towards Agent Based AI, so it would not be very good for say, a board game, but for games with individuals and such, it fits perfectly.

Z.

how bad is the math? I am really interested, but I don't feel like buying a book where I don't understand anything and get frustrated by looking at it....

Hi,
I spent considerable time over the past week working on some needed concepts and modeling for this program idea. Managed to get my wife to listen for a half an hour as I explained the concept. She is a teacher so she was somewhat interested.

As the human tells the program that a 'win' has just occured, a string of text is written to a data file such as:

ABS(1,1);(2,1);(3,1)=1

These are absolute cell locations within a 3x3 grid..if tic tac toe, then this is a win in first column. The '=1' means this resulted in one win.

The next game, the program will try to play the exact pattern recorded above. Let's say human blocks and wins by playing third column. This is written to data file as:

ABS(1,3);(2,3);(3,3)=1

The program, once it has two or more absolute win patterns is hardcoded to look for similarities that I call relative patterns. Since both wins above are vertical, 3 blocks long, then they are the same pattern. The program generates this string:

REL(0,0);(1,0);(2,0)=2

The '=2' means this pattern has already resulted in two wins.

The program can also be coded to compare various REL patterns. For example, in a 2D grid, patterns can be rotated 90, 180 and 270 degrees.

In addition to this, each element is tracked for its contributions to wins. I call these elements. For example:

ELE(1,1)=1
ELE(2,1)=1, etc.

This is relevent after several games in which the center block of the tic tac toe board can have a high number because it intersects 4 possible wins.

I have created about 20 more strings to enable the program to play checkers and chess. I need to do more thinking regarding hardcoding the program to play chess.

The programming to all of this seems actually pretty easy. My human interface window (for playing games and teaching program) uses a MSFlexGrid. I hope to type my string or AI code set into a DOC and will post it if anyone is interested. I will begin coding once I figure out exactly where I am going in the very near future.

Z, this AI model I have been working on does very well with patterns and pattern recognition. I am fairly certain that human behavior in game playing can be collected and saved as a pattern of some kind. If so, then this model may actually work without two great headaches for most people: 1) complex algorithms and 2) complex math. Again, this is a theory that must be put to the test.

Will someone out there describe briefly a human behavior in a particular game that would be useful for an 'agent' to learn and thus alter its strategy or approach? Or "how do two humans play the same game differently?" would be a good start. The goal is to think of someway of converting human game playing behavior to a binary bit/byte pattern.

Regards,

Quote:

---

Originally posted by ChuckB
Will someone out there describe briefly a human behavior in a particular game that would be useful for an 'agent' to learn and thus alter its strategy or approach?

---

In O's & X's, if a player sees that they can create 2 chances of winning in one go, they will choose that position, so that they are guaranteed a win. Perhaps you could build in some sort of algorithm that checks for whether this is about to happen, or if they get the opportunity.


E.g. It's the computer's (X) go,

-O-
-XO
-X-

It should recognise that if it went bottom-left (or bottom right) it would win on it's next go. Perhaps this is the sort of thing that wouldn't be too hard to implement.


BTW: Although i have very little knowledge if AI, i would be very interested to see the results.

Chuck... seems to be coming along nicely. Good work!

Misan: Most of the math involved is actually in the training of neural networks (these would help you in your current problem, Chuck). There is also a lot of boolean algebra involved. Beyond that, even without the math, the concepts are quite easy to grasp.

Z.

Hi,
I have written Part 1 to a 5 page Word doc (ZIP Attachment) that explains in more detail my proposed AI Model. It covers no math and no complex concepts. It is relatively simple.

For the AI model to truly simulate human learning and intelligence it cannot have any hard-coding to play tic-tac-toe. It must have the capacity to play. It must also be capable of learning more complex games using the same AI Engine. I hope to cover that in Part 2...a more complex game using the same model with the addition of more scripting.

I hope some of you will read this and feedback your thoughts on the matter.

Thanks Z.
SLH, I address your ideas to some degree in the attachment.

Regards,

It looks good, Chuck, but a few things that you need to address.

Although the current overview is great for games in which you place pieces (Tic Tac Toe, Connect 4, etc), How does your algorithm extend to encompass games in which pieces start in certain locations, and are then moved? For instance, in a game of chess, it is perfectly feasible that every square will be visited, but that doesnt mean that every square contributed to a win. How would you determine what contributed to a win? How to represent certain strategies? Pattern matching could still be a valuable tool, but you would first have to work out a method that chooses which patterns are good in what situations.

Youve got a great start, but there is still a lot of work to do =).

Z.

Hi Z,
Great questions that deserve well-thought out answers. Let me put forth some other concepts then I will try the chess questions you ask. I am making one assumption. If I can derive a clean scripting language that can be encoded/decoded I assume I can write the modules required to parse the script and feed to the AI Engine. If not I know that there are brillant programmers out there that can help me out with this.

So, if we can describe all aspects of several types of games with a scripting language, I feel comfortable we can write the code. :-)

Let's talk checkers. I can describe all game pieces on the board as 1 of 4 types. Black piece and black king, red piece and red king. Each of these pieces have a prescribed manner of play. Consider this:

SYM(1)="B"|MOV(0,0);(-1,1)|MOV(0,0);(-1,-1)| ....
JMP(0,0);(-2,2)|JMP(0,0);(-2,-2)

This is symbol 1 which is one of 12 black pieces. MOV are moves from current position relative (0,0) to another relative position. I assume black pieces are at the bottom of the board...red on top. JMP are jumps which refer to how it moves to captures pieces.

ORG(9) = SYM(1)|IPO(6,1)

I am trying to be creative...ORG is organism number 9 which is a black piece. IPO is initial position at row 6, col 1. We define from the human interface panel in teaching mode all 24 organisms.

A chess knight or piece can be described as above. Some syntax consideration is required for a pawn which can move 1 or 2 from it's starting position.

The actual game board must be defined and saved to the database for the AI Engine to process. Consider the checker board.

UNI(1,1);(8,8)|NOT(1,1)|NOT(1,3)|NOT(1,5)|NOT(1,7)|NOT(2,2)....
etc.

UNI is universe (more creativity) defining the grid. The NOT keywords identify elements or cells within the grid that are not played. So, there will be 32 not statements to identify the 32 squares not played in checkers.

The above script can be used to describe a chess board, it's pieces and movements. Other details can be added such as weighting for piece values...but I would argue that this is something the AI Program should figure out on it's own.

Continue checkers.

A black piece advancing to top row changes to a black king so...

TRA SYM(1);SYM(2)

Means symbol 1 transforms to symbol 2.

Now, the real task is to identify several different board games that utilize grids. Then create a robust scripting language to describe all aspects of game behavior so that we can play an entire game on paper simply by writing the scripting language.

However, my immediate task is to produce a v0.1 game to handle simple pattern recognition games such as tic tac toe up to 5x5. Once this is working, program v0.2, for example, to play connect 4 which has pieces dropping in from the top and dropping down due to gravity.

Chess. The AI Program will be able to learn the boundaries to the chess world, allowable play for each of its pieces pretty quick as the human teaches it. This session can be an hour or so.

The program can now play legal chess, which incidently does not require any hard-coding. I have written a basic chess program before and it took me a lot more than an hour to get it to play legal chess. Legal I mean it does not cheat.

When the human defines a win, it is not as a result of a 'pattern' per se but due to a capture.

CAP SYM(15);SYM(8)=1

Capture of symbol 15 (king) by 8 (opposing queen) results in 1 win. Position of pieces will also be stored.

Game plays again, this time human takes king with a knight.

CAP SYM(15,);SYM(6)=1

Chess and checkers are different from tic tac toe and connect 4 because one starts with a board full of piecs and the other starts with none. So, this may be cheating, be we define game type as 1 or 2 respectively.

GAMETYPE=1

The human tells the AI Program what type of game it is...in this case the 1 means board loaded with pieces.

Now, each piece's movement history can be tracked. For capture type games, AI program can be made to study moves made prior to a capture so it can replicate these moves.

This is a superficial response to your chess questions but it must be sufficient for now.

Z, I will give this more thought.

Regards,

Another method of teaching could be to use an ALLOW statement. For instance, the first time with chess, the player moves a pawn. This is a legal move, and thus, a new ALLOW statement is placed in the database:

ALLOW(1,0,1)

Basically, allow organisms of type 1 to move in an upward direction. The computer then mimics that move. As each combination of moves is played, it goes into the computers database. You could also try rating pieces, so that the computer can make intelligent descisions on what pieces to capture (or it could learn piece worth, based on captures).

As to the scripting, you need equation trees. Basically this is a tree where all non-leaf nodes are operators, and all leaf nodes are values used as inputs to their parent operators:

http://www.vbforums.com/attachment.p...postid=1042817

This would help greatly in parsing out your data files.

Z.

One problem you may encounter when teaching games such as chess, is how to get it to realize that it can only move it's pieces, and that the rules for moving it's pieces are slightly different from moving yours (pawns starting at the top move down, ones at the bottom move up). To counter this as one method of teaching you could allow 2 players to play against each other, an have the computer learn that way. This may also be faster, as people have a statagy to start with, which the computer may be able to adopt.

SLH,
When I taught my young children to play chess there were certain things I instructed them on. I showed them how pawns, the king and queen moved. I told them they played either white or black. So, I think it is appropriate to have a command that indicates what color or symbol type the program controls.

Incidently, we did not use rooks, bishops or knights. I introduced them over a 2-3 week period as they got the basics down.

Program observes 2 persons playing? That's possible and something I hadn't considered.

Z,
Your graphics on the decision tree really made sense. Funny how words can be confusing. I am now thinking of the parsing module that will place the scripting language from the database into arrays and variables during startup. For example:

UNI(1,1);(3,3)

When the line above is read by the Decoder it would result in an array be created such as:

0,0,0
0,0,0
0,0,0

Could you provide a simple example of how the decision tree might be incorporated to parse and gain info from a sample scripting string? I would appreciate it. Nothing too complex as I am sure you are busy enough with things.

Regards,

Beware: Recursion Ahead! =)


Ok, We will use the UNI() operator. Our tree would look like this:

Code:

---

      UNI
    /      \
  3        3

---

Our script parser knows about certain operators, and UNI is in that set. We then define a function that creates the universe:

Code:

---

Public Universe() As Long

...

Public Sub operator_UNI(SizeX as Long, SizeY As Long)
  Redim Universe(SizeX* SizeY)
End Sub

Public Function ParseTree(Root As clsNode) As VALUE ' change value to a real data type
  If Root.Left = Nothing And Root.Right = Nothing Then ' Leaf
    ParseTree = Root.Data
    Exit Sub
  Else
  Dim l as VALUE
  Dim r as VALUE

  l = ParseTree(Root.Left)
  r = ParseTree(Root.right)

  If Root.Data = "UNI" Then
    operator_UNI(l, r)
  End If
End Function

---

There is a basic framework. You will have to implement The code to get the operator tree going yourself. The implementation for clsNode is simple:

Code:

---

Public Left as clsNode
Public Right as clsNode

Public Data as Long

---

Basically, You parse the script into the tree structure, so that you end up with a root node (no parent). You just pass that root node into the ParseTree function. For each operator, you need to add code similar to the "If Root.Data = "UNI" Then" code. That should get you started.

Z.

PS: All code untested, though it should work, as long as you change VALUE to something like Long

Z,
I have read your last post several times. It is beginning to make some sense. I picked up a C programming book for $1 that explains much of what you are describing. However, the MIT author has had great difficulty talking to me at my level...and there is no math. ;-)

Today, after students left, I devoted 5 hours to AIP v0.1. The program is working well so far. I have preprogrammed a combo box with winning patterns described by ABS(1,1);(2,1)=1, etc. I use a 4x4 array. The user selects a winning pattern and the MSFlexGrid updates. The user can then accept the win and send it to AI Engine. The engine of course will compare this new absolute win script with all previous entries and develop appropriate REL patterns that match. That is goal number 1. I hope to be done with this early next week. I will post it then.

The next goal is to program the thought process of program by which it evaluates possible game play and makes decision based upon learned knowledge. By working with 4x4, I should be able to run the same program with a 3X3 and spend a few minutes playing it. I believe it will be playing good strategy after just a few games.

Now, I believe your ParseTree is supposed to take text format like ABS above and pull grid data out of it. Is that right? If so, I am going to stick with my technique for parsing until I get a hold on ParseTree.

Regards

In an earlier post on this same thread, Chuck mentions checkers (posted 6/11) and his NOT keywords, specifically the 32 squares that are not playable on a checker board.

I know this idea is a bit extreme but it might be thought provoking :-

If the goal of your program is to "learn" to win at checkers (or any other game), is it too far removed to enable it to also learn the rules of the game?

If you presented the computer with a checkerboard and three neatly lined rows of checkers and asked it to move any checker to any square on the board, and was then rebuked by the human player when it made an illegal move, wouldn't the computer quickly build a set of legal and illegal moves, from which it could establish a pattern, and thereby learn the rules of the game?

This is certainly extreme, as it may take many inane and arbitrary random moves before the computer "fluked" enough legal moves to establish a pattern. Watching two human players can accelerate its rule learning as it would develop a wealth of legal moves, instead of illegal moves that random choices will inevitably produce.

But think of the benefits. If the program had this ability, you are not only avoiding the hard-coding of the game "rules", but you are also providing the means for the computer to learn other games.

In fact, the computer could learn to play any game that involved a checkerboard of any size and any number of pieces that behave in any manner, including chess pieces.

Of course, I wouldn't want to be the "trainer" that sits through all those initial mundane illegal moves. And this would certainly shift focus from finding a winning strategy to learning to play the game which are arguably different goals.

Initial discussions mention the question the computer would ask are :-

"Is this a Win, Tie, Loss, or is the game not over?"

Is it that much harder to include :- "Is this move legal?"

I presented that learning method in my third or fourth post in this thread =). It seems perfectly viable, but shifts the focus to learning the rules instead of winning. At the moment, the system has a rule set to work with, and tries to analyze past games to find winning strategies.

Z.

Hey, I know this means a lot of re-working, but since it has to learn patterns, wouldn't it be a lot simplier to just use a neural network (and of course save the state of the neurons instead of a history of all the previous moves)? That's what NNs are for. They'll keep a lot of information in a relatively small space, and use it to make decisions (like our brain :D ).

I think that the game should have 2 steps, one where it learns the rules and another one where it plays and learns how to win.

In the first step you'd teach the rules like this: the NN will do some random moves, and based on the simple rules (maybe in a script or something?) it would know which ones it can do and which ones it can't. That would be a great help since you wouldn't waste your time teaching it the basic rules by training it (it would be like teaching someone the rules before actually playing, by telling him/her the rules instead of having it make a lot of moves and saying "yes" and "no").

The second step would be the actual game, the NN would happily make some random but legal moves, and its goal would be to win (of course that it would be taught the conditions of winning in the first step, so for example in chess it would try to place one of its pieces on top of the king instead of doing random moves and after 1000 games it would win because of ONE of the many conditions and say "oh, i won?!" :) ). It would not only learn from its moves but also the other player's moves (this should be obvious but if you don't do it it really makes a difference).

Oh well this is only my opinion. If you don't wanna do it like this it's ok, but I think you'd end up having to train your program a lot more than what you want to ;)

Hi,
Mental gymastics at its finest trying to sort out the scope and depth of AI for something simple like tic-tac-toe and checkers....which is a lot more challenging then it might seem on the surface.

I have engaged my children and wife during the past 2 weeks at all sorts of these games we have been discussing. I have been paying attention to their level of play, mistakes, my correction and their response.

Clearly a 3 year-old learns differently than a 6 year-old. In fact, the 6 year-old is very good at learning a simple game when you specify the following:

1. Gameboard setup
2. Identify pieces that belong to them and yourself.
3. Moves that can be made.
4. Who goes first.

With experience they can then learn the following additional concepts:

1. Capturing opponent pieces.
2. Blocking opponent's play.
3. Transforming pieces (pawn to a queen in chess, making Kings in checkers).

So, I think it reasonable to define an entry level vocabulary that the AI Engine will understand such as the 4 items in the first list above...a six-year old mentality as an estimate.

Long teaching sessions? No problem, my younger children would be delighted to sit in front of the computer teaching it to play tic-tac-toe or checkers. I would get a tremendous amount of satisfaction playing the computer after it has been taught and seeing that it is making a definite effort to play a challenging game.

So, I am still committed to getting this AI program to play a simple game before I take on checkers. I have spent a lot of time writing various functions. In fact I was inspired in Church Sunday and managed to write four functions during the sermon that managed the bit pattern representing the game board. I had heard the message before. :-)

Neural networks, weighting, inputs, teaching, etc....lot's of work in my opinion not to mention that I have no clue on how to simulate a NN on my Pentium 4. However, I have read some simple material on NN and it does sound interesting.

I appreciate the input on this posting. Lots of smart people out there forcing me to think this concept through.

The big, big flick is this. I am really interested in Natural Language Processing (text based for now). Lots of work out there already. But not one system can you talk to and eventually say, Can I teach you to play chess or Monopoly or Risk, etc. Can you show me how to solve this math problem? Can I teach you to program in C++? My thought is to develop the game playing capability so the AI knows patterns, 2D, 3D concepts. Add time comprehension to the gaming with some math problem solving skills. Then add a module for NLP (basic at first), etc.

Of course, I must start small...tic-tac-toe learning capable program 1st.
Regards,

Chuck, take a look through the book I posted above, if you can find it in a bookstore somewhere. Youll find it fascinating.

I think, once I get my computer back together, and finish up some work that needs doing on TOW, I am going to take a good look at NN and Genetic Training methods, and see if I cant get them to play tic tac toe, and maybe chess =).

Z.

Hi Z,
Remember to document your code very carefully so when you are completed with your Genetic Training methods in VB you can post the code and we can all learn...or copy and reuse w/o learning.:-)

I'll look for book this week. My wife and I leave children weekly to go on date to Barnes & Noble (that's what us old people do for fun) to read for free and drink strong coffee. ;-)

I got that used book for $1 that explains binary searches using C and other techniques. I have been reading that. Also downloaded DevC++ (easiest C++ compiler in the world to install and use) and tutorials from gametutorials.com (for DevC++). Taught myself crash course in C++ so I can understand all of the stuff available out there.

AI Program in VB going well. Interface is complete with grid size selectable, who goes first, what symbols to use, their assigned numerical values, etc. I'll leave color squares out for now. Expanding upon initial language set (i.e. GAME.GOFIRST=, GAME.GRIDSIZE( x,y), GAME.PROGRAM_WINS=).

Writing needed functions for manipulating and crunching bit patterns. I am planning on 32 bit long integer to store status of 3x3 (9), 4x4(16), 5x5(25). One long glProgram stores bit pattern of all X's, glTeacher stores bit patterns of O's, glGridUsed stores bit patterns of all used cells, etc.

I will experiment today with writting a simple DLL with DevC++. Then try to use it with VB. If works, then I can convert many subs/functions to DLL for speed. I did this a few years ago to create an INP/OUT for reading PC ports in VB...so I can program temperature monitoring system at my plant.

What is TOW? I think of an army smart weapon.

Regards,

Sure thing =). Ill make it as impossible to copy and paste as possible =).

I got my copy at B&N, so you should have some luck. It may be a bit more expensive then Amazon, but the atmosphere is unbeatable =).

MS Visual C++ is the best Compiler/IDE availible for Windows, say 9/10 programmers, so if you can find a copy for cheap, its a great investment. MSDN is also the most helpful set of help files Ive ever used =).

Looks like you are making progress with the Actual Deal™, Great job!

If you need any help with C++ junk, youll find tons of help down in the C/C++ forum here. I frequent that forum as well =).

Times of War (TOW) is the game I am currently working on. You can take a look down in the Communications Area Forum here =).

Z.

Hi Z,
Made it to B&N. Didn't find your book but looked through a text "3D Game Engine Design" by David Eberly. Full of math and a lot of C/C++ sample codes...focused upon practical...still over my head. I finished CalcIII 5 years ago. Need a refresher though, especially with linear math and vectors.

However, I read a considerable amount of "The Zen of Direct3D Game Programming" by Peter Walsh. That took me all the way through necessary windows programming with VC++. I resisted buying it though in order to finish the tutorials from Gametutorials.com.

I have made great strides this week writing console apps in VC++ and DevC++. I can move my text guy move through a maze with the cursor key. Lots of big picture C stuff getting sorted out in my head. I even built my first class. I'll be ready to try DirectX stuff soon.

Your binary search tree above and recursive behavior is making much more sense now. I am now coding the actual decision making in my AI Program. I need a smooth way for the game engine to digest various game types and rules to run them through one nice process. Very close with the process.

Regards,

I have 3D Game Engine Design, and it is exactly as you've described it =). Actually, once you get through the first few chapters (the ones with the REALLY heavy math), there are lots of good ideas. Overall, it is a good book to have around.

I never took a look though the Zen book, and Im not sure how far it takes you into D3D (it's version 8, right?). Depending on your internet connection, I would recommend downloading the DX8 SDK from the MS web site. Once you have that, the tutorials at http://www.directx4vb.com are the best I have ever seen, in VB or C++. The really good part is that once you have the basics down, its quite easy to move all of that VB code into C++ =). I havent done VB DX stuff in quite a long time =).

Just to set the record straight (and to keep you on track =), my tree above is NOT a binary search tree. Search trees are ordered, while mine is un ordered. A real BSP would look something like this:

Code:

---


        10
      /    \
    4        14
    /  \        \
  1      5      16

---

Youll notice that all nodes on the left of the parent node are less then the value of the parent, and the nodes on the right are greater. In this manner, you can search through the tree by determining if the current node is greater then or less then the value you want, and go the correct direction, thus reducing search time.

I think I am rambling, and I know that I am a bit off topic =).

I cant wait to see what you come up with for the rule-set parsing. I think the most important thing is modularity, so youll need to make sure that you have enough statements to allow you to describe just about any game to the computer, and it would learn to play with that.

Anyway, signing off =).

Z.

Hi,

The terminology still messes with me...but I understand the concepts. I found good literature on Linked Lists which explains in detail with sample code (VB,C) how to make it work.

I am focused upon completing the code to play tic-tac-toe...of course, the program will not know how to play, but because of it's innate (programmed) ability to see and manipulate patterns and becauses it knows very basic game rules, it will learn and eventually tie the human...so I hope.

All coding is based upon the grid size, so by resizing and establishing a new game, the code should all work...4x4, 5x5, etc.

Now, the AIP will be limited by one game type...that is, you start out with an empty grid, alternately placing one piece at a time down until a specific pattern or patterns are created for a win. The code should handle this.

The engine will then have to be upgraded to accomodate the possibility of learning checkers which will constitute another game type.

Here is a sample database file (flat database text) that stores info from playing several games.

'**********************************
'LEARNING.TXT
'Date: June 22, 2002
'Time: 11:35 pm
'**********************************

'system variables
GAME.NAME=TIC-TAC-TOE
GAME.ROWS=3
GAME.COLS=3
GAME.TEACHER.SYMBOL=O
GAME.TEACHER.VALUE=1
GAME.PROGRAM.SYMBOL=X
GAME.PROGRAM.VALUE=2
GAME.GOFIRST=1

'win-loss history
GAME.PROGRAM.WIN=2
GAME.PROGRAM.LOSS=4
GAME.PROGRAM.TIE=6

'winning patterns
ABS(1,1);(2,2);(3,3)=2
ABS(1,2);(2,2);(3,2)=1
ABS(3,1);(3,2);(3,3)=1

The program will open or create this file. Upon loading the file, it places ABS data into a user defined array, and then begins thinking about similarities to create a REL array full of possibilities. It's brain evaluates several possible plays that will produce a win or block down the road. I have scaled down upon the AI Language in order to get this functioning first.

Once complete, there should be a single SUB that does the AI thinking and decision making for making a move. This will be the module to improve upon in case I do something sloppy.

How is the pattern stored? I am using a 32-bit long variable type to hold the info...lots of bit manipulation. But this allows for easy pattern matching.

You know, everyone starts a program with great expectations. However, most of us never finish what we start. So, I appreciate the programmers at this site and their encouragement. If I don't finish I am just a bunch of hot air...;-)

Regards,

Looking good Chuck! Keep going like this, and you are well on your way to finishing =).

Z.

Hi Z,
The AIP is getting closer and closer. Took break tonight to grade lessons and pay bills (they never stop). I wrote a tightly coded VB app for "Hangman" in response to a question posted in this forum. It felt good to start/finish a program so quickly. The AIP workout has got my brain working again.

Z, You can take a look at my style and conventions in that small app. It is under Hangman. There is a cool bug...I am not sure how to fix it. I added a button that gives simple instructions on recreating...it is cool though.

I have been tempted to post 'screenshots' of my AIP program...but that I think is the kiss of death. Lots of links out their with screenshots from incomplete games made over a year ago with no recent updates. Maybe be a curse. ;-)

Here is a debug tip for beta testing your TOW...Maybe you have something already. Normally beta testing only results in a small number of users testing your app. The problem is that the final release will most likely contain bugs....generally lots of them that show up over time on different systems with different people. So...

A couple of years ago I added an Error module that logs errors to a file. I insert lines into each sub or function....along with some markers indicating code position. Then when a customer/user runs program and it bugs out...the data is recorded objectively. Often the customer/user can call me..I direct them to open errorlog.txt and the data tells me what line errored out. I like to dump key system/program variables to the file to aid me in debugging. Looking at the source code with customer/user on phone and I can tell them the fix (generally something other than my code..i.e. network mapping, file attributes, corrupt data entry, etc.) If you are interested let me know and I can send error mod with explanation.

I have incorporated another feature in the AIP. There is a button that allows all global variables to be displayed in text box while program is waiting. Additional buttons exist to dump current AI knowledge and the initial loaded file to the same box.

Grid ops with mouse are complete. I must complete pattern manipulation routines, saving data and AI decision making. For decision making I am going to use the number of wins per pattern (absolute or relative) and individual cell wins for weighting...a tight control loop for playing/blocking must be completed as well.

Enough tonight. If you can find the fix to my Hangman bug please let me know. Instead of fixing it I highlighted it to make people think I knew the answer...ha! You can do that in TOW maybe. ;-)

Regards,
Chuck

Well, I had a reply to this last night, but it never got posted...

Anyway, I will take a look at the hangman thing and see what I can do. As to the error logging module, since the game and engine are both C++, I cant use it =(. Currently, I have a system that works like a stack trace that is displayed when an error occurs, and it works quite well. Thanks for the offer though =). The other thing I have going for me is, since the game is full freeware, anyone can be a part of the beta test, so I should get a good variety of testers =).

As for AIP, looking good! The pattern matching should be pretty quick to finish, and then you are pretty close to finishing =).

Z.

i have a very simple genetic training example. if you want me to post it, respond.

Hi,
"Very simple?" I like the sound of that. Please post it...I am very interested.

Regards,
Chuck

this was originally a bad link. sorry to whoever downloaded it! forgive me. have fun with this, if you download it you can do whatever you want, but post any cool results you find after you tweak. basically, you give it a number(between 1 and 50 works best) and it will "evolve" until most of the "organisms" equation, encoded as "dna"(a hex string) is equal to your number.