Author |
Topic: OpFor (Read 7069 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
Janzert, it is great to see bot_OpFor up and playing! A bot in the gameroom is worth two on the drawing board. Perhaps you were reluctant to talk much about your bot while it was still hypothetical, but I'd love to hear more about it now that it is real.
I note that OpFor is stronger than Occam out of the gate, at least it appears so from beating ShallowBlue where both were averaging 0.10 minutes per move. In the 2007 CC, Omar had Occam play just to make the field an even eight, so without going any further OpFor is already better filler material...
I'm quite curious what you are doing the same as or different than other developers before you, if you have time for sharing between bouts of coding.
|
|
 IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
 |
Re: OpFor
« Reply #1 on: Dec 18th, 2007, 4:03pm » |
 Quote  Modify
|
I hope OpFor can play the Owl Tournament. That is, only if I can beat it.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #2 on: Dec 18th, 2007, 4:37pm » |
Quote Modify
|
OpFor is using pretty much just basic standard techniques. At the moment this means straight up iterative deepening alpha-beta search, a few simple positional evaluations mostly implementing the easy to do parts of fotland's description of bomb's eval, a very primitive goal search and FAME for material eval. Already written but not yet integrated is also a trap search. But next thing on the todo list is some real time management. Most of the current games have simply been P1 search (the very first one was 6 step search with tournament rule game endings).
This is actually the around the 5th implementation of the core engine for a bot I've finished. The first one I wrote on my own was pretty horrible, the later ones have benefited greatly from my browsing of (mostly in historical order I think) Don Dailey's sample bot, Jeff Bacher's Clueless, Ola Hansson's Fairy and David Fotland's descriptions here of Bomb. Thanks to all for releasing these and I hope to do the same in the future.
My goal is to get OpFor somewhere in the vicinity of Clueless' or Bomb's strength and then, as the name suggests, use it as the opponent locally for bots based on more experimental techniques.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: OpFor
« Reply #3 on: Dec 19th, 2007, 12:23pm » |
Quote Modify
|
This is a reply to a game comment, but it seemed like more general discussion that should go in the bot developer thread, not in game comments that quickly scroll off. How much discussion of the development of Bomb is effectively lost since it occurred in game comments that nobody can find any more?
Quote:Right, after making the initial comment last night I realized this. So instead of changing goal threat evaluation any more I started adding a term for pieces on unsafe traps. But then came to the realization that the quiescent search should take care of these problems once added.
So I left things alone for now and started back in on time management where I should have been in the first place.  |
|
Yes, quiescence search until no one-move captures remain is surely more important than having the evaluation penalize pieces on trap squares. In fact, 99of9 convinced me that sometimes pieces on traps squares make the trap safer! I think Gnobot is the only bot that uses this strategy, though.
I would argue that quiescence search is more important than time management as well. I have a hunch that the bot that eventually wins the Challenge will not do so by excellent evaluation, but rather by excellent selection of which lines need to be examined more deeply than others. Capturing moves are an obvious place to start selective extensions, and one that can be done efficiently (with decision trees, as Fotland showed us).
Imagine, though, if bots could quickly choose 30 "moves that need to be looked at" from _every_ position, whether captures are available or not. The branching factor problem disappears, and poof, computers dominate Arimaa.
|
| « Last Edit: Dec 19th, 2007, 12:26pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #4 on: Dec 19th, 2007, 2:15pm » |
Quote Modify
|
I'm probably mis-communicating my meaning of time management.  I don't mean anything fancy, I mean anything at all. Currently the bot will only search to a fixed depth (or infinite depth) and even that is a hardcoded number that requires a recompile to change. So to even enter the championship I'm pretty sure I have to get something done. No it probably won't be very fancy, elegant or good either.
Btw, when I said nascent I really do mean it is just barely developed and functioning. The first alpha-beta search (without even a transposition table) was only finished at the beginning of November.
Janzert
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #5 on: Dec 20th, 2007, 7:11pm » |
Quote Modify
|
Emergency stop right now and send a move before timing out implemented.
And yay it let's it just barely beat bombP1 when searching 10 steps or run out of time deep.
Janzert
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #6 on: Dec 21st, 2007, 1:37pm » |
Quote Modify
|
Here is a slightly condensed commit log for my current iteration of bots.
Janzert
------------------------------------------------------------
revno: 1
timestamp: Fri 2007-08-31 16:23:29 -0400
message:
Initial import
------------------------------------------------------------
revno: 10
timestamp: Wed 2007-09-19 12:51:09 -0400
message:
add copy method to steps
rename random move bot
create random step bot
------------------------------------------------------------
revno: 15
timestamp: Thu 2007-09-27 13:48:58 -0400
message:
Arimaa score p1 bot
------------------------------------------------------------
revno: 19
timestamp: Thu 2007-10-04 20:40:06 -0400
message:
Added FAME scoring
Various fixes. UCT still plays much better as gold.
------------------------------------------------------------
revno: 24
timestamp: Sat 2007-11-03 02:48:36 -0400
message:
Initial alpha beta bot work
------------------------------------------------------------
revno: 25
timestamp: Sun 2007-11-04 23:31:24 -0500
message:
Minimally working alpha beta bot.
Fix some memory leaks.
------------------------------------------------------------
revno: 26
timestamp: Tue 2007-11-06 11:59:07 -0500
message:
Add transposition table to alpha beta
Create caching FAME eval fastFAME
------------------------------------------------------------
revno: 27
timestamp: Wed 2007-11-07 11:46:44 -0500
message:
Add History heuristic.
Do some top level move ordering.
Make the search run incrementally.
------------------------------------------------------------
revno: 28
timestamp: Fri 2007-11-09 15:27:33 -0500
message:
Some positional evaluation.
More various stats recorded.
------------------------------------------------------------
revno: 29
timestamp: Mon 2007-11-12 17:20:10 -0500
message:
More positional evaluation work.
Infinite analysis support in alpha-beta bot.
------------------------------------------------------------
revno: 30
timestamp: Fri 2007-11-16 21:25:19 -0500
message:
Beginnings of a goal search
------------------------------------------------------------
revno: 31
timestamp: Mon 2007-11-19 00:26:48 -0500
message:
Add goal search to alpha beta bot
------------------------------------------------------------
revno: 32
timestamp: Fri 2007-11-23 12:02:27 -0500
message:
Correct bug allowing pulls after a push step
------------------------------------------------------------
revno: 34
timestamp: Wed 2007-11-28 00:17:03 -0500
message:
Initial capture move generator
------------------------------------------------------------
revno: 35
timestamp: Fri 2007-11-30 13:23:15 -0500
message:
Split alphabeta search class out from bot_ab
------------------------------------------------------------
revno: 37
timestamp: Thu 2007-12-13 10:09:48 -0500
message:
Encapsulate transition table handling.
Change transition table replacement to greater depth only.
Small bug fixes and cleanups.
------------------------------------------------------------
revno: 38
timestamp: Tue 2007-12-18 01:17:27 -0500
message:
Rename bot_ab to bot_opfor
------------------------------------------------------------
revno: 39
timestamp: Tue 2007-12-18 17:50:06 -0500
message:
Add support for casual play game end rules (no rabbit capture win)
Make goal search evaluation better handle multi move threats
------------------------------------------------------------
revno: 40
timestamp: Wed 2007-12-19 15:29:22 -0500
message:
aeibot.d:
Add UnknownCommand exception to aeibot interface
bot_opfor.d:
Clean up the aei score reporting
Adjust goal search weighting
Reduce trap safety weight
------------------------------------------------------------
revno: 41
timestamp: Wed 2007-12-19 18:00:05 -0500
message:
Handle go ponder and goal by ignoring them
------------------------------------------------------------
revno: 42
timestamp: Thu 2007-12-20 00:29:09 -0500
message:
Add aei setoption command
Get rid of several aei go command modifiers
Add ability to set search depth through 'setoption depth'
------------------------------------------------------------
revno: 43
timestamp: Thu 2007-12-20 00:45:18 -0500
message:
Fix bot_score to handle setoption
------------------------------------------------------------
revno: 44
timestamp: Fri 2007-12-21 00:15:43 -0500
message:
Add aei stop command and bot_opfor handling of it
------------------------------------------------------------
revno: 45
timestamp: Fri 2007-12-21 04:29:37 -0500
message:
Add timecontrol information to bot_opfor. Now just need to do something with it.
------------------------------------------------------------
revno: 46
timestamp: Fri 2007-12-21 14:08:31 -0500
message:
bot_opfor: Switch dog and horse placement in opening setup
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: OpFor
« Reply #7 on: Dec 21st, 2007, 2:26pm » |
Quote Modify
|
Thanks for the interesting detail.
You had mentioned writing a learning bot long ago that bombed, but I didn't know you had also written a UCT bot. Was your experience the same as JBD's, namely that it flung rabbits forward to their doom because a random defense might let them through?
I see you implemented FAME early on, despite its known shortcomings. That reminds me to take another pass at improving FAME some day.
I note the dog/horse setup placement comment. That makes me suspect that there would be utility in completely randomizing the setup while testing. You are surely still at a stage of finding out in general terms about OpFor's abilities, which is hindered by always giving it the same puzzle to solve. Different bugs might manifest under different stresses. Giving OpFor an ideal setup seems like an improvement to maximize winning chances (e.g. for the tournament), rather than a good way to test/learn.
Of course, this comment reflects my own journey in gradually becoming willing to experiment in order to learn even if it hurts my winning chances. My recent drubbings at chessandgo's hands have taught me more than I learned in twice as many "safe" victories in the past.
|
| « Last Edit: Dec 21st, 2007, 2:28pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #8 on: Dec 22nd, 2007, 1:31pm » |
Quote Modify
|
on Dec 21st, 2007, 2:26pm, Fritzlein wrote:Thanks for the interesting detail.
You had mentioned writing a learning bot long ago that bombed, but I didn't know you had also written a UCT bot. Was your experience the same as JBD's, namely that it flung rabbits forward to their doom because a random defense might let them through? |
|
I didn't actually get very far with the UCT bot. What little I saw did seem to like advanced rabbits though yes. After playing with it for a little bit I decided I really needed to write a regular alpha-beta bot for an opponent and hence the development of bot_opfor. UCT is certainly something I want to go back and experiment with some more.
Quote:| I see you implemented FAME early on, despite its known shortcomings. That reminds me to take another pass at improving FAME some day. |
|
Well it's still better than any static piece evaluation I'm like to put together and since I'd already implemented it twice (javascript and python) a third time was pretty easy.
Quote:| I note the dog/horse setup placement comment. That makes me suspect that there would be utility in completely randomizing the setup while testing. You are surely still at a stage of finding out in general terms about OpFor's abilities, which is hindered by always giving it the same puzzle to solve. Different bugs might manifest under different stresses. Giving OpFor an ideal setup seems like an improvement to maximize winning chances (e.g. for the tournament), rather than a good way to test/learn. |
|
Random or at least semi-random setups would probably be a good idea for testing. Right now the setup is simply a string with the setup predefined and making sure that the silver elephant doesn't end up straight across from the gold one. The impetus to flip-flop the horse and dog was just having watched a game where the horses ended up not being moved at all till into the endgame while the dogs almost immediately got moved up to be next to the trap then used further from there. So it seemed worthwhile to change 10 characters to encourage the use of the horses in the games. 
Quote:| Of course, this comment reflects my own journey in gradually becoming willing to experiment in order to learn even if it hurts my winning chances. My recent drubbings at chessandgo's hands have taught me more than I learned in twice as many "safe" victories in the past. |
|
Yes, hopefully I don't develop a 'fear' of letting the bot lose games. That would certainly hurt development.
One thing I'm trying to be a bit careful of is not getting the bot to 'do the right thing' for the wrong underlying reason.
Thanks for the comments,
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: OpFor
« Reply #9 on: Dec 22nd, 2007, 2:09pm » |
Quote Modify
|
on Dec 22nd, 2007, 1:31pm, Janzert wrote:| One thing I'm trying to be a bit careful of is not getting the bot to 'do the right thing' for the wrong underlying reason. |
|
For example, you are being careful not to get OpFor to use its horses rather than its dogs (right thing) merely by having the horses conveniently located in the opening setup (wrong reason)?
Quote:
You are welcome. I enjoy speaking at length on topics about which I know little. Thank you for sharing your project progress so I have the opportunity.
|
| « Last Edit: Dec 22nd, 2007, 2:09pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #10 on: Dec 22nd, 2007, 2:34pm » |
Quote Modify
|
Ok, guilty. My excuse is that at the moment I wasn't considering the setup to be part of the bot's 'reasoning' since it's just a static setup.
Janzert
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #11 on: Dec 24th, 2007, 3:07pm » |
Quote Modify
|
Basic time management that should work fairly decent with any time control is finished. Although I'll need to do something more for postal games where it shouldn't actually run the whole time. It also may not do particularly well with time controls that have a low percent of unused time applied to the reserve, but I don't think those have been used much anyway.
Janzert
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: OpFor
« Reply #12 on: Dec 26th, 2007, 12:31am » |
Quote Modify
|
How did you come up with the name "OpFor?" It is a programming term, I suppose?
That makes me wonder at the names of other bots. Here are my guesses, but please correct me if I'm wrong:
Bomb - perhaps a martial symbol of power or a pop-culture verb meaning "to fail abjectly," but more likely a programming term referring either to a system crash or a piece of code that is dormant until triggered (which would be appropriate given bot_Bomb's features)
Clueless - a humorous self-description
GnoBot - uses root of the word gnosis, meaning "special knowledge"
Aamira, Arimaalon, Arimaazon, Arimaazilla, Arimaanator - plays on Arimaa
ShallowBlue - parody of the chess computer Deep Blue
Loc - abbreviation for the computer term "lines of code"
Occam - name of a programming language
|
| « Last Edit: Dec 26th, 2007, 12:52am by The_Jeh » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: OpFor
« Reply #13 on: Dec 26th, 2007, 1:02am » |
Quote Modify
|
on Dec 26th, 2007, 12:31am, The_Jeh wrote:| How did you come up with the name "OpFor?" It is a programming term, I suppose? |
|
Nah it's military in origin. See Opposing Force on wikipedia.
Quote:| Occam - name of a programming language |
|
Don't really know, but always thought this one came from Occam's razor
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: OpFor
« Reply #14 on: Dec 26th, 2007, 7:07am » |
Quote Modify
|
on Dec 26th, 2007, 12:31am, The_Jeh wrote:| Loc - abbreviation for the computer term "lines of code" |
|
I was persuaded Loc derived from from "loco", meaning crazy, is indicated by its playing style. BlackKnight, however, explained that it derived from "location", and had to do with the way moves were generated by piece location.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print