AI for Othello

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!"

Othello is all about having a good evaluation function. Searching the entire tree is out of the question, even for the 8x8 board (strong programs can do a complete search in the end-game - around 20 moves before the end). Also, the efficiency of the min-max search depends completely on the quality of the evaluation, as are advanced search methods.

A simple evaluation function should try to minimize the opponent mobility (number of moves he can make) and increase own mobility, and also try to capture the corners and avoid moving next to the corners. Trying to have the most pieces is not a good strategy (in fact, in the early game it''s probably best to try to have as few pieces as possible).

...which is why it would be better to just weight win/loss conditions in the end game rather than trying to GUESS as to what a good mid-game position would be.

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

I think you underestimate the size of the search tree (been looking for a reason to say "underestimate" for a long time ) It''s simply impossible to search right to the game end during much of the game.

Well, that is true. I haven''t put a lot of thought into the scope - just the theory. I would be interesting to calculate how big that tree woud get. I suppose someone has already done it so I''m not going to burn the calories to do it myself.

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

quote:

---

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

---

Sorry, Dave, I missed that in the original post.

My brother made an AI opponent for Othello, and from my knowledge of listening to what he found out, I have found that it is not a good idea to ''score'' board squares. Because the score of the x squares can change dramatically throughout the game. In the simpliest version of your program, you should at least have some edge tables (at least 4 for each 8x1 sized edge). I have seen a 7 or 8-ply searching program without edge tables get beat by a 2-ply searching program with them. Take a look on the internet for simple ways of producing them.

The last thing you want your program to do is attempt to grab the most pieces right off of the bat - in fact, this is never a good idea unless you see a final board position (i.e. end of game). It is typically what beginner humans do when they learn to play, and you will notice that even an amateur will destroy a beginner with this train of thought. Also, as someone has already mentioned, mobility is far more important. One of the most important things, in fact. If you can get into positions in which you have 15+ moves, and the opponent only has 3 or 4, then you are in control of the game (much like any other game, except positions like this are far more common in Othello, than say, Chess). This typically happens when you have a few pieces in the middle, and the opponent has surrounded your pieces with a ton of his own.

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