I have a task to write a Gomoku AI but I`m totaly stuck with the function that evalates the position. When I was writing chass AI i was able to find endless number of source codes so I could get idea what evaluation could be best, and I am good chess player so this is big advantage to when you are into game tactics. But I have never played Gomoku more than a few times casualy so I don`t know the tactics myself and I can`t find any good hints on how to evaluate a position in Gomoku. Not to mention there are almost none source code available that I could find. There is a world Gomoku AI championship, but ALL of that AI`s are closed source. I don`t need any fancy stuff. I would implement alphabeta search with maybe iterative deepening and transposition tables but the most important part of that AI is the evaluation function which I can`t find anywhere. I need to finish it in ten days so because of that I said that I do not have time for some fancy stuff, just want to implement some simple but yet deacent evaluation function that could play on begginer to intermidiate level, and from my experience, when I was writing chess AI, the simple ones perform better if you don`t have really much spare time to fine tune complex evaluation function. :) Thanks, I started to worry about my Google searching skills :) ..or maybe it is just a bad day.

Oops! 10 days is short!
It's no so hard though; you have an board representation and you need to evaluate a good move for a given position. For a start: 4 in a row with an empty space either end is a very good thing because you'll win next go, so 3 in a row is almost as good because you can make it 4 next time...
You get the idea? Work out the good combinations and scan the board for them. I guess if you've done chess that you know about minimax & so on?

Yes, I said that minimax (with alphabeta) is not the problem, just the evaluation function. Again, taking your cases into account, and many many more (.X.XX .XX. and many many more, and not just situations that are good for me, I also have to value moves that block oponent), I`m bothered which values to assign to them, if I for example overrate for in a row and only look to make that streak I could overlook my oponent making for in a row before me and I loose. You got the point? I would loose much time fine tuning the AI trying it with different point distribution for all available threats. I just want to see how, someone who allready spent time investigate it, have done it and I can`t find it on the web.

And also, what would be my hints for sorting moves for alphabeta? I decided to consider only the moves that are at most one blank space away from the allready putted stones on the board (because I want to cut the number of probably bad moves so I could speed alphabeta), but which moves are generally better then other?

[Edited by - ssijak on October 20, 2008 3:36:56 AM]

Temporal Difference (TD) learning was shown to produce good coefficients (quickly) for chess engines

The basic premise is that you have the current position (P) and your current search score (S) which is the minimax of eval()'s over a subset of the game tree..

now, essentialy the idea is.. why not go ahead and adjust the coefficients you use in your eval() for position (P) so that it is closer to (S), the score after an actual search of some depth.

This is often done "on-line" where, essentialy, the engine is ALWAYS learning from its own searches.

The chess engine I played with most that did this sort of thing was exchess, whos source code was available. It learned its own piece cefficients (which rapidly converged to near accepted values), as well as its piece-square tables, if I remember correctly.

Edit:

Here is a paper on the learning algorithm:

TDLeaf()

The way I did the evaluation function for a simple connect 4 game I made was to create a lookup table. It was indexed by an 8-bit value which consisted of 2 bits for each tile in a row of 4 (empty square, my square or opponents square, the 4th value was unused). Each entry stored a value between -1 and 1 (1 for all four containing my pieces, -1 for the opposite, zero for a combination of both sides pieces, etc).

The table was generated by a separate bit of code, and it could be adjusted by hand if need be. Obviously you'll need a 10 bit number which means a 1024 entry table.

I then looped over all possible places on the board where there are 4 in a row, and added the results up (with some extra tests for handling a won / lost board). That does mean that you evaluate multiple overlapping positions, but it seemed to play reasonably well, and was nice and quick.