Author |
Topic: "Deep Thinking" in bots (Read 1400 times) |
|
The_Jeh
Forum Guru
Arimaa player #634
Gender: 
Posts: 460
|
 |
"Deep Thinking" in bots
« on: Dec 26th, 2006, 12:52am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: "Deep Thinking" in bots
« Reply #1 on: Dec 26th, 2006, 1:09am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: "Deep Thinking" in bots
« Reply #2 on: Dec 28th, 2006, 12:46am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: "Deep Thinking" in bots
« Reply #3 on: Feb 16th, 2010, 8:05am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: "Deep Thinking" in bots
« Reply #4 on: Feb 16th, 2010, 8:21am » |
Quote Modify
|
on Dec 26th, 2006, 1:09am, 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?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: "Deep Thinking" in bots
« Reply #5 on: Feb 16th, 2010, 1:28pm » |
Quote Modify
|
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  .
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print