Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Scoring partial plys, an alternate approach
        
(Message started by: half_integer on Oct 25^th, 2014, 8:34am)

Title: Scoring partial plys, an alternate approach
Post by half_integer on Oct 25^th, 2014, 8:34am

I'm developing my bot and learning about alpha-beta as I go. The following was motivated by re-discovering that alpha-beta node count is b^ceil(p/2), or b² for P3, not b^1.5 - but P4 should also be b².

When my bot can not complete a full ply, I only consider the moves from partial move generation (since there are usually 10-15x as many 4-step moves as 3-step moves) - consider these 3-step moves with the clarification below. Of course, this introduces the fact that I may not have seen the best move in the last ply. It occurred to me that perhaps this could be counteracted by restricting the opponent moves in the same way in their last ply - and since alpha-beta performs very well in even plys, if I can do a partial P3 then I can probably also do a partial P4.

So what I am proposing is this: P1 and P2 searches are full searches (with cutoffs), then I only generate 3-step moves for P3 and P4 and score at P4. Giving the opponent a chance to reply at P4 should produce more valid scores, and having the same restriction on move generation in P3 and P4 should balance out - better perhaps than if I could do full P3 but no P4.

So what are opinions on this idea? I have not implemented it and I don't know if I will - I have many other optimizations I can still make before this point. I believe I read that some chess engines only increase depth by two ply at a time to avoid the even-odd effect of oscillating scores when comparing across plys, and this approach could enable that.

By the way, are other bots able to achieve full P3 through search and eval optimization? Or do most bots only do full P2 and extend only some moves to P3 and beyond?

Here is the clarification: I actually generate moves one "atomic step" at a time, meaning a 2-step push or pull gets generated at once when adding steps. So, a "3-step move" really means any move with 1-3 steps or any 4-step move that ends in a push or pull. Similarly, I can only generate "2-step moves" which will actually have all the double-push-pull 4-step moves, 3-step moves with a push or pull, and 1 and 2 step moves. Since a capture requires a push or pull, this approach boosts those moves to earlier consideration, however I think this is hurting me at goal search where the goal moves tend to be late in my move ordering.

By the way, I do intend to develop extensive extensions (pardon the alliteration), so please don't reply that I should do extensions instead - I am considering how I will deepen my search once I have explored the extensions.

Title: Re: Scoring partial plys, an alternate approach
Post by nbarriga on Nov 7^th, 2014, 10:20pm

on 10/25/14 at 08:34:46, half_integer wrote:

alpha-beta node count is b^ceil(p/2)

First of all, this only holds assuming perfect move ordering. Worst case is the same as minimax: b^p.
Second, I believe the actual formula is b^ceil(p/2) + b^floor(p/2) - 1

Title: Re: Scoring partial plys, an alternate approach
Post by n00bftw on Nov 8^th, 2014, 12:32pm

I would be cautious of any algorithm that is static with regards to the depth of the tree. Some searches for certain trees and certain move orderings take much longer than others; if you're trying to develop a practical bot, you can't assume anything about how a long a search of a certain depth (P4 as you suggested) will take.

I'd suggest taking a look around and seeing what others have posted on this topic in the forum before trying to design your own approach.

Title: Re: Scoring partial plys, an alternate approach
Post by half_integer on Nov 9^th, 2014, 12:23pm

nbarriga: everything you said is true. I was speaking in informal terms, and should have said something like "on the order of" to cover the clarifications you made.

n00bftw: Your warnings are well taken. Certainly I need to include time management into my bot. However, I thought the ideas discussed could apply to the last two ply regardless of how many actual plies are being done. Or did you mean that you didn't think it is a good assumption that the increase in work multiplier for even plies will be drastically smaller than that for odd plies?

Title: Re: Scoring partial plys, an alternate approach
Post by n00bftw on Nov 9^th, 2014, 2:33pm

As you iteratively deepen, you can limit the steps of the last two moves/plies to 3 if the search depth is at least four moves/plies. If that's what you're planning then that addresses that particular concern I raised.

on 11/09/14 at 12:23:59, half_integer wrote:

Or did you mean that you didn't think it is a good assumption that the increase in work multiplier for even plies will be drastically smaller than that for odd plies?

I wasn't talking about that, but now that you bring it up, and after looking at the top of your post and nbarriga's reply, I agree with nbarriga. I would do an actual node count of your searches for many different positions and get some data before you develop a strategy for a search tree that may or may not be close to what you are assuming it will look like.

Title: Re: Scoring partial plys, an alternate approach
Post by lightvector on Nov 9^th, 2014, 10:41pm

For my bot, I haven't seen a notable difference in behavior in odd vs even plies. Even step-by-step on average it's not too nonuniform. I expect that things deviate a bit from the case you considered in your post when you add in quiescence search and a bunch of various search extensions and pruning. However, this is anecdotal, in that I haven't actually done a measurement or experiment to test this. I simply don't recall noticing such a difference when running my bot to analyze various positions. This could mean that I'm very bad at noticing (possible), or that for my bot, any such effect if it exists is small (likely).

Also, for sharp, "P3", whatever that means, as the depth for the main search (ignoring qsearch) is usually possible at cc time controls, and lesser versions, such as S10 (10 steps) are usually possible at faster time controls. I say "whatever that means" because for quite a long time now, the search has been fairly lopsided with pruning and reduction and extension, so that it's not clear what "P3" or "S10" means any more. Particularly if then you add back in qsearch, which haphazardly tacks on more variation in how deep the search "really" goes.