Thanshin
Joined: Feb 09, 2010
|
 Posted:
Nov 16, 2010 - 18:28 |
 
|
Just some idle thoughts about BB AI.
Caveat: I do believe that creating a competitive BB AI is much beyond the budget that will ever exist for that purpose.
Ok, how I would structure a BB AI to reach a minimum degree of non-idiocy:
I see essentially two ways for an AI to understand a BB game: by patterns and by raw statistics. For many reasons, I'd choose raw statistics.
What I mean by raw statistics is that the AI should see the board at any point as a single number: the statistical chance of it scoring or not being scored against in that turn or, if impossible, in the next, etc.
Now what must be studied is:
A - whether it's possible to reach that number in a reasonable time.
B - whether it's possible to reach that number so fast that it can be used to establish a factual "value" of a given position.
If A is false (which I don't believe), this entire idea fails and a pattern recognition aproach must be used.
If B is very true (i.e.: calculating a position's value is trivial), the algorithm is reduced to calculating that value for any reachable position and then multiplying the value by the probability of reaching that position with a ponderation coefficient that would have to be tweaked (Is it better to have a 50% of scoring? or a 75% chance of reaching a position from where the possibility of scoring is 75%).
If B is only partially true (i.e.: a position's value can be calculated but it takes 0.1 seconds in a home computer), further study should be done to find out how to crop the evaluated positions, with the advantage of this being a very common problem and literally hundreds of ways to face it have been developed.
If B is simply false and it takes half a minute to know a position's value, a "partial value" would have to be found and replaced in the entire idea as a new, faster to reach, "value". That partial value would have to be one that hopefully would be close in perfection to the value and yet much faster to compute.
Now. I think A is true and B false. Which means the value of a position can be calculated but it would take hours.
I also think that to find the "partial value" one would have to be smarter than me and also know quite a lot about BB. |
|
|
Grod
Joined: Sep 30, 2003
|
| Posted:
Nov 16, 2010 - 18:58 |
|
Verry interesting Thanshin.
How would you go about evaluating the statistical chance of scoring over multiple turns?
Also, because BloodBowl is probability based, how would you go about assigning trade-offs for sub-optimal outcomes (when dice rolls fail)?
I am wondering if you might be able to expand on your idea (or, rather, make it more specific for Blood Bowl) ? |
_________________
I am so clever that sometimes I don't understand a single word of what I am saying.
Oscar Wilde |
|
Thanshin
Joined: Feb 09, 2010
|
| Posted:
Nov 16, 2010 - 19:36 |
|
| Grod wrote: | Verry interesting Thanshin.
How would you go about evaluating the statistical chance of scoring over multiple turns? |
Theoretically, exploring every branch to its inevitable end. In practice, I wouldn't. I'd only value my position by checking for each possible branch every possible enemy response that makes me lose the ball or him score. i.e.: I'd only let the ai think one turn ahead.
Having done that, I'd select other indicators other than ball possession and score. For example, ball position or players' status.
Having done that, I'd run a genetic algorithm to find the optimal relation between those indicators.
Having done that, I'd ask better players than me how they evaluate their positions and only then I'd incorporate that knowledge as additional indicators.
| Grod wrote: | | Also, because BloodBowl is probability based, how would you go about assigning trade-offs for sub-optimal outcomes (when dice rolls fail)? |
Dice rolls failing are just a chance. For example, let's say I have a single player who has the ball and is a must-down 2d blitz vs a blodger and two 2+ dodges away from scoring.
I'd just save that path as 21.2% of TD and then cut the computation of any other path that goes under 21.2%TD
All the rest is extending this to the entire turn tree. With the help of removing everything worse than the previou best and also that I'd try to compute first the players who have a chance to score.
| Grod wrote: | | I am wondering if you might be able to expand on your idea (or, rather, make it more specific for Blood Bowl) ? |
I will, when I'm back at work and bored.  |
|
|
BroadAsImLong
Joined: Mar 21, 2008
|
| Posted:
Nov 16, 2010 - 19:45 |
|
many flavours of AI. from neural networks to decision trees to fuzzy logic to robotics to game theory all the way down to choosing the correct sort algorithm in your program.
AI is one of the most complex and unfinalised (is that a word?) areas of computer science, and it took teams of dozens of the brightest researchers years to come up with a system to beat humans at chess. and they mainly cheat by working out the next 20 moves possible and reasoning which is better. now it would be awesome, but dont get your hopes up as like others have said, bb is more complicated than chess
b |
|
|
Christer
Joined: Aug 02, 2003
|
Generally, the methodology that Thanshin is talking about sounds to me like what AIs use for chess, othello and other zero sum games use.
In a generic sense, you come up with a number, let's say between -100 and 100. 100 means a victory for one team, and -100 for the other. Then you implement an evaluation function that for any possible board setup generates this number.
For example, being one TD ahead might give you 30 points, while one TD behind is -30 points. Then you add or subtract points for various things like the "area of influence" coverage, ball possession, ball threat, scoring threat, number of prone players, number of players in TZs, etc. Anything you can think of really.
To do the search, you then figure out the "best move path" by testing every possibility and searching further ahead using some kind of min-max search (look up alpha-beta for a fairly simple optimisation of the standard min-max algorithm). |
|
|
Carnis
Joined: Feb 03, 2009
|
| Posted:
Nov 16, 2010 - 21:45 |
|
| BroadAsImLong wrote: | many flavours of AI. from neural networks to decision trees to fuzzy logic to robotics to game theory all the way down to choosing the correct sort algorithm in your program.
AI is one of the most complex and unfinalised (is that a word?) areas of computer science, and it took teams of dozens of the brightest researchers years to come up with a system to beat humans at chess. and they mainly cheat by working out the next 20 moves possible and reasoning which is better. now it would be awesome, but dont get your hopes up as like others have said, bb is more complicated than chess
b |
How is that cheating, isn't that almost exactly the same kind of logic the human players use when dictating their moves?  |
|
|
asharak
Joined: Nov 27, 2007
|
| Posted:
Nov 16, 2010 - 22:09 |
|
Sort of. We don't actually consider every possible move. That said, for most chess AIs nowadays they don't either, taking a heuristic approach to try and avoid looking at apparently stupid paths for longer than strictly necessary.
When taken to the extreme it can make a game redundant (though BB having chance involved prevents this)
If you take a simpler example - checkers. Computers have now 'solved' checkers and proved that barring a mistake it will always be a draw. If chess were ever to be solved there would be no point in ever playing against a computer player as you would know winning is impossible. In this sense it could be viewed as cheating, indulging in a rigged game. (Of course it may be that it will be solved as always being winnable by white for example. Then you could play as white to see if you could achieve this. Unlikely though and tournaments vs. such a computer would be meaningless) |
_________________
Give a man a fire and he will be warm for the rest of the day.
Set a man on fire and he will be warm for the rest of his life. |
|
Thanshin
Joined: Feb 09, 2010
|
| Posted:
Nov 26, 2010 - 15:09 |
|
An alternative idea to avoid the chance crunching that goes much beyond the computing power we'll have:
A coach AI and a player AI for each of the team's players.
Each player considers himself only, calculates his possible results. For example, a player who's carrying the ball would find his best path to the TD and only considers the teammates who could remove obstacles that are in front of him. A blocker would just return his best blocking or blitzing chance. A guard could calculate his best chance of adding dice to the most enemies.
Then, the coach AI would choose among his players' suggestions (given as a numerical improvement of the playfield, a chance of losing the turn and the needed teammates) follow the best one and, if he (the coach) keeps the turn, he'd ask all remaining players to respond again (with optimizations to avoid recalculating unchanged situations).
This system is not only much faster but has also the advantage of allowing to evolve the single players or coach AIs independently, to find a faster, better, player or a better coach.
All AIs, players and coaches, would have numerical parameters that define how they take their decisions (safest first coach, cager coach, bashy player, ball taker, runner, marker, etc.). Those parameters could be assigned to different races/positionals, selected by hand to form a specific team or even optimized with a genetic algorithm.
[Edit: Or, even better, the coach could supply those parameters when asking a response from each player. For example the coach AI could ask all blockers their perceived best block, the ball carrier his perceived best advance option and some free linemen their perceived best chance of reducing the reachability of the carrier.]
[Edit2:
Funny consequences of this system:
- The coach AI could even ask several "questions" with different parameters to the same player if he so wished.
- The coach AI could even be replaced by a human being to test the player's AI.
- It would be possible to create a meta-game where players come with an attached AI, so you could have to fire a lineman because he thinks like a thrower.
] |
Last edited by Thanshin on %b %26, %2010 - %15:%Nov; edited 1 time in total |
|
Grod
Joined: Sep 30, 2003
|
| Posted:
Nov 26, 2010 - 15:26 |
|
| Thanshin wrote: | An alternative idea to avoid the chance crunching that goes much beyond the computing power we'll have:
A coach AI and a player AI for each of the team's players.
Each player considers himself only, calculates his possible results. For example, a player who's carrying the ball would find his best path to the TD and only considers the teammates who could remove obstacles that are in front of him. A blocker would just return his best blocking or blitzing chance. A guard could calculate his best chance of adding dice to the most enemies.
Then, the coach AI would choose among his players' suggestions (given as a numerical improvement of the playfield, a chance of losing the turn and the needed teammates) follow the best one and, if he (the coach) keeps the turn, he'd ask all remaining players to respond again (with optimizations to avoid recalculating unchanged situations).
This system is not only much faster but has also the advantage of allowing to evolve the single players or coach AIs independently, to find a faster, better, player or a better coach.
All AIs, players and coaches, would have numerical parameters that define how they take their decisions (safest first coach, cager coach, bashy player, ball taker, runner, marker, etc.). Those parameters could be assigned to different races/positionals, selected by hand to form a specific team or even optimized with a genetic algorithm.
[Edit: Or, even better, the coach could supply those parameters when asking a response from each player. For example the coach AI could ask all blockers their perceived best block, the ball carrier his perceived best advance option and some free linemen their perceived best chance of reducing the reachability of the carrier.] |
Yes, that is pretty much exactly what the AI I have programmed does. Download it and take a look! |
_________________
I am so clever that sometimes I don't understand a single word of what I am saying.
Oscar Wilde |
|
Thanshin
Joined: Feb 09, 2010
|
| Posted:
Nov 26, 2010 - 16:29 |
|
| Grod wrote: | | Yes, that is pretty much exactly what the AI I have programmed does. Download it and take a look! |
I had it already and have played with it a bit. I can't download netbeans at work right now but I'll try to find a moment to read the code.
[Edit: Silly me, I could (and am now) read it perfectly with any other ide.] |
|
|
birdbanger
Joined: Jul 02, 2009
|
| Posted:
Nov 27, 2010 - 15:42 |
|
Been away from fumbbl for couple of months. Gotta try this out! |
|
|
Grod
Joined: Sep 30, 2003
|
| Posted:
Nov 28, 2010 - 21:44 |
|
I just released a version which has all the frogs leaping, and the Goblins using their secret weapons (except bombardier), and the vampires gazing and biting...
Get it from my blog. |
_________________
I am so clever that sometimes I don't understand a single word of what I am saying.
Oscar Wilde |
|
Thanshin
Joined: Feb 09, 2010
|
| Posted:
Nov 29, 2010 - 16:27 |
|
| Grod wrote: | I just released a version which has all the frogs leaping, and the Goblins using their secret weapons (except bombardier), and the vampires gazing and biting...
Get it from my blog. |
Now if you could only release a version with an option to activate:
- players into black letters.
- a white playfield.
- No player avatars.
- No sound.
- Move, pass, foul icons as textual "Mov", "Pas", "Fwl"
You could call it the... "High contrast" option . |
|
|
|
|
| |
Finishing the 60 Gam...
Search
