|
I was looking at this problem which is essentially a game known as Colonel Blotto
Each general must allocate a given number of troops across a given number of platoons which then battle against each other with results being decided on numerical supremacy. To win you need to both win the greatest number of battles and have the highest number of remaining troops.
So what we have is a zero-sum game which has twin objectives (somewhat like hi-lo poker variants but with a requirement to win both hands) with the additional complication of sequencing (a la rock-paper-scissors - e.g. if I set my troops out [19, 1, 19, 1, 19, 1, 19, 1, 19, 1], I might get a very different result than I would be sending out [1, 19, 1, 19, 1, 19, 1, 19, 1, 19] even though I'm using an identical strategy).
All of which gets me wondering - how well could we get a machine to play this game against a human opponent?
For the first element, calculating the optimal troop split, we could simply brute-force every possible combination, play them against each other and see what wins. Given the vast number of combinations involved, it's obviously a huge task but it's clearly do-able. We're essentially going to wind up with a ranked list of possible distributions). Let's assume that the results of these calculations will be revealed/knowable to the human opponent.
Now the human general has an advantage, he knows that the computer knows that the best distribution is distribution X and can easily counter (let's suppose the calculated "optimal" distribution is actually 10 platoons of 10 and the human knows that the computer will play the "best" distribution, the human simply plays 9 platoons of 11 and 1 of 0 and crushes him every time).
So the computer needs to throw a few curve balls - the easiest way to do this is to pick a random distribution from the top n distributions. The computer could further obfuscate by applying random increments and decrements to various pairs within the distribution or whatever.
Similarly when it comes to ordering the platoons, the computer's most effective approach might just be to randomise the whole distribution array, maybe it can work a more intricate algorithm based on previous distributions employed by the human general.
The human of course, has all the same curve balls at his disposal.
Machine learning is definitely on the menu and time is no object. All previous games are stored and available to both players for analysis. The human has all the necessary database skills and tools to view the data as meaningfully as possible.
The human general is so fond of Colonel Blotto and proud to be human that he is happy to play against the machine a million times over if necessary in order to prove that humans are smarter than tin.
Will he win?
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
PeejayAdams wrote: The human general is so fond of Colonel Blotto and proud to be human that he is happy to play against the machine a million times over if necessary in order to prove that humans are smarter than tin.
Will he win?
If the human is like me he has one huge advantage:
a bloody big hammer!
(well 2 advantages if you include my strength ... of rage.)
Message Signature
(Click to edit ->)
|
|
|
|
|
Fair point, I'll rephrase the question:
Will there come a point where the human general has to resort to extreme violence or praying that the cleaner unplugs the computer?
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
PeejayAdams wrote: human general has to resort to extreme violence
Every human on earth has the propensity for evil and violence.
so yes, the human general has to resort to extreme violence; it is his nature.
|
|
|
|
|
Slacker007 wrote: Every human on earth has the propensity for evil
The true question here is what kind of evil. Chaotic evil, neutral evil or lawful evil.
I have lived with several Zen masters - all of them were cats.
His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
|
|
|
|
|
Well evil is relative in regards to "type", but the only constant is that evil is the result of negative energy. So does it really matter what kind it is? No, of course not.
|
|
|
|
|
If there were no random elements to the machine's strategy then I would be tempted to say the human could win over time. As if they are able to identify the machine's algorithm, they could potentially predict future moves.
However, given then random element, the human ultimately has no idea what the computer will play. Therefore in order to have a chance of winning, the human must also play random guesses.Therefore I believe the outcome will ultimately be based on luck alone, and could unpredictably go either way.
Having said that, the psychological element of the human could effect the true 'randomness' of their placements. For example, they may subconsciously implement a pattern to their randomness without realising it, and if the machine has been implemented to pick up on that, it could steal the upper hand. So in this scenario (where the human also plays random), I would probably choose machine.
But... the wiki link suggests that there are strategies to avoid losing. In which case the human can simply play that strategy every time, and because they know the machine won't play it. The human will always either draw, or win. If that strategy is permitted by the rules though (i.e. playing the same distribution each game), then the machine would be stupid not to also play that same strategy every game. So all games would be a draw, and therefore no winner.
So bottom line, I think it really depends on how prepared the human is before starting, and very much how the machine is programmed to play.
|
|
|
|
|
musefan wrote: So bottom line, I think it really depends on how prepared the human is before starting, and very much how the machine is programmed to play.
Yes, I think we should go under the assumption that every human involved - programmer(s) and player alike - is as good as they can possibly be.
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
In which case I feel that they will all be forced to play the strategy that results in drawing every game.
That's assuming my understanding on the wiki information is correct (and that forced draws are even possible), I didn't read too much into it.
|
|
|
|
|
PeejayAdams wrote: Machine learning is definitely on the menu and time is no object.
Try an evolutionary algorithm[^]. It will produce results far more quickly than brute force and is far easier to implement than machine learning. The whole problem looks very well suited for such an algorithm.
I have lived with several Zen masters - all of them were cats.
His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
|
|
|
|
|
It would certainly suit the initial distribution ranking process.
Would it, however, help with the more psychological element of the game - the "A is the best thing I can do but he knows that so he'll expect me to do B but he knows that I'll know that he knows that I know that he knows that we know that I know that he knows ..." (there's a song in there, somewhere)?
With games that computers have beaten (or allegedly beaten) the best human players such as Chess and Go, you don't have that element of bluff and counter-bluff. So as much as computational power can only be of help at Colonel Blotto, could Deep Blue ever beat Napoleon?
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
Yes, it is possible if you don't just train the computer player and then use it forever. Keep a list of them, sorted by their fitness rating and generate a new one from the top 10% for every game. This way the evolutionary process keeps going and will try to adapt to the human player. You should have seen the best of my orcs against human players.
I have lived with several Zen masters - all of them were cats.
His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
|
|
|
|
|
A future CP coding challenge, do you think? (albeit with a somewhat simpler game than Blotto - rock, paper, scissors could be a good testing ground).
Whenever you find yourself on the side of the majority, it is time to pause and reflect. - Mark Twain
|
|
|
|
|
Why not? But don't make it too simple. Evolutional algorithms succeed where machine learning fails. You need to know the correct solutions to the problem to train a neural net. What if there is no single correct solution, like in your example here? Or what if you simply don't know the solution, even if it exists? Evolutional algorithms are search algorithms which home in on the best solutions. The drawback is that they also produce very 'weird' solutions, like naturally evolved systems do. There will be one or another appendix which will serve no purpose anymore and sometimes a baby's head will have to go through the mother's pelvis bone at birth.
I have lived with several Zen masters - all of them were cats.
His last invention was an evil Lasagna. It didn't kill anyone, and it actually tasted pretty good.
|
|
|
|
|
I am doing HPC work with GPUs these days. If it were me, I would use a brute force algorithm written using CUDA to run on a GPU. It's fairly simple algorithm and when running on a few thousand GPU cores it would be pretty fast.
"They have a consciousness, they have a life, they have a soul! Damn you! Let the rabbits wear glasses! Save our brothers! Can I get an amen?"
|
|
|
|
|
Do you know what the best thing about UDP jokes are?
I don’t care if you get them.
|
|
|
|
|
I am not going to acknowledge that.
"It is easy to decipher extraterrestrial signals after deciphering Javascript and VB6 themselves.", ISanti[ ^]
|
|
|
|
|
You just did 
|
|
|
|
|
And you responded. Looks like we have a connection here. My Totally Caribbean Personna worked!
"It is easy to decipher extraterrestrial signals after deciphering Javascript and VB6 themselves.", ISanti[ ^]
|
|
|
|
|
Well played  
|
|
|
|
|
Oh, pack it in with these technical jokes, you've lost me.
|
|
|
|
|
for me that was out of order
Message Signature
(Click to edit ->)
|
|
|
|
|
Doesn't look like there was a SYNergy there
|
|
|
|
|
Multicast: IP in your general direction.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
ACK! Get that thing away from me...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
