Author |
Topic: search tree techniques (Read 4514 times) |
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
 |
search tree techniques
« on: May 20th, 2006, 8:01pm » |
 Quote  Modify
|
I'm wondering which bots use pruning or other similar techniques, and which don't.
All I know so far is:
- Gnobot 2005 & 2006 doesn't prune at all.
- Clueless has a rabbit-only search extension?
- Fairy (at the moment only) looks deeper at interesting moves, and shallower at bad moves.
What does bomb use?
Do any of these bots use alpha-beta pruning?
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
|
Re: search tree techniques
« Reply #1 on: May 21st, 2006, 12:18am » |
Quote Modify
|
on May 20th, 2006, 8:01pm, Swynndla wrote:| Do any of these bots use alpha-beta pruning? |
|
I expect all of them do. It is so standard that I don't even call it pruning!
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: search tree techniques
« Reply #2 on: May 21st, 2006, 5:40am » |
Quote Modify
|
Ohhhhhhhhhhhhhhh gotcha ... so Gnobot 2005 & 06 uses alpha-beta, but doesn't use any real pruning, nor any extensions right?
|
|
IP Logged |
|
|
|
unic
Forum Guru
Arimaa player #1878
Gender:
Posts: 63
|
|
Re: search tree techniques
« Reply #3 on: May 21st, 2006, 3:14pm » |
Quote Modify
|
Fairy uses alpha-beta (of course), or to be more specific, nega-scout with aspiration windows at the root.
I've been running tests on the looking shallower at bad moves lately - cutting search depth by 1 ply, half a ply, or not at all, makes no discernible change in playing strength. So, I'll probably remove that part (as if it makes no difference in strength, I'd rather go with the simplest version. Cutting search depth by 2 ply made it noticeably weaker.
Bomb must use various techniques - probably both some pruning (or looking shallower at sequences) and extensions - setup a position in the downloadable bomb, hit Analyze, and look at its output - it gives depth as for example 9 (6-16) - so 9 depth, but real depth varying between 6 and 16.
|
|
IP Logged |
|
|
|
unic
Forum Guru
Arimaa player #1878
Gender:
Posts: 63
|
|
Re: search tree techniques
« Reply #4 on: May 21st, 2006, 3:15pm » |
Quote Modify
|
on May 21st, 2006, 12:18am, 99of9 wrote:
I expect all of them do. It is so standard that I don't even call it pruning! |
|
I'd agree! Thing is, alpha-beta never changes the value of the root node... it never prunes parts of the search tree that might matter.
Pruning, to me, generally refers to 'unsafe' pruning - which might (or might not) theoretically change the value of the root node.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: search tree techniques
« Reply #5 on: May 21st, 2006, 4:00pm » |
Quote Modify
|
Ahh thanks for explaining all this to me (a newbie to games programming).
I'm reading up on alpha-beta ... very interesting.
So why is bomb so strong? ... I can't believe that it's because it has better evaluation, because clueless P1 seems to be stronger than bomb P1 ... so does this mean that it comes down to bombCC having better search tree pruning techniques than cluelessCC??
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: search tree techniques
« Reply #6 on: May 21st, 2006, 6:35pm » |
Quote Modify
|
on May 21st, 2006, 4:00pm, Swynndla wrote:| So why is bomb so strong? |
|
In human strategy terms, Bomb is so strong because it understands trap control better than any other bot. It fights to gain control of a trap with more precision than other bots, and when it is doomed to lose control it gives up and cuts its losses sooner than other bots. Bomb isn't perfect at trap control by any means, but it is noticably the best of the bots.
In computer science terms, Fotland said that Bomb does "quiescence search". I don't understand how that is possible. In chess, quiescence search means (I think) deepening the search only with capturing and checking moves. But in Arimaa a capture move can take the full four steps, so how can Bomb look at only capture moves without generating a lot of unwanted moves? Alternatively, if the unwanted moves are in there even temporarily, why isn't quiescence search prohibitively expensive?
Apparently Fotland has found a way of looking at it that eludes everyone else to this day, at least a year and a half after he shared with everyone that he somehow manages to do quiescence search. I don't know nothing about coding, but from where I stand, it looks like Fotland is some kind of wizard.
|
| « Last Edit: May 21st, 2006, 6:44pm by Fritzlein » |
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: search tree techniques
« Reply #7 on: Jun 16th, 2006, 2:59am » |
Quote Modify
|
I don't know what quiescence search is, or for that matter most of the ideas that are discussed here. yet.
but just in case anyone didnt already find this I thought I would mention it .. the thread at
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=devTalk;action=display ;num=1073334799
has a summary of what Fotland claims bomb has. Does he not plan on working on it anymore?
it's too bad if that is the case. Would he be willing to sell the code? That time he spent writing it, at least 3
solid months of 40 hour weeks.
I am sure that I am not the first to consider that way more very well developed code has been lost
due to improper archiving, people leaving companies, companies going out of business,
getting acquired, or the source being deleted by the new lab tech who didn't know what was on the drive that he
had just formatted, etc.
I suppose human knowledge continues to evolve and many systems continue to work without the source even existing
anymore, but once we reach a certain point, if anything major breaks, life will become like that in Asimov's Nightfall.
Anyway. Bomb is pretty good.
So who is going to write the next logical successor? True AI with the additional ability to speak fluent arimaa
notation, predict human oversight and accomodate server overload natively? :)
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: search tree techniques
« Reply #8 on: Jun 16th, 2006, 11:48pm » |
Quote Modify
|
Thanks for the link ! interesting ... still he doesn't technically explain why Bomb is so good 
As for the next bot ... well, we are here and he's not, so it's up to us  I'm giving a try, but I fear what Fotland writes in a mn takes me one hour ... Still I'm trying to implement Leo's idea of agents trying to achieve goals ... funny but interesting idea
Are you trying to program one, Nick ? I've not heard about Fairy recently ... neither about Nathan's progress ...
jdb seems to have a lot of ideas to work on ... are there other people building their bot currently ?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: search tree techniques
« Reply #9 on: Jun 17th, 2006, 2:54am » |
Quote Modify
|
I am working on a complete eval overhaul for Gnobby, but it is still a long way off.
|
|
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: search tree techniques
« Reply #10 on: Jun 17th, 2006, 7:25pm » |
Quote Modify
|
Are there any C++ runtime libraries for linux? the ideas I had for a bot are based on my methods of writing code for windows which may or may not actually work on linux. I could do it in C but then I would not be doing my best work. the reason I want to do it in C++ is to extend some level of evaluation to each of the nodes based on type, then have a list of options generated based on those evaluations and pick them by value to process at a global level. this would allow a much deeper search I think, and based on each object's view of the board which would allow goal based evaluation to be easier too. all of this would be possible with C I am sure but it starts to be complex enough to ensure all of the requirements are considered that it really wouldn't be as attractive an option. I may kick it around a few times anyway though.
At the moment I have a few things to learn before I am ready to begin writing my bot. so it may yet be a while for me too. Are you bored with all of the current bots already? 
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: search tree techniques
« Reply #11 on: Jun 19th, 2006, 4:55pm » |
Quote Modify
|
There may be more specific compilers on linux, I don't know, but the standard GNU linux compiler "gcc" is designed to compile many different languages, and C++ is one of them.
Maybe this helps? ...
http://gcc.gnu.org/onlinedocs/libstdc++/documentation.html
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: search tree techniques
« Reply #12 on: Jun 20th, 2006, 6:11am » |
Quote Modify
|
on May 21st, 2006, 6:35pm, Fritzlein wrote:| how can Bomb look at only capture moves without generating a lot of unwanted moves? |
|
It must be similar to searching for goal moves, which is hard coded in some other bots as well. I think it has to go in increasing numbers of steps and keep those numbers at a tight minimum :
- There are no capture possible in one step.
- Captures in two steps are made of a push or a pull into an unprotected trap or a push or a pull of a lone trap-protector.
- Captures needing three steps are those needing a step before capturing in two steps. That step can only be about getting the pushing or pulling piece next to the pushed or pulled enemy piece, or unfreezing that pushing or pulling piece, or emptying a needed target square. I think.
- Captures in 4 steps... well, something a little more complicated along those lines.
David Fotland is an engineering wizard
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: search tree techniques
« Reply #13 on: Jun 20th, 2006, 10:46am » |
Quote Modify
|
on Jun 17th, 2006, 2:54am, 99of9 wrote:| I am working on a complete eval overhaul for Gnobby |
|
Good luck !
Nick : .... hum .... Well I'd like so much to see another bot get past Bomb
|
|
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: search tree techniques
« Reply #14 on: Jun 22nd, 2006, 11:44am » |
Quote Modify
|
I was looking for a good book on Game AI and found some interesting sites...
for one, check out this article...
http://ai-depot.com/LogicGames/MiniMax.html
but that is just one step along the way, I still need more info to really understand the optimizations and extensions that need to be designed into mine.
unfortunately it seems true AI wouldn't actually even be as good as a human at this game.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print