|
||
|
Title: quarterplies Post by tangentstorm on Aug 11th, 2011, 6:19am Hey all. Here's a newbie AI question: Has anyone tried making a bot that pretends you only get one step (or one push/pull) per turn instead of four? It seems to me that this would reduce the search space considerably and thus allow looking much deeper into the game tree, at the expense of tunnel vision -- discarding moves that exploit the opponent's inability to counter each step immediately. But: it may be that there are still plenty of strong moves left over. So the bot would evaluate each possible step (counting any legal push/pull combination as one step), then evaluate the opponent's best possible step, and so on. Then it would batch the results into a normal 4-step move. I'm trying to imagine how such a bot would play. On the one hand, it might be very cautious, because it only chooses moves that would stand up to a barrage of immediate counters, but it might also overlook all sorts of dangers from a regular opponent, playing with the full set of available moves. (Perhaps you could have a hybrid system, where the bot evaluated single steps for its own side, interspersed with full moves for the opponent.) Did that make any sense at all? And if so... what do you think? |
||
|
Title: Re: quarterplies Post by rbarreira on Aug 11th, 2011, 7:00am Trying to reduce the search space is definitely a good thing, but eliminating all 3 and 4 step moves, plus some of the 2 step moves is definitely going too far. I never tried it, but the simple fact that it would be blind to simple tactics like flipping a piece is enough to cause big problems. It would be interesting to see a bot playing like that, and also the "hybrid" variety that you talked about. |
||
|
Title: Re: quarterplies Post by Fritzlein on Aug 11th, 2011, 12:19pm on 08/11/11 at 06:19:05, tangentstorm wrote:
It seems like the big problem here is steps that are dependent on each other. For example, suppose the best turn is to play elephant forward four steps. That can't be built up out of four step from the base position. The best I can do is move my elephant one step plus three other steps that would also be legal from the base position. Also, many immediate captures require all four steps, usually two back-to-back dislodgements. Often if you do only half a capture, only the first dislodgement, then the opponent will have a defense to capture. So allowing the opponent to respond mid-turn could make it look like a capture is impossible when it is in truth immediate. |
||
|
Title: Re: quarterplies Post by Manuel on Aug 12th, 2011, 4:11am Actually, I think your basic premise is incorrect. By considering only one step per move, you are not going to look deeper into the game tree. Yes, you will be looking deeper in number of moves per player, but not in number of steps per player! A player cannot reach deeper goals in a high number of moves than in a low number of moves containing the same total number of steps... A more promising idea could be to do the opposite: Give the first player more than the normal four steps, evaluate these positions and choose the best ones, and then see which best evaluated positions cannot be messed up by the opponent in the discarded intermediate turn. This way you could do a 3-ply search with the effort of only 2-ply-and-a-bit, and so on. But as the opponent can probably mess up most of the positions, this idea may be not so easy to make as efficient as it sounds... |
||
|
Title: Re: quarterplies Post by tangentstorm on Aug 12th, 2011, 8:08am I think you guys are right: this idea ignores too many fundamental moves. Back to the drawing board. :) |
||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |