57 coaches online • Server time: 11:46
Forum Chat
Log in
Recent Forum Topics goto Post Speccing and Playing...goto Post Southern Wastes Leag...goto Post Theory-craft League
SearchSearch 
Post new topic   Reply to topic
View previous topic Log in to check your private messages View next topic
Traul



Joined: Jun 09, 2013

Post   Posted: Jul 18, 2019 - 03:15 Reply with quote Back to top

Thoralf's links are pretty good for reviewing the different notions of complexity. BloodBowl is pretty simple in terms of tree size. The problem is the state size, and the number of initial states that all lead to different trees. That would affect the size of the network needed to process the game state. Besides, go and chess are stationary games where the actions are the same in each state, whereas BloodBowl is full of mini-decisions (use skill X? Follow-up after block?) Finally, the game must be simulated during training, so the complexity of coding a trainer would be at least as high as that of coding the client, and any bug could invalidate training results.

On the bright side, Fumbbl probably has more than enough data to kickstart the training. Instead of looking for the best BloodBowl coach ever, one can first train a typical coach by asking it to reproduce the existing replays on the site. This is several orders of magnitude easier than the alternative of having the bot try all kinds of stupid moves against itself until it lucks into something that works.
Amon242



Joined: Aug 02, 2003

Post   Posted: Jul 18, 2019 - 04:24 Reply with quote Back to top

Frog Hack for the AI if anyone wants it

10 Stand Up all players not moving
20 Move all players not blitzing or dodging
30 Blitz player with ball
40 Recover Ball
50 Pass Ball
60 Score TD
70 END
**h4x3 bY aM0n242**
thoralf



Joined: Mar 06, 2008

Post   Posted: Jul 18, 2019 - 04:27 Reply with quote Back to top

MenonaLoco wrote:
BB ai is way more complex than go ai.

My own intuition is that strategical concerns in Go are on a whole different level. It took a really big computer to beat grandmasters. An architecture of more than 1000 CPUs isn't cheap, whereas your smart phone would be banned in Chess tournaments. To give you an idea, a Chess engine can calculate more than a million nodes per second on an ordinary comp. That's a lot, more than enough to find the best one-turn setups in less time that it takes us to recall how to chain push properly. Yet it requires an opening book and endgame tablebases to be competitive.

Still, building a BB program is no trivial task. Classical chess engines (AlphaChess is another kind of beast altogether) require, among other things, an evaluation function that takes material, pawn structure, piece activity, King safety, and positional features into account. It should be possible to find something similar in BB for ball safety, defensive positions, contacts, tactical shots, etc.

Most of the time the BB engine would try to minimize risks while optimizing rewards. Playing safe and sound moves does not require that much. What's hard are the tactics. BB tactics are not trivial, but they are uncertain. Which leads me to my basic point. It makes little sense to calculate long lines when the first fail ends your turn. Which means that the BB engine might end up choosing almost randomly amongst many moves that are more or less equivalent.

That point remains theorical, as the man-hour required is lightyears away from building a BB GUI. Until it attracts real research interest, let's not hold our breath.

_________________
There is always Sneaky Git.


Last edited by thoralf on Jul 18, 2019 - 04:36; edited 2 times in total
Wozzaa



Joined: Apr 23, 2016

Post   Posted: Jul 18, 2019 - 04:31 Reply with quote Back to top

Did anyone see this blog?

_________________
Image
thoralf



Joined: Mar 06, 2008

Post   Posted: Jul 18, 2019 - 04:35 Reply with quote Back to top

\o/

_________________
There is always Sneaky Git.
mister__joshua



Joined: Jun 20, 2007

Post   Posted: Jul 18, 2019 - 07:46
FUMBBL Staff
Reply with quote Back to top

I feel people are conflating very different things here. A dumb ‘bot’ AI like we see in BB2 would be quite difficult to program to the point it was good at the game, which is why BB2 doesn’t have a great single player experience. Grod is making a decent stab at this from what I read.

The AI they use to play Go and Chess teaches itself using reinforced learning to play the game against itself millions of times over a few days. One of these would absolutely be the most optimal BB player in the world in just a few days, though it still wouldn’t always win due to random elements. The point is moot though as we don’t have DeepMind and hundreds of millions of dollars.

_________________
"Yeah, well, you know, that's just, like, your opinion, man." - The Dude

Mr. J's LRB7 / Forum
delusional



Joined: Jan 18, 2013

Post   Posted: Jul 18, 2019 - 08:23 Reply with quote Back to top

I think BB has needed a Dumb 'bot' option for ages.
The BB2 AI, well it could get an idea but yes it did not seem to want to score.
Would love to code an AI where it could get a +50% win rate on here. I fear the good players would still kick it.
Chivite



Joined: Sep 04, 2017

Post   Posted: Jul 18, 2019 - 10:19 Reply with quote Back to top

delusional wrote:

Would love to code an AI where it could get a +50% win rate on here. I fear the good players would still kick it.



Making good use of the user name i see! Laughing
Mnemon



Joined: Aug 02, 2003

Post   Posted: Jul 18, 2019 - 11:44 Reply with quote Back to top

mister__joshua wrote:
The AI they use to play Go and Chess teaches itself using reinforced learning to play the game against itself millions of times over a few days. One of these would absolutely be the most optimal BB player in the world in just a few days, though it still wouldn’t always win due to random elements. The point is moot though as we don’t have DeepMind and hundreds of millions of dollars.


Ye - I mentioned the manhours in passing up there. Neither really is realistic unless people really put in some funding for someone to focus on that for a good long time - and even then nothing useable might come out of it. That said - it wouldn't need to reach DeepMind levels of sophistication to be useful as a bot - or even attempt to get to the level of mastery.

DeepMind isn't about making an AI that is good at playing a specific game; that's more of a training excercise for different long-term aims.
PeteW



Joined: Aug 05, 2005

Post   Posted: Jul 18, 2019 - 11:48 Reply with quote Back to top

I thought this had been done already? Wasn't Woodstock a bot? Laughing

_________________
"Jesus loves me this I know, 'cos my Bible tells me so." MrMojo - where did you go?
koadah



Joined: Mar 30, 2005

Post   Posted: Jul 18, 2019 - 12:42 Reply with quote Back to top

delusional wrote:
I think BB has needed a Dumb 'bot' option for ages.
The BB2 AI, well it could get an idea but yes it did not seem to want to score.


It would at least provide some entertainment if it understood that the closer you get to the end of that half, the more you need to prioritise getting to the end zone.

Some of the stuff it does isn't that bad. But if it is not trying to score then it isn't really playing the game.

_________________
Image
O[L]C 2016 Swiss! - April ---- All Stars - Anniversary Bowl - Teams of Stars - 13th March
JellyBelly



Joined: Jul 08, 2009

Post   Posted: Jul 18, 2019 - 12:47 Reply with quote Back to top

I agree with madvig. The main problem with chess AIs isn't making one that can beat a human - that's easy. It's making one that is just the right level of challenge. All the ones I've seen tend to flip very quickly from trivially easy to practically impossible, as you increase the difficulty.

_________________
"Opinions are like arseholes, everybody's got them and they all stink." - The protagonist, Fallout 2

"Go for the eyes, Boo! Go for the eyes!!" Razz
Nelphine



Joined: Apr 01, 2011

Post   Posted: Jul 18, 2019 - 17:57 Reply with quote Back to top

For ai difficulty, I've always endorsed providing a 'menory score'.

Design an AI that always plays optimally, but then have it ignore certain details. For blood bowl, you'd have 3 sections to this:

Each skill and stat would have a score. Something like block would be 100%, bit remembering that MA10 allows really easy one turns would be a bit less. Very rarely used skills like pass block or disturbing presence or throw teammate would be a bit less. Each run, roll against each skills or stat and if you fail, ignore that skill or star for optimal move selection.

Second each player would also have a memory for easy of its skills stats and action options. Remembering a blitzer has block and blitz action be 100%, remembering the rookie saurus can take a Dodge action and 2 gfi's might be less. Remembering that the human catcher has STR 4 might be less. Things like weather would also be in here.
This would be further modified by whether it's the AI player or the opponent player.

And a third section would be a difficulty or personality modifier. A rookie AI might 'forget' that a blitzer has block, or that GFI can fail (or that GFI is possible). A legend ai might never forget throw teammate or pass block. Etc. A passing ai might forget the hand off option exists if the pass option is available.


Last edited by Nelphine on Jul 19, 2019 - 04:33; edited 1 time in total
thoralf



Joined: Mar 06, 2008

Post   Posted: Jul 18, 2019 - 18:52 Reply with quote Back to top

Team management is indeed another task. Two AI could be needed. One would be the BB coach, the other would be the BB owner.

I'd like to hammer home the point about optimality. Suppose the AI needs to attack a cage. It sees a few ways to do so. Let's say 5 with a similar best score. Nevermind how it proceeds to choose for the moment. Ask yourself instead - how would it matter?

In other words, I duly submit it would be incorrect to presume that Blood Bowl is a game where seeking the optimal path matters most of the times. Micromanaging thousandths of percent may not make any difference in the end. At best you get a depressing AI against whom you win one game out of three (or four). These would be good odds compared to a Chess engines, whom are *really, really* good. Non-dedicated amateurs stand virtually no chance.

Check the ratings. Unless Fumbbl has yet to see true BB grandmasters, BB has obviously less skill than other games. That's what I like most about it. Always losing is boring. Always winning is boring too.

_________________
There is always Sneaky Git.
Nelphine



Joined: Apr 01, 2011

Post   Posted: Jul 19, 2019 - 04:30 Reply with quote Back to top

I decided to try to calculate a rough upper bound for the number of states a game could have. I've based this on players.

There are 32 players. This is broken into 2 teams of 16. Each team is from a given roster. (For this discussion, we'll just go with the standard 24 rosters). Each player can then be 1 of up to (remember this is an upper bound, so this number is actually high since most teams don't have that many player types) 10 player types (the team with the most types of players is chaos renegades, with 8 positions, plus loner linemen, plus no player at all).

Therefore, just from this we can see the first player has 24 choices of roster and the 17th player (the first player from the second team) has 24 choices of roster, and the other 30 players all have their roster choice already determined. Each player then has 10 possible position types. So, at this point, we have (24*10)*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10*(24*10)*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10 choices of players. Or 496*10^32.

I'll address star players after the next paragraph.

Each player then has the choice of 74 possible skills they could have got when they got a skill up, plus 8 possible stat increases, over 6 skills ups. (We'll ignore old players with 7 skill ups for this discussion.) This means each of our players have 82^6 possible skill variations. Further, each player can have up to 3 stat lines for each of the 4 stats based on stat injuries (1 of them being no injury at all), all of which are an option for every skill variation. Further, every one of these options has up to 5 'stat' lines based on niggles (1 of them being no niggle, and we'll pretend there's a max of 4 niggles for discussion purposes.)

Star players are assumed to be a player from the team that has some combination of skills, which is why we've included the full list of possible skills (including extraordinary and mutations) for all players. This isn't QUITE true, but there are far fewer combinations of star players than there are 'extra' counts due to a player being not-a-player who somehow has the full complement of skills. Therefore, since we're talking just about an upper bound here, we're still fine, and the number holds.

Therefore, we are now at 496*10^32*82^6*13*3^4*5. This gives us 7.94*10^49 possibilities. We further multiply by 5 for different weather options, and we should probably account for non star player inducements somehow, but, I'll do that later. It'll probably end up being less than the 'no player who has skill combinations' number anyway, so in the end shouldn't matter.

Next, we have possible positions for each player. We have 4*12+7*12+4*12 for one side of the pitch, +15 end zones, 2 sides of the pitch, +4 off pitch locations (reserve, KO, cas, missing) for players of the current player +4 off pitch locations for players of the other player. And if the player is on the pitch, the player can be either on the team playing turn, or on the team not playing. If not playing, the player can be prone or standing or stunned or standing with the ball. If playing, the player can be prone (not moved), prone (already moved, which includes player stunned recently), standing (not moved), standing (already moved), standing with ball (not moved), standing with the ball (already moved). Therefore each player has 15*13*2*10+8 statuses for the player.

Now our total is up to 1.55*10^55 possibilities.

Now the ball has 15*13*2 possible locations. (Some of those have been checked already by player state, but oh well, this is an upper bound.)

Now we have ~6*10^56 game state possibilities.

Now, to fully compute game state possibilities, we'd need to determine what I'm going to class as a sub game state complexity. I'd actually calculate this similar to game tree size, but instead of looking at possible GAMES that can be played, I'd simply calculate the possible MOVES that can be played, given a particular game state. However, as this needs to be calculated somewhat akin to game tree size, I'm going to leave that for another post. But, we can say that it's probably going to be AT LEAST as complicated, as, say backgammon, which has 144 digits.

Therefore, our game state possibilities are at least 6*10^200. This actually makes it more game state complex than any game on the list that has previously been investigated. However, it is probably not of a higher CLASS of complexity than any previously investigated game.

Therefore, it should be possible to design an AI that could play optimally, it just might take slightly longer for the AI to become optimal.

If you then refer to my previous post, once you design an AI that can play optimally, you can then design AI that play sub-optimally (there are numerous other ways to play sub-optimally as well, for instance, considering an 'end' state as something less than an actual win - for human players, this is the equivalent of paying attention to the end of the action, the turn, or drive, or half, instead of looking ahead to the end of the actual game. You could also put other end states in, like trying to farm spp for a particular player, or trying to use particular skills just to use them, like tomb guardians who act as primary ball carriers for the team or dwarves who pass when they could hand off).
Display posts from previous:     
 Jump to:   
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Log in to check your private messages View next topic