Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> AI or not AI?
        
(Message started by: Swynndla on Mar 11^th, 2006, 12:25am)

Title: AI or not AI?
Post by Swynndla on Mar 11^th, 2006, 12:25am

Omar seems to help bot developers quite a bit by letting the bots play on this site, and pointing out the weaknesses in bots (in fact everyone in this community seems to do that) etc, not that Omar wants someone to win his money (and the other's money who have sponsored the prize fund), it's just that Omar truly doesn't believe that a bot will be better than humans using existing AI programming techniques, and the prize fund is there to motivate people to develop new AI techniques ... okay I haven't said anything new so far, but my question is, are bot developers really trying to think up new AI techniques? ... or are they mostly trying to directly assign numbers to pieces and their positions (eg an advanced R that has its E near is worth such and such, and an M hostage is worth so and so, etc) and juggles the numbers until something sensible comes out? It's just that to my mind, juggling directly assigned numbers isn't AI at all (even though that technique works with chess bots).

Title: Re: AI or not AI?
Post by ntroncos on Mar 11^th, 2006, 9:28am

on 03/11/06 at 00:25:18, Swynndla wrote:

[...]
or are they mostly trying to directly assign numbers to pieces and their positions (eg an advanced R that has its E near is worth such and such, and an M hostage is worth so and so, etc) and juggles the numbers until something sensible comes out? It's just that to my mind, juggling directly assigned numbers isn't AI at all (even though that technique works with chess bots).

juggling with the number is a very important part of the AI. The whole point of AI is to make the computar do right choice of moves. The only way a bot can may right choices is if the can evaluate properly the game board. The discution about the pieces value is some what tricky because arimaa is very sensible in the positional aspect, and if you just rely on the absolute value of pieces the bot will play no quite good.

you have to take into consideration:

Value of the pieces
Positinal aspect
And the branching factor

those 3 aspects are key in the development. Basicaly what we are looking for is a good Material positional evaluation, and a way around the branching factor.

Title: Re: AI or not AI?
Post by IdahoEv on Mar 11^th, 2006, 11:15am

I am trying some very non-traditional techniques that do not much resemble the other bots that I am aware of. More info to come, down the road.

Title: Re: AI or not AI?
Post by Fritzlein on Mar 11^th, 2006, 11:18am

on 03/11/06 at 00:25:18, Swynndla wrote:

but my question is, are bot developers really trying to think up new AI techniques? ... or are they mostly trying to directly assign numbers to pieces and their positions (eg an advanced R that has its E near is worth such and such, and an M hostage is worth so and so, etc) and juggles the numbers until something sensible comes out?

I think this is a fair distinction to make. While it is true that some people consider alpha-beta pruning with a hand-crafted evaluation function to be an AI technique, most people don't think it is AI. As commonly understood, AI has to be fuzzier and/or it has to include learning of some type.

I'm pretty sure that for the top two bots, Bomb and Clueless, we have a couple of developers who want to do whatever works, and what works is not AI. Bomb and Clueless have no learning (except a little bit of opening book in Bomb). I don't think they have anything like bot_V's method of choosing moves based on a plan, incidentally neglecting most possible moves.

If I interpreted Haizhi's paper correctly, he made a very serious attempt at having his bot learn. The parameters started out hand-turned, but bot_haizhi was given a chance to learn and self-correct. Apparently this produced absolutely no increase in playing strength. So there was an earnest AI endeavor that fell flat.

99of9 will surely be able to explain his several attempts to have Gnobot learn (apart from the opening book, which seems to have a real value against other bots, at least), but if I'm not mistaken, all of his attempts at AI have done nothing to improve his hand-tuned parameters. 99of9 may be handicapped in this regard by being so good at Arimaa that machine learning has little room to improve over his own intuitions.

I'm not sure if everyone would consider bot_V to be an AI attempt, but aggressive forward pruning is at least a radical departure from standard brute force computer thinking. Unfortunately for Gerhard, bot_V didn't play as well as bot_Loc, which had been done in a more traditional way.

So I guess the upshot is that most people are willing to try AI techniques, but they haven't helped at all yet. Furthermore it just so happens that the two stubborn developers who think it isn't worth their time to try AI are also coincidentally the two who have created the top two bots. Go figure.

Title: Re: AI or not AI?
Post by ntroncos on Mar 11^th, 2006, 7:23pm

With bot weiser we have done some attemps. nbarriga made some tests with genetic algorithims, i played around with tabu search. Unfortunatly until now our bots have been unable to beat the classic bots. I think that with a little more work we could see some improvement in the future.

I suppose that those aproaches are more AI than the classic mini-max method (alpha-beta).

nbarriga also fooled around with TD-\lambda to see if he could adjust the weights of the evaluation function, that way he could make the bot learn after each game. I dont remember what his conclusion where tought.

Title: Re: AI or not AI?
Post by 99of9 on May 3^rd, 2006, 12:11am

on 03/11/06 at 11:18:58, Fritzlein wrote:

99of9 will surely be able to explain his several attempts to have Gnobot learn (apart from the opening book, which seems to have a real value against other bots, at least), but if I'm not mistaken, all of his attempts at AI have done nothing to improve his hand-tuned parameters. 99of9 may be handicapped in this regard by being so good at Arimaa that machine learning has little room to improve over his own intuitions.

A brief aside: I just found out that Omar disabled opening book learning in bot_Gnobot2006. So the version we play is exactly frozen in time as it was during the 2006CC.

My previous attempt at learning was this:
* Take every position in the games database.
* Evaluate it at 8 ply.
* Save that eval score as the target score for that position.

then repeat the following
* Vary the parameters used in the eval.
* Evaluate every position at 0 ply.
* See if you got closer to the target scores than the previous parameters did.
* If so, accept the variation.
* If not, go back to the previous parameters.

(This was actually done using the Simulated Annealing method, if you know of it...)

(I repeated this entire process a few times)

My conclusion was:
Tuning will not make up for evaluation features that don't exist. No matter how well tuned Gnobby is, I will have to teach it about goal threats before it can become good at goal defence :-). I don't think tuning is Gnobby's current weakness.

Title: Re: AI or not AI?
Post by Swynndla on May 3^rd, 2006, 5:10am

Very interesting.

From what I know about SA, it's exactly the same (in my mind) as a simplified class of EP (Evolutionary Programming). If I'm correct, then it's quite simple to program, but still very powerful.

A thought: if you added up the evaluation scores to
Quote:

See if you got closer to the target scores than the previous parameters did

(or sum of absolute values, or the sqrt of the sum of squares, or some other linear measure ... I'm not talking about fitting the parameters to a linear model, I'm talking about measuring the fitness of the new parameters) then could there be the case that it might get closer in a lot of positions, but a few special positions it could be even worse (but the overall total was still better and so those parameters would be accepted). But if those special positions cropped up once in every game (mostly), then consistency would go out the window, and it'd lose quite a few games. Am I making any sense?

One way to tackle this may be using the sum or squares rather than the sqrt of the sum of squares, so that any "outliers" are punished more ... or even the sum of cubes. I think this would be better for consistency, but it'd be very restrictive, and it'd only be good if you wanted to make something pretty good just that little bit better.

Another way might be to exclude those outliers and put each of them in their own sub-class, where you may or may not choose to use SA on them, and because they are excluded, the remaining parameters will hopefully better fit a linear fitness measure (not talking about linear parameter model though). At the end of it all, you may have piecewise rules like: in the opening use evaluation optimization A, or in the middle game use B, or in the end game use C, or if there is an advanced supported rabbit, use D, or if there is a camel hostage use E etc.

Title: Re: AI or not AI?
Post by 99of9 on May 3^rd, 2006, 5:46am

on 05/03/06 at 05:10:06, Swynndla wrote:

One way to tackle this may be using the sum or squares rather than the sqrt of the sum of squares, so that any "outliers" are punished more ... or even the sum of cubes.

Yes, I had to play around with this kind of thing a fair bit, because you get *very large* errors near the end of the game when it spots goals within 8 ply ;-).

Your piecewise ideas sound reasonable too, but I wanted something quick and easy to test out :-).