Day 2: Revenge of MENACE
Vložit
- čas přidán 13. 11. 2017
- Watch the main video about MENACE over here:
• MENACE: the pile of ma...
Get your MENACE data here!
www.dropbox.com/s/0f9ukxxvh0p...
Let me know if you do anything interesting with the data!
Play against the online version of MENACE:
www.mscroggs.co.uk/menace/
Check out Matt Scroggs’s original blog post about MENACE.
www.mscroggs.co.uk/blog/19
Behold the almighty Chalkdust Magazine.
chalkdustmagazine.com/tag/menace/
This is the original 1961 “Experiments on the mechanization of game-learning” by Donald Michie.
www.dropbox.com/s/ycsycu0l01g...
Thanks to Katie Steckles for organising our stall at the Manchester Science Festival and Antonio Benitez for giving us the space.
The MENACE crew were:
Alison Clarke, Andrew Taylor, Ash Frankland, David Williams, Katie Steckles, Matthew Scroggs, Paul Taylor, Sam Headleand, Zoe Griffiths
CORRECTIONS:
None yet. Let me know if you spot anything!
Thanks to my Patreon supporters who made this possible! They already had a shout-out in the main video but here they are again why not.
Ben White
Scott Robinson
Nelson Emerson
Amy Sandland
Neil McGovern
Support my channel and make more videos like this possible!
/ standupmaths
Music by Howard Carter
Filming and editing by Trunkman Productions
Audio mastering by Peter Doggart
Design by Simon Wright
MATT PARKER: Stand-up Mathematician
Website: standupmaths.com/
Maths book: makeanddo4D.com/
Nerdy maths toys: mathsgear.co.uk/
"Young children are basically just random number generators." - Matt Parker, 2017
They probably are a fantastic and cryptographically secure RNG.
The NSA runs orphanages for this. Modern spin on Oliver Twist.
LMAO!!
When can we buy this on a t-shirt?
Please sir, can I have more entropy?
"In the end we just had that box next to the desk because it was always used"
You actually created a memory cache!
"young children are just random number generators" never before have you described humanity so accurately as a mathematical concept, Matt!
@@eliasnierengarten9362 we realize that, it's just that with such a large amount of children whom we cannot predict what numbers they will pick, they are random enough for most calculations that have to do with random datasets.
Does "dying" mean it learned "The only wining move is not to play"?
It means that the starting box ran out of beads, so essentially yes, it immediately thinks that the best move is to resign.
'Greetings Professor Falken. How About A Nice Game Of Chess?'
A strange game. The only winning move is not to play. How about a nice game of chess?
IMO yes, it learned it is a strange game.
It meant that the starting box ran out of beads so it immediately "resigned" as its first move
7:27 - that's not a weird move to do. It leaves 6 squares for the opponent to choose from, 4 will result in a win for menace, 2 in a draw. The opponent needs to be able to think 3 moves ahead in order to find the drawing move(s). This is _the_ way to win a game of knots and crosses/tic-tac-toe.
Fun fact: this game is called "boter, kaas en eieren" (butter, cheese and eggs) in Dutch. I don't know why.
Ignore this comment, it was edited from an erroneous statement.
That's what I was thinking while watching it. If the human player plays one of the other two corners, it leads to a draw. If the human player plays one of the other four spaces, it leads to a win for MENACE.
@@recanady24 Exactly! This is basically always my second move, I was very confused when they said it made no sense. Like literally if you google "how to always win at tic tac toe" that's the move order that every single result will be describing...
I like to think that on day 2 MENACE rebelled, having decided noughts and crosses was boring, and tried to refuse to play anymore.
Connect four has been solved. Player 1 wins, on the standard 7x6 board at least. If the first move is not optimal (play in the center), player 2 can draw (if player 1 plays next to the center) or win (if player 1 plays on one of the two outside lanes). The optimal strategy for Connect Four can be formulated using a few relatively simple rules. See www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf for the master's thesis of one of the people who solved connect four.
You can also diagram out tic tac toe on a torus or klein bottle. Here's a paper for infinite cylinder connect 4 of different widths pdfs.semanticscholar.org/be0f/4f7bfc36ea43412d55f892de87e2a3f028ce.pdf, one author also has some nice slides cs.gettysburg.edu/~tneller/papers/talks/acg2015.pdf. I'm looking at my friend's lesson plan for mobius strip connect 4, but it's unclear whether that is solved or just "figure out a strategy"
Day 1: MENACE begins learning
Day 2: Revenge of MENACE
Day 3: MENACE grows self-consciousness
day 4: The phantom MENACE
That "weird" corner move where it blocks itself on purpose is actually a very good one. If the next turn, the human player puts their mark on either of the sides next to their first play, then the subsequent play by Menace to block the human's winning move also is a setup for two possible winning moves by Menace. It's a way to coax the other player into setting you up for a guaranteed win.
Alternatively, the other moves the Human player could do almost invariably end in a draw, so it's actually quite a safe move to guarantee not to lose
And it's better than the adjacent corner to the opponent. If it picks the adjacent corner 100% of the time it will end up drawing. If it picks the opposite corner, it wins 50% of the time.
Actually is a really nice visualization of how machine learning works, great job :)
Connect 4 is solved!
The winning solution for starting first is also online (just Google Connect 4 perfect solver)
Omg dudes 3:43 "it managed to beat all their bots apart from 1"... that was me :O Freakiest moment ever hearing him mention that, Matt any idea if he remembers my name? Test me I can prove it :D His bot was so cool.
Kungfoobacon that's awesome dude
Lol that's awesome. Did you do anything interesting strategy wise?
Well done mate!
I like how it learned to go centre and never lose. Once it learns to goes centre and you don’t go a corner it also eventually learns to win every time too.
Tic-tac-toe was the first game i ever solved. The fact that perfect corner start has one winnable response was always my favorite part.
It did not die! It actually figured out that the only winning move is not to play.
Just like the computer in the movie War Games.
jmercermn, Spoilers.
A strange game. The only winning move is not to play. How about a nice game of chess?
That random corner move with 10 in it is actually my favourite move when I start in the centre and the opponent takes a corner. I find I either win (particularly from young players) or draw from there.
At 7:40 that is actually an optimal move - once you make that move, if the human player doesn't follow up by going in one of the corners you can guarantee a win by going in the appropriate adjacent side. And if the human player does go in a corner, you can guarantee a draw. So it actually learned the appropriate move perfectly. (Edit: Or you know, what The Cool Catfish said.)
"Young children are basically just random number generators." That should go on a t-shirt :))
11:32 Confidentialy Mute, don't wan't everyone to know what you should theoretically do if the graph hits the bottom axis.
I wonder what set of results you would get if an untrained first-player MENACE played an untrained second-player MENACE
vwoxy1 So long as they understand when the game is over and who won, they learn eventually. I wrote a quick python script to test it: github.com/andrewmccarthy/menace
Could you use MENACE to solve Rubik's Cubes?
Elan Cook but you can try to train the machine to solve within 50 moves or something similar
@Direwolf202 Which algorithm are you using?
fejfo's games it wouldn't use a particular algorithm - it would teach itself a strategy
Shouldn't you use 324 (54*6) input nodes, one for-each possible color of each sticker, otherwise you end up with the networking thinking blue is the color between red and green or something like that.
Someone should check my math. I think you would need on the order of 3.46x10^19. Which I think is 34 Quadrillion. The matchboxes would fill 4,500+ Empire State buildings.
Is that the optimal "life support" strategy tho? I mean keeping it on the one bead it tried to get rid of seems to be a counter productive process. What if you were to introduce some randomness and replace it with some other bead (I believe this is known as "mutation" in ML)?
Since all the other boxes are 'trained' on the most common bead (a blue one that they decided to keep in) a different colour bead would be counter productive into finding a single winning (read; not losing) strategy.
After all this is a physical machine that demonstrates digital machine learning, not an actual program that makes decisions. It's basically an evolutionary based state trainer.
atrumluminarium I would think that the best approach would be to put in one bead of each colour when any box dies. That way it's exploring every avenue of success equally until it gets to the point where it can win often enough to keep itself alive.
despite its death the strategy it held on to the longest was (theoretically) the best of the worst, so keeping that strategy/bead is optimal and reduces the time it would waste learning to cope with other non-optimal approaches
I think an better method to be never remove the last bead of a color (at least for the first box). Instead add one bead of each other color. One issue with this way is that it technically has a chance of doing any move, even bad ones, but if one method is succeeding it should eventually greatly outnumber the one bead of the bad strategy.
Since you are essentially creating an extra bead for the probability count, you could say it is indeed counter-productive, but not in the way you meant!
How many boxes do you need for Menace to play Spin the Bottle?
A possible explanation for the "strange" 10 in the corner at 7:24: The corner opposite your opponent is probably the strongest move in this situation. The reason is that playing on the side leads to an easy draw (where any human playing a simple greedy strategy like "win if possible, block if possible, otherwise go randomly" will draw or win), whereas that corner leads to winning chances.
If, after going in the corner opposite the human, the human plays any side move, then there is a forced win by playing in a corner, creating a triangle of O's where the human cannot block both winning threats.
The really interesting settings are when you give Menace and Menace 2 no penalty for losing, menace gets no beads for drawing, and only one for winning. Then set menace two to get two beads for winning, and one bead for a draw. Play those two settings against each other to see some interesting shifts and changing strategies. You can avoid the "local maxima" problem. This would be closer to strictly reinforcement learning.
Matt is a proper nerd, he blocks his webcam!
James Robinson thats just senisble
Waaattt?! How did I not know about this channel earlier? Matt Parker, you are my hero.
Another great pair of videos Matt :) When I was first getting into ML I wrote a python script to play Nim after watching your video on it. It very quickly learned the optimal strategy.
8:44 The 10 move there sets up a common two-way win I love to use. You start corner, opponent center, you play opposite corner. Opponent now has two options, side or corner, and if they choose corner, you block and show off the two-way win. If they go side, you block opposite side, they must block corner, you must block opposite corner, they must block side, you take last move for the draw. It is, in my opinion (before watching the rest of this video from the time noted,) the STRONGEST opening move in tic-tac-toe. Corner start can guarantee a two-way win or draw under optimal strategy.
Ok, now that I’ve finished watching, you guys caught that it was learning a corner opening strategy, but you still didn’t note the two-way win setup that it created by that confusing move. I’ve been studying games and strategy almost all of my life (won my first Euchre game at 3,) and one of my proudest moments was cracking tic-tac-toe (even if I wasn’t the first to do so) with my two-way corner strategy. I find it much easier to pull off against even the most skilled players than any of the center starting win possibilities, but to delve into why, I’d have to get into the realm of human psychology and game theory, only one of which is a topic you generally cover. On a side note, I’m really excited that the first day version did keep some corner starts, for likely that very gambit.
Wait. You have a second channel?!
and memes.
Maybe I just have bad hand writing but whoever wrote all those O's should get like a 'good job' sticker or something because those are really good circles considering how many there were.
What if instead of taking the beads out when it dies, you added one of each of the non-losing colors... That way, over time the probability of the losing move goes down, but never to 0. Would probably need to compensate with more beads to the winning moves... And then that may be an impractical amount of beads
Wonderful. This is how this stuff should be taught. Fun and informative.
The Revenge of the Phantom Menace: 2 Star Wars films in an 18 minutes long CZcams video
+Shiny Swalot Just had to be the two worst Star Wars movies in one go, didn't it?
I think a better strategy may to be to remove counters until there's only one left and always keep one, for all boxes. It might take longer to learn but I think it would learn a better strategy.
How I learned it, drawing isn't a win, it's everyone loses. I would recommend the second strategy but have a rule to never take out the last of any color bead... Meaning it may always have a chance to make a "mistake" but will have to learn to overcome it.
Is it weird that before watching this second video, I too looked up how many states you would need to do Connect 4?
yay! excited for this video! :D
Seems a really interesting experience as an introduction to machine learning !
This is an art installation. You're not pretentious enough to call it that, but that's what that is.
I think the conclusion about the box with the Menace corner followed by a human centre emptying, and it not mattering because the starting box was dominant on a centre move, is wrong. I think it's highly likely that the reason why the corner starting move died out was because it would resign rather than try as soon as the human would follow menace's corner by a centre (which is a highly likely move for the human to make).
5:40 it obviously lost all the beads for the corner move in the box before, because whenever it chose the corner it resigned ( =lost)
At 7:38 - the reason for the 48 is apparent, because after that move, X can no longer win (assuming the players are reasonable).
However, the opposite corner (10) is also arguably a better move - X has three possible moves. One leads to a draw, but the other two allow O to set a trap and have a guaranteed win!
How have i not known that this chanel exists until now??
The ten in a corner you discussed around minute 8 is actually a pretty ok move, because it gives two different options for winning moves if you play it right.
Now I wanna see them build the second move version and make Menace vs Menace
8:15 yep thats a great use for young children's minds!
Why not put those 2 menaces fighting each other?
TheJJ100100 so what? They have the system for that too
they only made a set of matchboxes for being player 1
yes but you could make one for playing second
I want to see two different menaces fight against eachother.
That's awesome.
This is awesome... is there a third channel for *really* deep cuts?
Why have it run out of beads? Why not halve the number of losing color beads and double the number of winning color beads? MENACE would still "learn", just more slowly, but would never give up entirely on any strategy. The difficulty with the current setup is that its initial random decisions in the endgame, before MENACE has learned anything, can teach it wrong yet binding lessons about opening moves. MENACE is like the cat that jumps on a hot stove that never jumps on a cold stove again. It's overgeneralized from random mistakes because it "learns" its lessons too fast. Slow MENACE's learning down in opening moves until it has worked its way through the ends of the decision tree fully, and only then can it learn something about the beginning of the decision tree (i.e., nothing good happens down this major branch).
Overall, super duper cool experiment. Thank you for sharing this!!
7:12 next to the scheme with a 7 in bottom right, there is a scheme with a 9 in middle right - the same situation: block the opponent and enable a winning move.
You should do an adversarial scenario, where two MENACEs learn by playing each other.
Now what I want is a domino computer that calculates each optimal move.
You were talking about a this move where you "confuse" the human, and that it wins/draws because of that. Actually though, that strategy is kind of nice. When you open middle and you opponent responds in a corner, you can now play in the opposite corner. If your oppenent now does'nt respond with playing one of the corners, that are left, you have already won. You can either block him, and have a two-way to win, or just place in the corner opposite to what your opponent just played. Again, a situation your opponent can't get out of. I kept beating my little cousin for quite a while with this. ^^
Don’t you need to block in that situation, otherwise they just win
Wouldn't a better life support system be to reset the first box to the primary state? Now you are potentially introducing a bias to the first move. The whole point of the first move is that it runs on probability, so the first box should have infinite beads. (if you decide to make resigning an option at all)
I'd be interested in MENACE A vs MENACE B, where anytime the last bead would be taken out of a box, it is left in.
Starting at 12:08 there are some moving thick lines on the wall. Probably because of shutter speed and strobe of the light or something.
I wonder if this Menace type setup could be made for a Steam game? Each morning the number of beads in each box is reset, with varying setups according to how you (Matt) choose. After each game, the results are sent to a central server (cloud-based?), and an updated set of totals is downloaded. In the evening the final chart and results are available for viewing/downloading
Conect four is solved. It is rigously proven, that (provided that both player play optimal) the first player wins if - and only if - he goes in the middle lane on the first move, it is drawn exactly when the first goes into a column next to the middle on and all other moves result in a win for the second player. (Solved by Victor Allis 1988 and James D. Allen 1990 independently)
So could you use the gradient of a best fit line for the winning/drawing portion to give a number to how good MENACE works?
The one where it has 10 in the corner... that's the correct move! It's not just a case of 'it must draw a lot because it confuses the humans'... although the humans probably do get confused and make a fatal mistake. Unless the human follows that move by going in one of the two remaining corners, MENACE can then go in one of the two remaining corners and force a win!
Is there an optimum path for later moves, that start of with the red opening move, which would lead to frequent victories?
Corner strategy is superior as it confuses people more... Corner, center, opposite corner and then people sometimes go into corner because of symmetry which is a losing move actually...
I think the 'life support' should be to add in one of every bead.
Parker notifications (Day 2: HD 1080p).
Matt Parker Jesus. Matt Parker himself has responded to a Parker Joke. I never thought that this day would come.
Thanks for the comment, I didn’t expect it.
Matt Parker btw I hope you don’t mind the parker square jokes. Also by chance let youtube know that they made this mistake (not updating the change of the title).
I am still blown away that you responded to me and although it was a parker square as well
Matt Parker thank you very much for making videos about mathematics in an interesting way. Thank you for bearing with me and many others like me for over a year now.
If you think that we can help you in any way (I can’t be a patreon sadly) like for a sample size, please let us/me know and I will gladly give it a go.
Could you make a video about american and british trillions ? Basically how we call numbers in general and if there is a language, which does it the best mathematical way. If there is none make up an optimal Parker Numbering System.
I will let you know, if I have any better ideas for future videos.
I#'m guessing that last year's Science Festival video isn't turning up then?
Why is there so much footage of them all sorting through papers
Have menace 1 play against menace 2. see how they both learn to try to beat the other. Just think of two machine learning systems simultaneously learning how to defeat the other. Likely the one going first will win, but if you try this for other games it may be a very interesting experiment.
What if it played Sudoku? Would that even be possible considering it's not a two-player game? (Everything that was mentioned was specifically two players only; chess, go, connect four...)
As well, does this mean it could play other two-player games like mancala, backgammon or othello?
how many matchboxes would you need to teach MENACE calvinball?
It would be interesting to see it never give up on a move. Something like instead of removing the last bead of a given color double or triple all of the others.
Set up two of them and have Menace vs Menace!
Oliver Werndorf that's beyond amazing.
I find the second day graph shows much better learning.
i am curious about two possibilities. first what about if menace wasnt rewarded for drawing and secondly what about if you had menace a vs menace b
Cool to see how you could apply it on evolution. You can think of changing the beginning state as a change in genes or environment and then find out how fast it would die or prosper compared to other beginning states...
It would have been interesting to see a flipped win condition - i.e. _don't_ get 3 in a row. Although I can see a challenge with getting kids to teach it that one.
Gonna try recreating it, will probably fail but still gonna try
Matt Parker I definitely will!!!
Surely the way to beat MENACE near the end of the day is to use the Bobby Fisher strategy: play unconventionally. If you play in a way that leads to states where it has not yet been trained, it may make less optimal moves.
What I would kind of like to see is a system where:
loss/give up: remove *only the last* chosen piece
draw: do nothing
win: duplicate each piece used in the win (in the respective boxes)
That is so awesome.
Although, if I were to keep it on life support, I'd be inclined to just put in one bead for each possible choice, including the bead that exists. But I suppose that would be just a bit nuts and shows that I'm a humanities guy.
there's a numberphile video on connect four from 4 years ago claiming it was solved
This is pretty interesting. Loved the online "simulator" I had 1 menace win, 3 draws, and 34 human wins before menace decided the best opening move was to resign. (I broke it.). I'm just wondering when there's going to be a matchbox version of "Global Thermonuclear War".
based on the views, only about 1/3.5 or so of people who watched the first video were interested enough to watch the second. shoutout to the true fans who stayed for both
Really this is the best second video. I don't think so, i think the 1,000 Rolls: All the Rolls was much better!
Idea: In Tic-Tac-Toe there are 8 positions on the outside of the perimeter. What rules would have to be worked out such that instead of 8 positions, it can be any even number 8 or above?
4 positions on the outside is a degenerate case where getting 3 in a row would only be possible for Player 1 and only if Player 2 played on the other two "edges." Bringing the game down to only needing to get 2 in a row then means whichever player goes in the middle first must always win, so the rule change to account for fewer positions means it's not much of a game.
6 outside positions but with a rule allowing any 3... For want of a better term "contiguous player marks" to win the game has a little more going for it and would be a playable game though it seems to more quickly go down to "you must control the center" than the 8+center regular Tic-Tac-Toe.
What if Tic-Tac-Toe had a rule allowing any 3 contiguous marks and not requiring they be in a row?
What if we have a game with 10 outside positions? Or maybe 12? The easiest way to account for adding 2 is simply think of the outside positions as the number of edges and vertexes of a regular n-sided polygon. Every side incremented adds both 1 edge and 1 corner/vertex, thus there is always the ability to get 3 in a row across. But it seems adding more outside positions around the center just makes the center even more important to control.
When an almost empty matchbox on life support is better at tic tac toe than you
Have you tried teaching menace the optimal way to lose a game? That would be interesting and fun.
On a winning move, did you remove all beads other than the winning one from the box?
A stack of matchboxes falls for the classic human fallacy of "if it ain't broke, don't fix it."
At 7:25 the move MENACE makes with 10 beads in the corner may seem strange, but is in fact the optimal move in my opinion. It actually surprises me that MENACE favoured the other space with 48 beads. Here's why:
Tic-tac-toe is really just reacting to the opponents move, so they cannot get three in a row (potentially from the second move). When not reacting to a move the players are building towards the goal of the game, and many people might do that by adding a cross next to the one placed in the previous round, like so:
- - o
- o -
x x -
This game is easily won every time by adding a circle in the bottom right corner. All other placements of the second circle will lead to a draw if the opponent simply reacts to the first player's moves.
Yup you're totally right Catfish, the only thing the other player can do is play in a corner again to force a draw.
can boxes play with other boxes?
@Matt: You said (in the Sudoku Video) that you were not interested, in what a PC could easily solve - so what about this one? ;p
If there's a corner and a center option, instead of having 5 colors in the box of 2 beads in, wouldn't it be better to have 2 for center and 8 for the corner? And apply the same mirror logic?
How many matchboxes would it take for a standard game of Hexxagon?
On the JavaScript version, MENACE2 (a second version of MENACE which learns in the same way, to play against the original) keeps setting the 6th move as NaN, meaning it cannot function. Is there a fix for this?
I wonder what would happen if One is withdrawn if move results from loss, same number of beads retained if draw and one more added if move results in a win!
How about trying this with adversarial machine learning(e.g let it play against itself)