Implement computer player

[edpegg]

Currently, the computer checks to see if a player has a move, and whether a player has any chance of winning. This could be used as a first step for a (poor) AI for the game.

If a player competes against the computer, it shouldn't count in the Profile record.

A few AI Strategies should be relatively easy to implement.

0. Make a list of possible moves. (currently done)
1. More randomly.
2. Take the highest scoring play.
3. Move to restrict opponents moves. (hard)
4. Gametree search (hard)

Implementing 1&2 only shouldn't be too difficult.

[irilyth]

This is easy for anyone to do, because the computer player can just play via the API. I don't think that it needs to be part of the server at all.

(If someone does write an AI that we want to run on the server, so there's an always-available AI player for people to play against, we can do that; but the initial development work of the AI doesn't require any server-side dev work at all.)

[jl8e]

Somebody should probably see if they can track down lunatic from the old site, and see if BMAI can be made to work on the new one.

Edit: I did some googling, but had no luck.

[cgolubi1]

I actually have a computer player, which i've been boringly calling RandomAI. I use it for regression-testing pull requests. It uses the API to request the game state, then takes a legal move at random. I've thought about setting up an account for it to play on one or both of the live sites, but i don't imagine people would find it very interesting to play against an opponent who takes moves at random, so i haven't bothered. :>)

[edpegg]

Playing a few games against a dumb opponent can be helpful. Also, Computer vs Computer games are interesting. For example, CynCyn vs Kitty Cat Seven, what would happen with 20 Computer vs Computer games?

Should the full games be recorded? Likely not, since thousands / millions of computer games could take up a lot of space. If it's a computer game, some of the results could be discarded.

Instead of http://www.buttonweavers.com/ui/game.html?game=2000, perhaps there could be game=0216v0266 , since Jingjing is 216 and Hannah is 266. The stats for all Jingjing vs Hannah games would be listed.
PvP PvC CvC-Random CvC-Greedy 2/3/0 - 1 0 3/0/0 - 27 3/1/0 - 10 2/3/0 - 4

[irilyth]

I feel like we've had a couple of contexts where the idea of marking a game as "special" in one way or another has come up. The "misere" idea, so games that you're trying to lose don't get mixed in with stats played between buttons that are trying to win; computer vs computer games; and probably others. Is there a general ticket about that sort of thing? I thought there was something about game flags, but now I can't find it.

[cgolubi1]

On Thu, 05 Mar, 2015 at 09:50:41 -0800, edpegg wrote:

Playing a few games against a dumb opponent can be helpful. Also, Computer vs Computer games are interesting. For example, CynCyn vs Kitty Cat Seven, what would happen with 20 Computer vs Computer games?

Should the full games be recorded? Likely not, since thousands / millions of computer games could take up a lot of space. If it's a computer game, some of the results could be discarded.

Yeah, my approach to this would be to play a bunch of games offline using a sandbox copy of the site, and just report the results if they were interesting. Anyone with a little bit of Linux-y experience can do this --- relatively speaking, it's pretty easy to stand up a sandbox copy of the site using vagrant and VirtualBox.

I don't know how much those head-to-head stats are worth... philosophically, the idea of assessing how a button does when played naively is appealing. Is "naively" the same as randomly? Off-the-cuff, i feel like if you're doing what RandomAI does (pick a type of attack at random from the options, then pick a legal implementation of that attack type at random), then adding a trip die to a recipe will make its random use stat weaker, because it will sometimes choose to do a trip attack when its value is already higher than the defending (non-poison, let's assume) die, which no human player would do. And that's probably incorrect --- having an extra skill should make a button better (you can argue about trip because of the initiative effect, of course, but i bet with a little more thought someone can come up with an example which is inarguable).

(But "don't choose stupid attacks" is subjective, and also contrary to my personal goals with RandomAI, according to which useless trip attacks are great because we find a lot of bugs involving trip attacks. :>)

[irilyth]

It probably wouldn't be hard to turn the RandomAI code into something like GreedyAI, which would make whatever attack improved its situation the most (from a "how many sides ahead/behind am I" perspective), with zero thought of the future. It wouldn't be very good, but it probably wouldn't be awful.

I wonder also whether the BMAI algorithm could be easily plugged in to the new site's client framework; my recollection is that it was pretty good, won like 2/3 of its games, although I don't know how much of that was against serious human players (but I think most of it was).

[blackshadowshade]

irilyth, #1519 was about Misere games, #347 was about marking games as broken, #533 was about implementing button tags. None of these are directly about generally labelling games as we wish, but they're all somewhat related.

[TheOrgg]

BMAI's code:

BMAI_1_0.ZIP

This was with the archive of the old BMO site I got from Dana.

[blackshadowshade]

Ah, it's in C++ and Perl! That shouldn't be awfully difficult to get running, if someone wanted to do that.

[blackshadowshade]

Let me bring attention to the last two points of the software agreement for BMAI:

5. LICENSE AGREEMENT

By using or modifying the contained source code, you agree to the following terms:

a) You are hereby granted license to use and modify the contained source code.

