Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> "Deep Thinking" in bots
        
(Message started by: The_Jeh on Dec 26^th, 2006, 12:52am)

Title: "Deep Thinking" in bots
Post by The_Jeh on Dec 26^th, 2006, 12:52am

From what I understand about creating bots, it appears that they cannot utilize "deep thinking." That is, they cannot think while it is the opponent's turn. Please correct me if I am wrong, or if there is another term for this.

Just curious, how much better do you think bots would play if they could use deep thinking, especially at fast time settings?

The_Jeh

Title: Re: "Deep Thinking" in bots
Post by jdb on Dec 26^th, 2006, 1:09am

Thinking on the opponents time is generally referred to as "pondering".

None of the bots currently ponder. The bot interface reloads the bot's program for each move, so pondering would be tricky to implement.

At the long time settings, pondering would make little difference. At the faster time settings it might, but even then I'm not sure.

The usual implementation for pondering is to the guess the opponents move and start the search as if that move had already been played. So in order to benefit, the opponents move has to be guessed correctly. I have no idea how many times this would happen in a game.

Title: Re: "Deep Thinking" in bots
Post by IdahoEv on Dec 28^th, 2006, 12:46am

Pondering - or even just retaining state between turns - could come in handy just by retaining a part of your hashtable. If you are searching 3 ply deep, you are almost guaranteed to have some of the branches leading from your opponent's move still in your hash table. This could gain you a few extra hash hits in the early parts of your search on the next turn.

Implementing this, or pondering, would require that your getMove program be a separate program from most of your bot, and the getMove program would be essentially an interface layer that communicated with the always-running bot.

Title: Re: "Deep Thinking" in bots
Post by Hippo on Feb 16^th, 2010, 8:05am

Even with very progresive cutting of search tree branches the saved time would be such tiny portion of the subtree to be searched that don't expect big gains of that. It would gain in positions with goal attacks, where the cutting would work well.

Title: Re: "Deep Thinking" in bots
Post by Fritzlein on Feb 16^th, 2010, 8:21am

on 12/26/06 at 01:09:56, jdb wrote:

The usual implementation for pondering is to the guess the opponents move and start the search as if that move had already been played. So in order to benefit, the opponents move has to be guessed correctly. I have no idea how many times this would happen in a game.

My intuition was that one would basically never guess the correct move to think about on the opponent's time, so pondering would be useless. In the Mob game, however, I have been keeping careful track of my guesses for the Mob's moves, and I have been right about one fifth of the time. So perhaps it isn't so useless after all?

Title: Re: "Deep Thinking" in bots
Post by 99of9 on Feb 16^th, 2010, 1:28pm

Opfor now ponders.

I would expect even a bot to correctly predict a few moves in most games. In particular many captures are fairly obvious responses. The downside is that the opponent probably makes those moves quite quickly, so pondering doesn't give you much :).