Forum adverts like this one are shown to any user who is not logged in. Join us by filling out a tiny 3 field form and you will get your own, free, dakka user account which gives a good range of benefits to you: No adverts like this in the forums anymore. Times and dates in your local timezone. Full tracking of what you have read so you can skip to your first unread post, easily see what has changed since you last logged in, and easily see what is new at a glance. Email notifications for threads you want to watch closely. Being a part of the oldest wargaming community on the net. If you are already a member then feel free to login now.

Thanks for that spreadsheet! Very nice!

Ostrakon wrote:To account for all these differences (and linearizing the game board, which makes it not terribly realistic ANYWAY) it would probably take 100 Deep Blues working in unison to compute these calculations by the year 3000.

Well, then the issue is only that of scale. If it would take 100 Deep Blues 1000 years to do it, it would take 1,000,000 Deep Blues mere days. We'd just need to throw Imperium-level resources at the task.

Also, there are more game combinations then there are atoms in the universe, right? As Ostrakon said, WH40K is exponentially more complex. Saying,

To account for all these differences (and linearizing the game board, which makes it not terribly realistic ANYWAY) it would probably take 100 Deep Blues working in unison to compute these calculations by the year 3000.

is an understatement. I would place the year around more....
Googol?

The only time I do any Math Hammering is when I'm weighing the effectiveness of certain units of my armies within the same type: For example...deciding whether to take 4 Havoc CSM w/ Las guns or 3 Obliterators. For me I don't ever see a reason to take Havocs over Obliterators based on cost, survivability, and over all damage output via versatility.

Mathhammer, the exact same concept used by professional poker players, yet some people think it's useless.

It's logical to bet you will win if you are mathematically 80/20 odds against an opponent in CC. Can you lose? Of course. Same deal in poker. But you still rely on statistics to weigh your risks.

