Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Incomplete heuristics
        
(Message started by: nbarriga on Aug 25^th, 2005, 1:42pm)

Title: Incomplete heuristics
Post by nbarriga on Aug 25^th, 2005, 1:42pm

Hi, i wanted to know if somebody has tried to use incomplete heuristic search such as Simulated Annealing, Tabu Search or Co-evolutive Genetic algorithms.

May be a mix of things, like making a full 1 or 2 ply search and then select a small population to continue the search with a genetic algorithm.

What do you think of this approach?

Title: Re: Incomplete heuristics
Post by 99of9 on Aug 25^th, 2005, 7:33pm

I don't think anyone has tried that during the search. I've fiddled with some of these stochastic methods for refining evaluation parameters, but that's quite a different objective.

Great to have someone with new ideas along.

Title: Re: Incomplete heuristics
Post by haizhi on Sep 2^nd, 2005, 5:19pm

on 08/25/05 at 13:42:23, nbarriga wrote:

May be a mix of things, like making a full 1 or 2 ply search and then select a small population to continue the search with a genetic algorithm.

I don't think it will work. There are cases like sacrifing a cat to capture a horse, they will be pruned by your shallow search.

Title: Re: Incomplete heuristics
Post by nbarriga on Sep 2^nd, 2005, 11:02pm

I suggested to search 1 or 2 ply to fill in the firsts 4-8 genes(1 for each step) of each individual, filling in the rest with random(but valid) moves. I'm thinking that the individuals should be around 24-32 genes long(6-8 ply), and at each generation you apply at least a couple of traditional genetic operators(crossover and mutation), wich sould be in charge of evolving the individuals into a good combination.

I've seen this approach on experimental programs of chess, with promising results, and i think the results will be better here(beacause of the large branching factor inherent in arimaa), since it will be doubling the search depth from other bots(at least that's what i'm aiming at). Also, having less evaluations than in a alpha-beta class of search, the evaluation function could be more powerfull.

Anyway, this is still random thought and investigation, but i plan on having something working in a month or so.

Title: Re: Incomplete heuristics
Post by omar on Sep 10^th, 2005, 5:43am

on 09/02/05 at 23:02:31, nbarriga wrote:

Very interesting approach. I am heavily biased towards using genetic algorithms and strongly encourage you to try this. It is really amazing what you can do with GA's. I used them in my MS Thesis and on some projects at NASA.
http://arimaa.com/arimaa/about/Thesis/

Are there any papers that describe this approach to using GA's for game playing in more detail.

Title: Re: Incomplete heuristics
Post by nbarriga on Sep 10^th, 2005, 7:08am

on 09/10/05 at 05:43:18, omar wrote:

Are there any papers that describe this approach to using GA's for game playing in more detail.

The only paper about it i've seen is a Computer Science engineering thesis at my university. Unfortunately i only have a hard-copy and it's in spanish. If i can get a digital copy i'll post it here.

The program he developed is at http://www.chessengine.cl/ , but i haven't been able to try it because i don't have MS windows on my computer.

Title: Re: Incomplete heuristics
Post by clauchau on Sep 10^th, 2005, 10:30pm

on 11/04/03 at 05:41:57, Toby 99of9 Hudson wrote:

Deliberately explore branches with very different features than those of branches you've explored before.

For that purpose, we might deeply search a reasonably interesting move, then a second move without any step in common with the first move, then a third move without any step in common with the two first moves... That's about searching 8 moves if there are 32 steps available or so.

Then we pick up the best move among those deeply searched and we try to refine it. We try a move that has exactly one step in common with the best move. Then another move that has exactly one step in common with the best move and no step in common with the previous move, except possibly a step in common with the best move... That's about searching 9 more moves at least if there are 32 steps available or so.

We get a refined new best move. We refine it now by searching moves that have two steps in common with it and no others with each others. That's about searching 15 more moves at least.

Then three steps - about searching 30 moves.

Edit: Unlike what I first wrote, we seem to need to list all valid moves and order them according to the static evaluation, as opposed to list all first steps and favor the most promising, etc. It seems worth it, as the result is we only deeply search 1 or 2% of the available moves at any inner node.

Isn't it close to what we do humans?

Title: Re: Incomplete heuristics
Post by Fritzlein on Sep 23^rd, 2005, 11:26pm

on 09/10/05 at 22:30:03, clauchau wrote:

Edit: Unlike what I first wrote, we seem to need to list all valid moves and order them according to the static evaluation, as opposed to list all first steps and favor the most promising, etc. It seems worth it, as the result is we only deeply search 1 or 2% of the available moves at any inner node.

Isn't it close to what we do humans?

No, I think we humans do something very different. I think we look for some objective to achieve, and then construct a move which which seems likely to get us closer to that objective. We may construct several different moves and compare them, but when each move is inspired by some idea it isn't like what a computer does. The short list of moves which a human evaluates more deeply is not generated by pruning some larger list. Only in a postal game do I ever have time to do (for example) a cursory examination of a dozen moves followed by a deeper examination of the two or three best.

Title: Re: Incomplete heuristics
Post by clauchau on Sep 27^th, 2005, 5:47am

on 09/23/05 at 23:26:14, Fritzlein wrote:

The short list of moves which a human evaluates more deeply is not generated by pruning some larger list.

I agree about her conscious mind. Her visual cortex and other parts of her may have a vague but larger list of available steps or moves though, that help her to construct her single move - even purely based on an objective.

Title: Re: Incomplete heuristics
Post by leo on Apr 26^th, 2006, 1:28pm

on 09/27/05 at 05:47:24, clauchau wrote:

I'm trying to detect in my own mind if there might exist subconscious branch exploration that provide gut feeling. But the more I search, the more I'm inclined to think that the gut feelings come from recognizing patterns that are associated by memory with subsequent moves and states, so the attention is driven to take these moves into account but I'm not sure the moves are simulated in the subconscious.

For instance when I have a look at the region of a trap square I have some bells that ring in a tiny fraction of a second about a piece in danger, but in order to evaluate how exactly the piece is in danger I have to take some time to prospect future moves. The same goes for pieces that are near the trap but are relatively safe, I have a gut feeling of "it's ok, don't worry" just by looking at them. I'd like to reproduce this feeling for my goal-driven bot, I have a strong gut feeling (once again :) ) that this is pattern recognition - which is something that comes only through experience.