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