PureGM Gets its arse kicked! But it's getting better!

[pdwyer]

I know that for the last couple of months you've been unable to sleep wondering "I wonder what Paul's been doing lately?"

Well, In january, I was checking this http://en.wikipedia.org/wiki/Gomoku since I was teaching my son (he's nearly 6 so not ready for Go yet) and I noticed the link down the bottom to "The Gomoku programmers' tournament " http://gomocup.wz.cz/en/index.htm . It runs in about April each year and since I've often though about trying to write a Go game but then making a reality check realising the closest I've achieved is a PB Tic-Tac-Tow I thought I'd try my hand at this.

By about Feb, I had a basic Gomoku game program that I could play against so I down loaded some of the loser "brains" (That what they call the AI competitors) from last years' cup to see how well I was doing. Well, Suddenly I realised how much work I had to do still.

April 19th came, and PureGM was as good as it was going to get in the short term, 63 versions on, a somewhat broken implementation of Alpha beta pruning on minimax with a cumbersome strategy engine. It was 4am Japan time and submissions needed to be in by 7am.

I get up in the morning at about 11am to see if it's started and



My submission has been bounced by their mail server !!! So, being a grown man, I begged and pleaded to considering the entry!. Sunday afternoon, no reply still, and the tornament has started, I could see it online and I wasn't represented... All that effort wasted. On the bright side was that I wasn't 100% happy with the final candidate, I needed to fix a few things still but ran out of time.

On Monday, an email titled Results have been anulled

Dear gomocup competitors,
We are very sorry and apologize for all problems with our email message box. It seems that message box became to be blocked on Friday and just now arrived a lot of emails apparently being sent on Friday.

We decided to change email message box. New adress is gomocup@gmail.com. We hope, it will work properly.

Affected AI were: pbrain-HfM(newest), Tito2008, Nabamoku2008 and PureGM. If there are another affected, please try contacts:

Anyway, I managed to win a few games but overall didn't meet my goal of not coming last but there are some monster AI's playing that have been in the cup for 6-7 years running now.

For the last few weeks I've been getting the bugs out still, I want to have a clean version for next year to work on and my 2nd son will arrive late this month so I'm not going to get much more work done on it this year.

My new version (75) has a lot of improvements and can beat the lowest 3 or 4 players now so I'm on the right track at last. As a finish up for the season I have put the engine in a GUI so that others can play against it.

See how you do!



You can download it here. http://www.dwyer-family.net/download/PureGM.exe

When I get the source cleaned up I'll post it. I might canvas some comments to help for next year.

Programming is so much fun when you don't have to do it for a living!

[srod]

Right, beat the easiest level first time.

Now for the medium......

(By the way, pretty cool!)

**EDIT - 3 attempts to beat the damn thing on the medium level! Now for the hard!

****EDIT : what happened to the damn forums? Right, I have the hard level beaten - get it every time now. Now for the final level....

Paul, the program seems to slow down the longer you play it. It eventually eats up 100% of the cpu. I've only noticed this on the hard level.

The 'very hard' level runs too slowly on my old machine. Almost 5 minutes per computer move!!!

[Derek]

Having a play now and just found out that I can click on the same place more than once and therefore lose a counter.

[didier69]

Good game, I would be happy to look at the sources as I would
like to produce abstract games too.

[Rook Zimbabwe]

The problem is that if you can trick the AI.

Easy dies every time within 12 moves... Medium I sometimes have gotten to 22 moves... Beat HARD 3 times so far... was kicked by HARD about 9 times!

Are you only checking for same color near to same color? Then planning a path out?



The three space one combo is killing the AI.

It doesn't like edge strategies either!

But I like it!

In the USA this was called PENTE... had a Roman flavor to the game... soft board and small glass drops for the pieces... played it a lot in the 1970's and 80's.

I know GoMaku came first though!

[Derek]

Sorry to keep finding bugs but I just started a game by playing in the top-right corner and the comp played on 21,2

[thefool]

Make it threaded damnit, i don't have a quadcore for nothing i want to beat it on VERY hard.

[Trond]

I never really understood this game. I mean, I understand the rules, but I don't understand how to win. I mean, I understand that you have to have five in a row, but I simply don't get how to get them there without being prevented by the opponent!