Not to interrupt but 40k is way easier than chess. It has fewer units, fewer variables and even, unlike Fantasy, all measurements are kept to quantities of 6" or 1" in the case of Scatter. (I don't want to be the nerde but I can ramble on about Fleet. Basically as far as decision making is concerned you are looking at 6" intervals.)

Any idiot could write a computer program that could beat humans at 40k, ESPECIALLY if they already knew how to write chess programs or other AI. Thinking turns ahead etc. Oh also it is only a six turn game with very clear rules of engagement. Most computer scientists could probably do it in an afternoon, other than the actual moving all the guys around. Everyone except Blackmoor who has that Brightlance list.

The computer's greatest advantage of course being the ability to guess ranges and measure with perfect precision. Besides knowing all the rules, not forgetting things etc etc.

Tacobake wrote:Not to interrupt but 40k is way easier than chess. It has fewer units, fewer variables and even, unlike Fantasy, all measurements are kept to quantities of 6" or 1" in the case of Scatter. (I don't want to be the nerde but I can ramble on about Fleet. Basically as far as decision making is concerned you are looking at 6" intervals.)

Any idiot could write a computer program that could beat humans at 40k, ESPECIALLY if they already knew how to write chess programs or other AI. Thinking turns ahead etc. Oh also it is only a six turn game with very clear rules of engagement. Most computer scientists could probably do it in an afternoon, other than the actual moving all the guys around. Everyone except Blackmoor who has that Brightlance list.

The computer's greatest advantage of course being the ability to guess ranges and measure with perfect precision. Besides knowing all the rules, not forgetting things etc etc.

I'm gonna have to say false on several accounts.

It is extremely hard to create a program that could beat any human in 40k when half of the variables are completely random. You could have a 99% chance to kill something and still fail. Chess, however, is 100%. There is no chance that you could not take a piece if it is in kill range.

40k also has FAR more variables than chess. Chess relies solely on the preset movements of 6 seperate pieces on a severely limited board. 40k has terrain, armor values depending on facing, random dice, movement, etc.

A genetic algorithm can generate a winning army and a super computer is not required.

Make a simulator with a basic AI that can play a warhammer 40K game. Start with an AI that follows the Tyranid instinctive behavior rules: assault units charge, ranged units find cover and fire.

Seed the simulator with 2 armies. Army #1 should be a solid tournament winning army. The second army is any valid army from the Codex you want to use.

The simulator then simulates a bunch of games with random variations of the codex army. The best armies are mutated and the cycle repeats.

After a few generations you'll have an army that does very well against the seed army.

If you want to evolve an army that does well against all armies then instead of simulating your army against 1 army, make it play against 10 solid lists of different varieties, e.g. mech, horde, etc.

You may be able to create an algorithm that would do well, but it is impossible to create an army that will beat a human player 100% of the time.

Chess is a game of absolutes. Everything has a definitive movement on a definitive board. 40k is very much based on probability and luck.

It's the same reason you can't create a computer that will win 100% of the time in poker. No matter what the computer has, the human player could have something that will beat it. If the computer has a hand that offers 99% chance of success, the human could have that 1% and there would be no way to stop it.

It's the same with dice. If the computer rolls well below average rolls all game, it will lose. It could lose to an entire army of foot-slogging tac marines. They could 1 shot all the vehicles with las cannons, win in assaults even if they are the ones getting assaulted, and make every armor save.

It comes down to random probability. And when you have that, computers are not able to think intelligently. It just goes with the most logical solution. Which can still fail.

Hoodwink wrote:

Tacobake wrote:Not to interrupt but 40k is way easier than chess. It has fewer units, fewer variables and even, unlike Fantasy, all measurements are kept to quantities of 6" or 1" in the case of Scatter. (I don't want to be the nerde but I can ramble on about Fleet. Basically as far as decision making is concerned you are looking at 6" intervals.)

Any idiot could write a computer program that could beat humans at 40k, ESPECIALLY if they already knew how to write chess programs or other AI. Thinking turns ahead etc. Oh also it is only a six turn game with very clear rules of engagement. Most computer scientists could probably do it in an afternoon, other than the actual moving all the guys around. Everyone except Blackmoor who has that Brightlance list.

The computer's greatest advantage of course being the ability to guess ranges and measure with perfect precision. Besides knowing all the rules, not forgetting things etc etc.

I'm gonna have to say false on several accounts.

It is extremely hard to create a program that could beat any human in 40k when half of the variables are completely random. You could have a 99% chance to kill something and still fail. Chess, however, is 100%. There is no chance that you could not take a piece if it is in kill range.

40k also has FAR more variables than chess. Chess relies solely on the preset movements of 6 seperate pieces on a severely limited board. 40k has terrain, armor values depending on facing, random dice, movement, etc.

That's fair enough, 40k is a game of chance just like other dice games and you could include card games. However if you do a large number of experiments or play a large number of games random chance will "even out" of course.

40k in fact has a very limited number of moves because there are only 5 or 6 or certainly < 10 units on the table. Chess has 32 units confined to a small board. 40k has a handful of units and a limited set of objectives it is not hard for a computer to beat a human, really. That's why they are computers. Especially since of all those potentialities there are only a handful of tactics that are actually any good similar to say American football or ice hockey.

It takes such large computers to beat humans in chess because they have to plan ahead, besides the fact the programmers had to improve their designs.

The bitch with 40k is when you play what I will call the Blackmoor. The player who knows how to win, forms gunlines etc. Knows all the RULES. Or at least knows their own army certainly. I would guess he could probably measure to an inch, something I have seen people do w/ enough practice. Another edge a computer would have over a human, besides measuring and understanding averages (two skills all 40k players should have of course) is they can also do complex calculations such as how many bodies should I charge into that close combat, that sort of thing.

I mean I am telling you right now, and not to be a jerk although this _is_ dakka. I am a computer scientist and I could write a computer program that could beat most if not all players, and could beat the Blackmoors given enough time and practice to program. In the end its edge would be measuring, knowing the rules and being basically infallible, I mean human opponents will make mistakes especially over a large number of games this is not a multi-million dollar a year pro circuit we are talking about here.

Basically what you do in writing the program is base it around 6" intervals and going for whatever the objective is/ Kill Points. Take into account line of fire, cover saves, etc. Assign probabilities to everything. Redbeard wrote an article on his blog he calls "circles" I wrote something that was supposed to be humourous although was just practice writing, really a few years ago.

http://kallend.net/40k/guide/circles.shtml
http://tacobake.blogspot.com/2007/05/40k-life-is-game-of-inches-salute-to.html

Anyway it could be done. Maybe I'll even do it although it would take more time than I, or anyone has, really.

I'm not saying you couldn't create a program that would beat MOST people, but due to the inconsistency of rolling dice, you can not create a program that will beat everyone.

Dice are too finicky to rely on 100% of the time. Chess is a game of absolutes. There is never a time in chess where someone is in range to be taken, but you miss. Or they make an armor save. Or you can't hurt them because they are facing you.

Well it is impossible to beat someone 100% of the time in any probability-based game of course. The only way you COULD, which you can is if you get into something like # of air molecules in a room, that sort of thing. I mean for all I know if you studied 40k stats in a game it could lead to something that is very predictable but I don't myself have enough experience to eye ball that so to speak. Like, maybe there ARE enough air molecules in the room to make good decisions. Air molecules referring to molecules of air will always spread out in the room they won't just all go in the corner, for example.

But yes it is true that if you play ONE game, assuming it has the same sort of odds that one roll of the dice will, you cannot predict a sure-fire winner.


Automatically Appended Next Post:
-----------------
Yes but to go back to the OP you can do it to a point, or I would guess you could. What you would be looking at is probably viable armies WITHIN a certain army. But I mean the core of that starts with the fact that certain units are just not that great compared to others.

It is possible to make decent armies from each book, Darklance Dark Eldar with Wyches, for example.

Branderic wrote:A genetic algorithm can generate a winning army and a super computer is not required.

Make a simulator with a basic AI that can play a warhammer 40K game. Start with an AI that follows the Tyranid instinctive behavior rules: assault units charge, ranged units find cover and fire.

Seed the simulator with 2 armies. Army #1 should be a solid tournament winning army. The second army is any valid army from the Codex you want to use.

The simulator then simulates a bunch of games with random variations of the codex army. The best armies are mutated and the cycle repeats.

After a few generations you'll have an army that does very well against the seed army.

If you want to evolve an army that does well against all armies then instead of simulating your army against 1 army, make it play against 10 solid lists of different varieties, e.g. mech, horde, etc.

Hey, you're seriously overestimating the power of Machine Learning here. Ignoring the inherent problems of creating an AI that can play a 40k game for reasons I've already discussed, all this ends up creating is a list that does well against 10 or so lists. We're talking best as in "best overall against all possible lists".

I mean, do you really have any idea how many permutations there are just in army lists? Not to mention how many permutations there'd be for the AI to calculate game by game? You sound like you have at least a little CS background, you should try to think this through.


Automatically Appended Next Post:

I am a computer scientist and I could write a computer program that could beat most if not all players

I sincerely doubt both assertions here. You sound more like a high school kid with a C++ book. Any sort of formal CS training would tell you that you're not

Please don't argue with game theorists about a subject you have no expertise in. Your assertion that chess - a discrete game - is computationally more complex than 40k - a continuous game with discrete elements - simply proves that you have no idea what you're talking about.

I feel as though this isnt realy in the spirit of the game.
this may be better not to find out
people will just get the "best" army because its the best army!
they will ignore fluff and all of the other good stuff ... what i find the game is realy all about

So... If I code up something, and enter it in the Vassal 40K GT... and it wins... do I get the prize?

skipmcne wrote:So... If I code up something, and enter it in the Vassal 40K GT... and it wins... do I get the prize?

Not the "I've found the optimal army" prize, but that'd definitely be an accomplishment.

Ostrakon wrote:Any sort of formal CS training would tell you that you're not

Any sort of formal CS training would tell me that I am not what, exactly.

Yes and while we are on the subject, please do not insult my intellectual integrity on a public forum.

Tacobake wrote:

Ostrakon wrote:Any sort of formal CS training would tell you that you're not

Any sort of formal CS training would tell me that I am not what, exactly.

Yes and while we are on the subject, please do not insult my intellectual integrity on a public forum.

That you're not a computer scientist. You fail to grasp basic game theory concepts like game complexity, and are making sweeping claims that you can build an AI that'd defeat "most if not all" players. That just shows a profound ignorance of basic theory of computation.

I don't think it would be all that difficult (in relative terms) to build a challenging AI for W40K. I mean, you already have an AI that does something somewhat related in the DoW video game series and does it in real time. I will grant you that the video game is a far cry from actual 40k tabletop, the programming uses a lot of predetermined tactical routines, and you can hardly say that it can beat 100% of people at it's hardest settings, BUT...I don't think it would take too much of a leap forward to provide a highly competant free thinking AI for a 40k simulation, certainly at least not hundreds of supercomputers and thousands of years as some have suggested. It also depends on what you are looking for. As pointed out already, if you are talking about building something that can beat 100% of human players 100% of the time in a format with a crapload of randomized elements, good luck. But if you are talking about something that can challenge most players than yeah, it could absolutely be done without putting the entire resources of a small nation behind it.

Maelstrom808 wrote:I don't think it would be all that difficult (in relative terms) to build a challenging AI for W40K. I mean, you already have an AI that does something somewhat related in the DoW video game series and does it in real time. I will grant you that the video game is a far cry from actual 40k tabletop, the programming uses a lot of predetermined tactical routines, and you can hardly say that it can beat 100% of people at it's hardest settings, BUT...I don't think it would take too much of a leap forward to provide a highly competant free thinking AI for a 40k simulation, certainly at least not hundreds of supercomputers and thousands of years as some have suggested. It also depends on what you are looking for. As pointed out already, if you are talking about building something that can beat 100% of human players 100% of the time in a format with a crapload of randomized elements, good luck. But if you are talking about something that can challenge most players than yeah, it could absolutely be done without putting the entire resources of a small nation behind it.

But that AI is not only

A) Not too great, as it can't beat a human player without cheating
and
B) Cheats by using information the other player wouldn't have about the AI's forces. For example, when you send scouts to Strategic point A, the AI already knows it, even though when he does the same thing you can't see it on your minimap.

Building an AI to simulate what an actual player could do when he's limited to the same information as his opponent is something else entirely. We simply do not have the resources to try and find a global optimum in a continuous system with as many variables as 40k. We COULD try to make a reasonable discretization to therein find a global optimum, but even that would take far, far too much time to compute, and because we applied subjectve bounds via discretization we can't really rely on it being an objective "best". That's what we need supercomputers for in this case: not running A simulation, which would be fairly trivial, but by running the trillions of possible simulations necessary to truly optimize the list.

If we ever have quantum computers we'll laugh at problems like this, but until then it's out of our grasp. We play 40k; we have a lot of time on our hands. If it were feasible, one of us would have done it by now.

Tacobake wrote:I am a computer scientist and I could write a computer program that could beat most if not all players, and could beat the Blackmoors given enough time and practice to program. In the end its edge would be measuring, knowing the rules and being basically infallible, I mean human opponents will make mistakes especially over a large number of games this is not a multi-million dollar a year pro circuit we are talking about here.

Basically what you do in writing the program is base it around 6" intervals and going for whatever the objective is/ Kill Points. Take into account line of fire, cover saves, etc. Assign probabilities to everything. Redbeard wrote an article on his blog he calls "circles" I wrote something that was supposed to be humourous although was just practice writing, really a few years ago.

If you write this program, I'll play it. I'll play it hundreds of times. And I'm willing to bet that it will never get to a point where I say, "Well, the AI is better than me." I'm inclined to agree with Ostrakon's thoughts given my own knowledge of game theory.

EDIT-Hell, feel free to run it against itself several million times first to let it mature before you give it to me.

Ostrakon wrote:
That you're not a computer scientist. You fail to grasp basic game theory concepts like game complexity, and are making sweeping claims that you can build an AI that'd defeat "most if not all" players. That just shows a profound ignorance of basic theory of computation.

Sadly true. There are reasons why, though people have devoted their entire lives to developing AI, it's still difficult to find a (non-chess) computer game that can beat a good human opponent without access to vastly more in-game resources than the human. Most games simply "cheat" by making the computer's units cheaper, or faster to build, or tougher (or simply giving them more resources to start with).

The scenario described above by Branderic, with everybody following 'Nid rules, has obvious flaws. I'm sure you think you can correct for those: keep units from shooting at or assaulting things they can't damage, don't assault the Bloodthirster with your assault marines even if they can damage him, etc. The problem is that, once you've corrected those, you have flaws that you wouldn't have thought of beforehand, but which are obvious now that you're testing the program. Next, you'll correct the ones of those that you've caught, only to find that one of the first flaws came back for reasons you can't understand. You'll correct for that one again, only to find new ones pop up. This will repeat for many months, until you've finally come up with what you think is pretty good AI. Then you'll get somebody else to play against it, who will beat it soundly. At that point, if you're bright, you'll realize that you were optimizing it to play against only yourself, and that if you want it to work against people in general, it will take years of work - if you're lucky.

Edit: I should add, by the way, that even after those years of work, it'll still be a middle-tier player. It'll be able to take on what you've programmed it to expect, but any time somebody throws something new at it, it won't be able to respond properly.

Actually, a lot of those scenarios would be accounted for even in a basic AI.

Another reason why this isn't going to work (at all) is the fact that players can't arbitrarily measure distances. A computer is going to "know" the distance between any two units whether we want them to or not. So we have to simulate a human player "eyeballing" the total distance to create a realistic AI. We want to find the optimal army, but if it can't be played optimally by a human then there's really no point in the exercise. And since we have to arbitrarily implement some sort of method to limit the AI's ability to "guess" the distance between two units, we can't rely on finding an objective conclusion.

I dont get where people are coming from saying 40k would be easy to simulate. It is orders of magnitudes more complex for a computer than chess is. Note the phrase "for a computer". Humans have abstract thought, computers do not. Obscuring actual distances from the program's decisions is cake, choosing a target to shoot at is hard. We just never notice it because of our ability to create and adapt a plan.

But mathammer doesnt have to be a simulation. Knowing the chance to get x kills is rarely bad. The only part I have trouble with in this is templates. Does anyone have a way to get the statistical chance of templates/blasts getting x hits on a unit in various formations? a CAD program maybe?

Gestalt wrote:I dont get where people are coming from saying 40k would be easy to simulate. It is orders of magnitudes more complex for a computer than chess is. Note the phrase "for a computer". Humans have abstract thought, computers do not. Obscuring actual distances from the program's decisions is cake, choosing a target to shoot at is hard. We just never notice it because of our ability to create and adapt a plan.

But mathammer doesnt have to be a simulation. Knowing the chance to get x kills is rarely bad. The only part I have trouble with in this is templates. Does anyone have a way to get the statistical chance of templates/blasts getting x hits on a unit in various formations? a CAD program maybe?

Shouldn't be that hard. There aren't really too many formations that people typically use (1,2,3 ranks between .5 and 2 inches spaced, then account for different base sizes), so it'd be easy to approximate if someone just sat down and did the work to account for all of those scenarios.

I'll try to do it when I get home from work if I get bored trying to score a Trapozohedron off of an Adamantoise.

Just ask if you can borrow the Cray Jaguar? XD

Ostrakon wrote:

Terminus wrote:

Ostrakon wrote:Now we just have to do this for every possible army list at every possible point value at and account for every possible movement, target decision, etc. This is certainly possible, but in a stricly theoretical sense. We don't have powerful enough computers to compute this data quickly enough to have the answer within the next thousand years or so.

Surely our computers are more than capable of performing the requisite calculations. I would think the coding of all those variables, and determining what constitutes a variable in the first place (and then how to best illustrate it numerically), would be the most time-consuming portion of the task.

You would be incorrect.

You know how we needed supercomputers like Deep Blue to beat humans at chess?

40k is several times more complex than chess. Chess has a finite number of possible board positions. Even if you reduced 40k to a grid system (let's say a 48 x 72 grid for 1 square inch "spots"), you'd have 54 times the number of board configurations as chess - assuming both players had 16 models! More likely each player is going to have 50 or more models, and this doesn't linearly increase the time it takes to compute it, it does so EXPONENTIALLY! And can you imagine how screwed we game theorists would be regarding chess if players could choose to forgo their rooks to take a second queen? To account for all these differences (and linearizing the game board, which makes it not terribly realistic ANYWAY) it would probably take 100 Deep Blues working in unison to compute these calculations by the year 3000.

The military runs complex simulations encompassing all aspects of combat (ground, air, and sea) which is infinitely more complex than WH40k, and they seem to get these things solved in less than a thousand years. You're greatly exaggerating my friend. Its not like we need one program to do all the calculations. Just create a battle simulator and constantly enter army lists as input and let it play out, thats even faster to do than one programming running hundreds of thousands of sims all in one go.

It would take longer to develop code to run the simulation and assure it's accuracy than it would to actually run the simulation itself but either way it won't take 1000 years. More than that, Deep Blue is a horrible comparison to make. DB was cutting edge in 1996, over a decade ago.

Hence me saying borrow Cray's Jaguar :3 Deep Blue blows.

But there are also different squad/vehicle sizes too. The odds of getting 5 hits on a 5 man combat squad are less than getting 5 hits on a 30 ork mob. 12 inches of scatter in however many directions, I would guess at least 8. There are a lot of permutations which is why I was hoping for some sort of program.

Edit: Military simulations do not run complex simulations without a supercomputer and are not as complex as you would think. Most others are computers to moderate what the live commanders are doing rather than automate units.

Gestalt wrote:Edit: Military simulations do not run complex simulations without a supercomputer and are not as complex as you would think. Most others are computers to moderate what the live commanders are doing rather than automate units.

I never said they don't use super computers. And though the complexity may not be as huge as I'd love to think it is, its still magnitude greater than a game of 40k.

The military runs simulations with implicit time constraints and they are merely looking for the best option out of predefined stratagems that generals propose. They're not interested in finding the absolute mathematically sound optimal plan, they use simulations to comparatively analyze a handful of possible scenarios and tactics for a given situation. The simulations they run in this manner would be in the hundreds, not the trillions.

We could use this approach to evaluate the best possible list and tactics out of, let's say, 10 predefined tournament lists for 10 different terrain setups with 5 or 6 predefined strategies, and find out which one is the best.

What it won't do is automatically find the best course of action for the best army list out of all possible army lists. If computers could do this, we wouldn't *need* generals anymore. We have generals because their insight is invaluable at weeding out tactics that make absolutely no sense, but that doesn't mean that they're going to come up with optimal plans every time. If generals could do this, we wouldn't *need* computers.

Selecting the best plan out of a relatively small subset of predetermined feasible plans is a completely different beast from selecting a global optimum out of all possible scenarios.