Author |
Topic: Incomplete heuristics (Read 1543 times) |
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender: 
Posts: 119
|
 |
Incomplete heuristics
« on: Aug 25th, 2005, 1:42pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Incomplete heuristics
« Reply #1 on: Aug 25th, 2005, 7:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Incomplete heuristics
« Reply #2 on: Sep 2nd, 2005, 5:19pm » |
Quote Modify
|
on Aug 25th, 2005, 1:42pm, 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.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Incomplete heuristics
« Reply #3 on: Sep 2nd, 2005, 11:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Incomplete heuristics
« Reply #4 on: Sep 10th, 2005, 5:43am » |
Quote Modify
|
on Sep 2nd, 2005, 11:02pm, nbarriga wrote: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 ....
|
|
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.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Incomplete heuristics
« Reply #5 on: Sep 10th, 2005, 7:08am » |
Quote Modify
|
on Sep 10th, 2005, 5:43am, 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.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Incomplete heuristics
« Reply #6 on: Sep 10th, 2005, 10:30pm » |
Quote Modify
|
on Nov 4th, 2003, 5:41am, 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?
|
| « Last Edit: Sep 14th, 2005, 12:55am by clauchau » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Incomplete heuristics
« Reply #7 on: Sep 23rd, 2005, 11:26pm » |
Quote Modify
|
on Sep 10th, 2005, 10:30pm, 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.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Incomplete heuristics
« Reply #8 on: Sep 27th, 2005, 5:47am » |
Quote Modify
|
on Sep 23rd, 2005, 11:26pm, 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.
|
|
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Incomplete heuristics
« Reply #9 on: Apr 26th, 2006, 1:28pm » |
Quote Modify
|
on Sep 27th, 2005, 5:47am, clauchau wrote:
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. |
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print