b) You are not permitted to sell or otherwise use the source code (or modified source code) for commercial means, without consent of the original author.

c) You are not permitted to distribute the source code (or modified source code), without consent of the original author.

d) The original author must be acknowledged in derivative works.

e) You will not use the source code (or modified source code) to assist you in playing online against other human players, without notifying your opponent that you have this advantage.

f) You will not use the source code (or modified source code) to have an AI player play other players (whether online through a BM web site or through other means), without posting a notice or otherwise indicating that the player is an AI.

6. CONTACT INFORMATION

For any questions, comments, or submitting improved versions -

Denis Papp denis@accessdenied.net http://www.accessdenied.net/bmai

[TheOrgg]

My bad. I never opened the .zip. Delete it if you feel it needed.

[jl8e]

I think point c is more relevant

Also, we have an email address

[danlangford]

i reached out to denis, hopefully not spamming him too much but I noticed another email online that seemed to be more current. i didnt know if others were also reaching out. this is part of his response:

Thank you for your interest in the BMAI. I am curious - could you send me what you have? I might post it on github, and would like to compare it against the last version of the source code that I actually have. I have an archive that looks like what may have been released around October 2001, and I just ran a diff against the latest code I have which has changes up to late 2005 (a sort of "version 3"). Clearly, that would be much better to use.

i replied with a link to this issue link and the zip file attached.

[blackshadowshade]

Always nice to keep in touch with members of the community who haven't made it back.

[pappde]

Hi everyone, I am the author of the BMAI. Dan Langford sent me an email making me aware of the interest. The last update that was made to BMAI was in 2005, effectively a V3.0. I will go ahead and post the last version of the code so that you may go ahead and use it.

For reference, here are some of the changes to the AI since the "1.0" release. // drp102801 - release 1.0 // drp111001 - support for FOCUS // drp111401 - support for WARRIOR (Sailor Moon) // drp032502 - support for SLOW (Brom - Giant) // drp033002 - support for UNIQUE (2000 Rare Promo) // drp033102 - moved to BMAI2 (with culling, ply 3) // - TRIP illegal if can't capture (i.e. one die tripping two) // drp040102 - website now live (www.buttonmen.com) // - more BMAI2 improvements // drp062702 - BMAI2: improvements with TRIP and bad situations // drp062902 - better RNG // - fixed dealing with TWIN that are MIGHTY/WEAK // - BMAI2: surrenders if no move seems to result in a win // - BMAI2: fixed movelist leak in CullMoves() // - BMAI2: culling for preround (swing/option) // drp063002 - Added performance stats // - BMAI: fixed major bug where ply3+ BMAI/BMAI2 was not working // - BMAI3: replaces BMAI2, major change (for attack actions) to use next ply for more accurate move scoring. // Instead of playing out the sim and assigning a score of -1/0/+1 it uses the estimated P(win) of the next ply action. // drp070202 - m_min_sims/m_max_sims. Previously the min was 20 now the default is 5. // - apply decay to min/max sims [currently hard-coded] // - BMAI: apply max_branch to UseChance() and Reserve() // drp070502 - GenerateValidChance() // - BMAI3: apply move culling to GetUseChance(), GetUseFocus() // - BMAI3: use accurate move scoring on preround moves // drp070602 - Stats: BMAI3 average moves/sims per ply // drp072102 - support for UNSKILLED (The Flying Squirrel) // drp082802 - support for STINGER (set Diceland) // drp092302 - ignore setswing action if have no swing dice (useless ply) // - AI::GetSetSwingAction() did not work with more than one swing type (but only used with ply 1 AIs) // drp022203 - MoveList: reserve space for 32 instead of 16 moves. Also use store Move objects instead of pointers // so that we cut out the extra allocs (if using pool, we would want to use pointers) // - BMC_Move: cut from 32b to 24b by replacing m_option_die with a BitArray<> // - BMAI3 SetSwing: catch case where the number of moves is too huge [Gordo] by randomly cutting out moves // drp071005 - changed unskilled from "k" to "~" (for Konstant) // - added basic support for Konstant // drp071305 - konstant: don't reroll (not done yet) // - fixed memory trasher with turbo swing // drp071505 - fixed UNIQUE check (mattered), fixed OPTION check (didn't matter) // drp091905 - BMAI3 Focus/Chance: "pass" moves were being mis-evaluated (scoring from POV of opponent) so // the AI would almost always pick "pass". Now pass "pov_player" to EvaluateMove() functions. // This was a big problem and explains the 42.4% with "Legend of the Five Rings" or // 46.7% with Yoyodyne,

