Some time ago, I had thought about an abalone IA based on a neural network.

Actual abalone IAs are currently strong because of brute force against common players, ie their ability to calculate deeper moves.

However, I think this approach has some limitations. The first limitation is in the time needed to calculate depper moves, which grows exponentially. The second limitation is in the current level of players, which is weak when compared to some other games (like chess), but i am confident that this limitation will rise with the players becoming better and better.

A game more played through deep calculations, like it is in chess, is currently being experienced by players like eob or gohatto. I am pretty sure that their aim is partly to counter programs such as aba-pro or nacre. Once players will be trained to such deep calculations, there is the risk that those programs become 1- too weak or 2- far too slow.

I think an IA designed around a neural network could be interresting in two points :
1- by requiring less time between moves
2- by being able to mutate and evoluate, particulary in this internet era.

I had in mind an IA oriented towards patterns recognitions, with a more typical "pathfinding" algorithm for going from the current reckognized pattern to the more advantageous known pattern.

The main reasons why i didn't go further in this project is because it's complex and time consuming, and most of all because i am very lazy. However, it doesn't cost too much to talk about this right here...

Nacre has several evaluation functions. Most of them use neural networks. I prefer to call them non-linear functions, though, because the term "neural" has too many unfortunate associations, like "thinking", "human brain", "learning (like humans)".

The strongest existing evaulation function is *not* using an ANN. The reason it is strongest is: 1) it is easy to use for forward pruning, 2) it is fast to compute. Both allow deeper searches.

In the 1980'ies (as far as I remember), many AI researchers tried making chess programs that were using a plan, but they were not strong enough. Take a look at http://en.wikipedia.org/wiki/Computer_chess

Why does Nacre use ANN then? Because I wrote a Backgammon program before Nacre, and much of the code was transferred. In Backgammon, ANN have had much success.

Can Nacre mutate/evolve? Yes, in a sense. During the 2003 olympiad, I trained Nacre on the games it played against AbaPro. This changed its evaluation function so it played at a higher leve. Unfortunately, it did so by mimicing AbaPro and this just made it easier for AbaPro to predict the moves of Nacre.

However, the effect of the ANN is much smaller than what you can get from examining games Nacre has lost, and trying to come up with a feature that shows Nacre how to avoid its mistakes. The human brain is still the master -- remember that the A in ANN is very large.

On my to-do list is a pattern-match function for my ANN, but about one year ago I was convinced that deeper search was the best way forward. My top priority right now, is a search extension, that can give an accurate answer to whether isolated marbles in ring 4 and 5 (the two rings on the edge) can be pushed out.

And finally, writing an Abalone program is time-consuming. However, you can download full source for Abalot / El-Boana / PeterTaxAbalone, three good implementations. The first has a high-speed search/evaluation, the second an early forward pruning scheme, and the third is beautifully coded -- a good place to add your own experiments.

If you want to play around with these programs, write a message on http://groups.yahoo.com/group/abalone_prog/ and I will gladly help you getting started. (I have modified all 3 programs to use the abnet net-protocol)

Thanks for the feed-back.

I think you are right when stating that evaluation fonctions are to provide better scores than pattern recognition/ann in abalone mainly, i think, because the blind horizon problem can easily be solved in abalone : you just cannot be completely wrong by getting more compact and closer to the center.

I wish i was a mathematician so that i could investigate alternate ways that this one, which seems the strongest so far, but also leading to such a boring style.

In my mind, there are three main components in an abalone game : structure (usually translated in game by compactness), position (how far from the middle) and timing (number of moves needed by each player in order to threaten the opponent).

I thing we have a lot of experiments to do to explore the abilities of micro-structures (like the 4 vs 1 balls currently discussed by silver and you), and i find very promising the fact that you want to explore these directions.

About the positionning (the importance of the middle), well, it's just an intuition, but i think its importance is relative to the structural part : the more compact it gets, the more important becomes the middle.

I hope your current work on sub-structures will reveal viable alternate styles in more and more cases. Those alternate strategies are all relying, in my mind, on the third component i talked about : timing. It is hard to give a clear definition of what i precisely mean by timing. To sum it up, it consists in finding a threatening suite of moves shorter than any of the opponent so that you force him to react to your moves rather than going on with his own suite.

I think timing is the essential notion that allows you to evaluate how much a sub-structure is dependant or wedged to another (sub)structure. This cannot be answered in a pure geometric/spatial manner (meaning you have to make projections in a short future to determine "how much" two structures are possibly related to each other).

I think there are a lot of possibilities with sub-structures that go far beyond the cases when they fight smaller sub-structures (like "how to take one opponent's ball with 4 of yours"). They can be explored in each and every specific case, but i am pretty sure that some generalisations can be coded out around some kind of timing concept given a weight of same magnitude (at least) that it is to structural and positionnal parts.

In netabalone, gohatto was playing around those notions of micro-structures and timing one or two years ago. Netabalone doesn't allow you to consult further than the 50 last games (despite all of them are stored - what a shame !), but i think some are accessible through achillobator's history (abillobator = eobllor). Those games are interresting because they demonstrate in an empirical manner that strategies based on micro-structures and timing can often compete or even beat strategies based on structure (compactness) and position (the middle). However, the games you'll be able to watch throuh achillobator's history are a little biased because eobllor was also playing micro-structures and timing. It would be interesting, maybe, to find games were the two different strategies are competing (but i'd have to do some searches for that).  

--Last edited by chriscool on 2005-10-26 17:50:54 --

Hello chris and nacre,

I think you can find those examples in the histories of Jennys old pseudos, too. She played micro-structures and complex and open games since almost two years, too - especially in Standard-Games.

I dont see any contradiction between evaluation functions and pattern recognition, too, and I agree in the contrary: the best way, probably, will be the synthesis in the particular manner: pattern-recognition to change the evalution-functions according to the patterns and particular types of evaluation-functions to lead the game-structure into particular, advantageous patterns, with, again, particular e.f., and so on.
Therefore the question "Neural network versus evaluation fonction ?" leads into the question:"How to integrate network and evaluation-functions?"

Best Regards,
Silver  

--Last edited by SilverSurfer on 2005-12-16 18:42:39 --