So there's a programming contest for my AI class to see who can write the best Othello-playing program (the game is actually played on a 10x10 board with holes cut in it, so it's not REAL Othello). Anyways, looking at winners from past years, it seems that whoever can search deepest and completely solve the endgame first wins. A lot of people focus their efforts on learning algorithms and board evaluation functions, but depth seems to win more games. Last year's winning program could solve a 17 ply endgame (time limit for the game is 150 seconds), so that's the competition. Since depth is key, I'm trying to think of a creative way to get more of it. I was wondering if someone could tell me if the following idea is good or retarded. IDEA: Use MTD(f) to crunch chew through the first 10-12 ply in a midgame position. Keep track of the 3 or 4 best lines (can MTD be adapted to do this?). Once we reach the search horizon, for each of the 3 to 4 final positions corrosponding to each line, do perhaps 100 additional very narrow breadth searches. These searches would be slightly random and explore different branches. Then, for each of the 3 to 4 best moves, average together the evaluations from the 100 searches. Play the move with the best average evaluation. The idea is that once we get to point where we can no longer afford full-breadth searches, we feel around in the dark to get an idea for what might be there and take the route with potentially fewer pitfalls. This isn't a perfect solution because it's not gauranteed to find any really good moves or any traps, even if they are there. The opponent needs only one forcible bad line to ruin you, even if there are lots of good lines if the opponent makes a mistake. So I was wondering if averaging the board evaluations is of any use at all in determining if one position is better than the other. Keep in mind that none of the other programs in this competition will be trying this, and will otherwise only search to the depth that my program would otherwise search to. Has anyone experimented with this kind of thing? I've written a chess program before, so I know about some of the issues, but I really have no clue how to play Othello well, and thus I have no real intuition for good heuristics. I don't think this technique would work well in a chess program.

I am not a great player of othello (for our confused American readers, you would call it reversi I think).

However, when I beat a computer, it is usually because I claimed a corner early on, which became incredibly useful eventually but was pretty much useless for the next 10 or 11 moves, say. Taking the corner is similar to making a particular move in a chess opening - you can't see ahead far enough to make use of it, you just know it's a good thing to do.

So, once you get to your deep level, adding scores for "I have a corner" and "opponent has a corner" might be a good heuristic, especially early on in the game.

I'm no great Othello player either, but there's definitely a huge advantage in taking corners and (to a lesser extent) sides early. IIRC, one of the MSVC++ examples was an Othello game, which was damn hard to beat. It was basically an up-to-6-ply search with each board position assigned a score. I'm sure the same heuristic (which has ~0 speed overhead) would apply for a 15+ ply search, with even better results.

I did some of this sort of thing (playing with search trees etc.) in my AI course, but I never managed to get any appreciable increase in playing strength over a brute force search. Maybe just optimize the fsck out of it in assembler? Heyyy... try and write your AI into a pixel shader and do it in parallel on the graphics card. That would kick ass! :)

Expecting to be able to search to ply 10 sounds a bit optimistic, even with mtd(f). If you are going to do selective search then use multi-probcut, simply because it is tried and true.

About the heuristic: DON'T rely on a weighted-squares strategy! It only works against clueless opponents. When I was a teaching assistant and people demonstrated their othello programs using this strategy to me, I could always without exceptions fool it into a humiliating loss. Since they are so easily predicted it is a small feat constructing a situation where taking a corner is actually a bad move.

Instead focus on mobility. It is the single most important feature in the othello mid game. If you have time then you can play with edge patterns etc to complement the mobility evaluation.

As for the end game I've heard people getting good results using fastest-first move sorting. Google for it..

Oh and using a clever board representation which lets you write the board evaluation function as just a series of table look-ups is essential if you want to be able to search deep.

Yeah, all the top programs in the past have used with MTD(f) or multi-probcut. The contest has been going on for several years, and recently the MTD(f) programs have been winning more. 10-12 ply has been routinely reached by the best programs in the middle game (Othello has a smaller branching factor than games like chess - I think b* is something like 3 with the right hueristics).

It's unclear how good each square is on our board because we are playing on a 10x10 surface with "holes" cut in the board at (3,4), with respect to the center, so that there are 4 holes and rotational symmetry is preserved. We have to implement some kind of machine learning anyways, so I thought I would have the program "discover" which squares are best by playing itself a lot. This approach also has the advantage that I can assign different squares different weights depending on the phase the game is in.

The real goal is to build an anti-computer computer Othello player. Scientifish, you mentioned a technique that you use in playing computers in Othello to make the corner squares bad captures. Keeping in mind that I suck at Othello, is there an algorithmic way to do this? A cheap trick like that would virtually guarantee dominance, since most of the other 50 programs in the contest will be cookie-cutter alpha-beta + simple heuristics type engines.

Also, on the subject of video hardware - computing with pixel shaders sounds like a cool idea, but I doubt the machine I'm working on in the computer lab has more than a geforce 3. Is it worth it if there are only a handful of pixel pipelines on the card? Do you know of anyone harnessing pixel shader hardware for AI? You might have been joking, but here at Stanford there's a whole group of researchers exploring using networked video hardware as a general purpose parallel processing device.

Can't remember any top program in the past using MTD(f). Anyway, sure 10 ply is possible but don't you have a dead line too?

The branching factor is slightly less than 10 in the othello mid game, but with good move ordering etc you can get close to an effective branching factor of 1..

Well if you are going to implement machine learning then I guess you can train your program against an opponent which uses the weighted-squares strategy, and it should learn how to exploit the flaws of that strategy.

Do look at Michael Buro's papers about Othello and machine leaning. I would implement his GLEM frame-work myself if I had had a course in statistics, but since I haven't I dont understand everything he writes in his papers yet.

With GLEM you dont have to worry about features like parity and mobility yourself, everything is approximated with patterns.

What I did against those programs was just to use parity.
Basically I give the opponent the four middle edge squares first, then I give it the corner and take the square next to the corner myself. I then give away the corner at the other end and subsequently take all squares on the edge except the corners. Voila, I got 6 out of 8 stable discs. This is a bit simplified, not all programs were fooled this easily, and you have to be careful not to ruin your chances of repeting this trick on the other edges. If you're lucky you get everything in the middle and your opponent ends up with only four squares: the corners.

Hey Telamon,

I don't think you had a very good idea. And your huge database idea that you posted to the newsgroup was also pretty retarded. Especially since you got bitch-slapped around in the tournament. And did I mention that we owned your ass in head to head play? Yeah that's right bitch.

Have a nice life.

Quote: Original post by Anonymous Poster
Hey Telamon,

I don't think you had a very good idea. And your huge database idea that you posted to the newsgroup was also pretty retarded. Especially since you got bitch-slapped around in the tournament. And did I mention that we owned your ass in head to head play? Yeah that's right bitch.

Have a nice life.

mmm, your maturity just shines through...

To the ap -> That wasn't too nice, now was it?

To the op -> nice idea! perhaps you could modify it, maybe use it to effect the end node eval, so you evaluate it. you then do a simple depth first probing, to affect the score. (by probablilty).
The ones that look promising, should be probed further, and those that don't should be pruned or not probabed at all (or only probed a little bit).

From,
Nice coder