Ok I''m a beginner in AI, and I was asked in a school assignment to make a 2 player othello game. Now I would like to port it to single-player as a hobby. Any simple approachs I could take to make a somewhat good AI? I tought of checking every possible play for the highest number of "conversions". I would then add some "bonue value for strategic points such as the corner etc.. any advice ?

I made one for college.

The cells near the edges are danger zones, since the opposing player could use them to grab an edge. So score them negative.

The edges are medium value, the corners high value.

Other than that, the value of an arrangement is the actual score (their chips minus yours).

At least, that''s the method I used. I didn''t bother with special beginning game tactics or endgame tactics, since I personally didn''t play the game enough to have an instinct for it.

There was also no internet back then, sonny, so my research was limited! *Limps to couch*

i checked the net, but the ressources I find use sophisticated AI techniques I cant use right now... I hadn''t tought about the near-the-edge things. The fact is that I never really played the game either... So as for testing, a ChooseRandomMove(); would probably beat me anyway.. Thanks for your reply

There are huge ongoing discussions of this on the game AI newsgroups lately. I haven''t read them, but I would guess that it would involve a complicated MiniMax tree. At that point, I would suggest knowing how to do one for a simple turn based game like Tic Tac Toe and then see if you can evolve it from there.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

Check this page for explaination and pseudo code for a simple game tree search algorithm that can apply to any 2 player game with full information known about the board position which involves no chance (i.e no dice), like chess, checkers, othello, etc:

http://www.xs4all.nl/~verhelst/chess/search.html

Also, this may be stupid, but are you sure your 2 player game assignement requires an AI opponent? Usually school assignments require only 2 human opponents. If it required an AI player, I think you would already have been taught the basic alpha-beta search algorithm.

Jason Doucette - my online résumé page: www.jasondoucette.com
projects, real-time graphics, artificial intelligence, world records, wallpapers/desktops

He said in the original post that he was doing the AI opponent as a personal project.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

As for assignments of points, I''d give the corners the highest points, edges high points and those spots next to the corners lowest points and those next to the edges low points. This way the computer tries not only to get the high value ground, but keep you from it also. You can adjust difficulty by changing the number of points assigned to those spots. Example:

Difficulty: Easy, Medium, Hard
Corner: 5, 8, 12
Edge: 3, 5, 8
Adjacent to Corner: -4, -6, -9
Adjacent to Edge: -2, -4, -6

If you want to make a Very hard, just make the negative (adjacent) points be the same as the associated location (-12 and -8).

This actually seems like it would be a pretty simple AI task, relatively speaking.

If you end up doing a minimax treatement, you won''t need to tell the computer what sucks and what doesn''t... it will find out for itself.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"

quote: If you end up doing a minimax treatement, you won''t need to tell the computer what sucks and what doesn''t... it will find out for itself.

That''s not true. Minmax will only search a few moves ahead. At the leaf nodes you have to evaluate something and return a score. So you do have to tell it what is good and what isn''t good, unless you want to wait for the minmax search to finish, in a few billion years (if you''re lucky).

It is true that the deeper it searches, the less knowledge you have to give it, because it will figure some things out on it''s own. But not THAT much, especially using minmax.

You could run minimax out to the end game states wherein you value you it a +1/-1 for a win/loss. This is do-able in Othello because, like in Tic Tac Toe, there are only x moves that can be made total. In chess, there is not really a finite limit to the number of moves so the ability of actually exploring to the ends of all branches is very limited. Therefore, leaf nodes are determined by a time based function rather than a game state function.

With Othello, you have 2 limiting factors. One is the number of squares on the board. If I recall, the sides are 10 spaces long and you start with 4 pieces on the board... so there are 96 turns total in the game. Also, there is a mathematical curve to how many moves are available at any one time. There are relatively few at the beginning, more at mid-game and then gradually back to 1 remaining move at the end. This helps to shape your tree and keeps it from branching TOO far out of control.

The end result is that you COULD be able to run out a full minimax tree for the whole game and just total up the possible +1/-1 end games to get the best possible branch to traverse. If you didn''t want to go that far ahead, you would have to assign some sort of weighting to both the spaces on the board and the advantage you would have on the board at the time. Let''s face it, there ARE times when taking an edge or corner space would NOT get you as much of an advantage as taking a less important space. Surely those times are rare, but they would lend importance to some sort of analysis algorithm beyond "is this a good space". The best solution would be one that involves some sort of planning - which minimax does.

Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"