[Trond]

Haha! I beat it on medium! My first ever won game of Go! The AI does some mighty stupid decisions, though.

I always had this feeling that there was no real "skill" involved, it was just a matter of playing perfectly and then you'd win or draw if you started. It actually turns out that that was indeed correct. So it should be possible to write an unbeatable (if it starts) AI for this.

Edit: Of course, the real challenge is to make it run so fast it gets done before the universe ends. But I mean, that's just a formality, right?

Edit: By the way, good job. The first game of this type that has actually engaged me (maybe because it seems possible to beat it). Although I am having a hard time at hard.

[thefool]

oh yeah forgot to say that i liked it too. Medium is perfect. I don't win every time but i do win sometimes. I don't keep repeating the things i win on though, thats not fun. I want to find new ways to smoke it

Well it was simple. 1 exe file, and i was able to play it immediately without any hesitation and trouble with controls or having to read anything. I just started playing!

[Derek]

Good game, shame about the speed on very hard. Can't wait to see the source, see if anyone here can speed it up.

[srod]

Yes I wanted to give it a good spanking on 'very hard' but I could go out and mow the lawn whilst waiting for the computer to make a move!

Good game.

[pdwyer]

Thanks for giving it a whirl!

To address some of the bug reports.

- Playing on line 21, is a bug but I thought I'd fixed the wall bugs (after losing a lot of hair on them). I'll re address this, thanks for spotting it.

- Slowdown as game progresses. Yes, as more pieces get added to the board, there is more to calculate and more canditate points to test. Normal minimax can't get much further than about 4 moves ahead and only 3 or 2 later in the game. Alpha-beta pruning is letting me get a little further (see below for corrolation with the difficulty setting) but pruning depends on the game, sometimes when there are no obvious attack or defence moves there's not much to prune and speed will drop, sometimes dramatically, and then later in the game speed up again as attacks become visible or defence required. I might get rid of the highest level, it's a lot of extra slow-down for not much extra strength. (diminishing returns). Still, sometimes you may be in one of those "take as long as you like to be really strong" kind of moods Actually, I think I capped the time at 5mins per move. The cup had rules of 30sec per move and 5mins for a game so you have to be able to control the time. I could add a settings dialog to control time I guess... (Srod, go buy a new PC )

- Threads. Yep, I have a quad core about 20 versions ago I tried getting threads working but having one thread per candidate move (3 to about 20) but the performance went through the floor Due to time constraints on the competition I dropped the idea. (also, I didn't know how many cores the cup computer would have). It's something I'd like to readdress though and possible seek some help on as maybe I doing something wrong with threads.

- Edges, yes, they are evil the strategies get a little loopy there. need to look at that more (but its not fun so doesn't get prioritiesed )

- "Are you only checking for same color near to same color? Then planning a path out? " Yes and no. The strategy engine does that but the lookahead should spot that on higher dificulties.

The difficulty is based on this:

Difficulty Lookahead moves
Easy 3
Medium 5
Hard 7
Very Hard 9

Where "3" for example is the move black is about to play, followed by white then black again.

4 is required to handle a situation where you have un-ended 3-in-a-row and reaslise it's a forced move and needs immediate attention. 6 or 7 is needed so a dual open three or 3-4 combination attack can be seen and dealt with.

9... well, 9 would be better if the strategy engine was better

Let me clean up the code to post. There have been SOOOOO many iterations and ideas, many that I thought would be a killer idea only to find it got it's arse kicked every time (I had another idea last night too that I want to try ... it never ends

[pdwyer]

Having a play now and just found out that I can click on the same place more than once and therefore lose a counter.

HAHA, forgot about that one! Yes, the first GUI version that I built was for testing purposes and let you play on the same place to change colour for trying strategies out. I need to trap that as the AI will just play again with the board unchanged Sorry.

[pdwyer]

Haha! I beat it on medium! My first ever won game of Go!

This isn't Go Go is here http://en.wikipedia.org/wiki/Go_%28board_game%29 and is LOTS more fun. Not sure if there are any PB players out there. Go takes a serious investment in time to play though (years). Computer version of that (and there is a competition) would be a major undertaking

The AI does some mighty stupid decisions, though.

Examples? Perhaps you are just not seeing it's strategy