[pappde]

I have posted the last version of the source code to github: https://github.com/hamstercrack/bmai

Please feel free to use and modify this as you need.

[blackshadowshade]

Many thanks, @hamstercrack!

Hope to see you visit the site some time, even if you don't want to get beaten up. :)

[danlangford]

@hamstercrack i will likely take a look at this, maybe update the vcproj to the latest version, maybe make some adjustments so it can be compiled cross platform. if i do any of that sort of stuff do you want me to submit PRs to you or are you just not interested in spending much time on it at this point?

[blackshadowshade]

Remember that it'll need adjustments to work with our API too.

[danlangford]

I got it compiled. I don't have it "hooked up" to our current site however I do have it able to suggest a "best move" and play out a game that I manually configure into it. reminds me of xboard/winboard/cecp!

[pappde]

@hamstercrack i will likely take a look at this, maybe update the vcproj to the latest version, maybe make some adjustments so it can be compiled cross platform. if i do any of that sort of stuff do you want me to submit PRs to you or are you just not interested in spending much time on it at this point?

I'm all for seeing it updated, so will pull in any commits you have (at least to a branch). I likely won't be reviewing the changes, so it will quick.

Also, feel free to send me any questions about the code. If I can quickly answer it if it will save you some investigation or trial and error time.

[jl8e]

Remember that it'll need adjustments to work with our API too.

Fortunately, it looks like one would just have to replace the perl with something, probably in python (because the code already exists), that speaks to the api and talks to bmai.

[jl8e]

An interesting question is how much more aggressive it can be in search depth on a modern machine. (Of course, to take full advantage, it'd need to be multithreaded or multiprocess.)

[pappde]

It actually had pretty good results thinking quickly on an old computer (60% win rate, one of the top players). The parameters related to the search effort are:

• ply - how deep
• maxbranch - hard max on how many simulations to run
• max_sims - how many simulations to run per move (I think)

The advantage of a faster CPU is that you can increase both how deep (to minimize having to rely on a heuristic for expected win without simulations) and how many simulations (to get a more accurate scoring of each move). While it is only single-threaded, these numbers can still be raised, though not sure how much.

Wouldn't be hard to parallelize but honestly, unless you want to "solve" button men or create a world champion, I expect it's good enough. Probably wouldn't be too fun playing against an optimal player.

The main effort I see in the AI is making sure all of the different dice types are supported.

[TheOrgg]

It would be cool to have a moderate (Nala), Hard (BMAI) and Master (BMAISTER?) level AIs to play against.

[danlangford]

i made a lot of progress and am getting close to being able to have BMAI monitoring games and making moves. if i did, would you want me to use the account BMAI? or should i create a new account BMAIBagels (since i am Bagels over on the play site) that i use for testing and someday this will be something that can run for permanently and then you will use BMAI?

[pappde]

It seems like a good idea to have multiple different AIs/accounts to play against as suggested earlier. Initially they could simply vary based on strength using the tweakables, but eventually some personality (e.g. perhaps some weightings to favor certain type of dice or strategies). Meantime, having a default one for testing per your suggestion makes sense, call it whatever you like (though it is nice to have "bmai/BMAI" in the name somewhere).

I currently don't have a plan to go back to working on BMAI, so you should feel free to make any changes/enhancements. It's awesome that you are going through this effort, and it would be great if I get the chance to jump back into it someday. I'm still a big fan of Button Men and look forward to playing on the new site. It would be great to see other online gaming sites like BGA get AIs too :)