Connect 4 robot
So there was I, halfway through writing another blog post, when this landed on Twitter. Feast your eyes. It’s a Raspberry Pi robot that plays a pretty mean game of Connect 4.
David Pride, the maker, had to do a considerable amount of building work here: the grippers are the pincers from a MeArm, cunningly mounted on a spare rail for a 3d printer.
Connect 4 is not, when you think about it, that straightforward a problem. Happily for us all, David had the great foresight to make a writeup available. He says:
I discovered that there is a well known algorithm called ‘minimax’ which is applicable to games of this nature – and there is a Python library for it ? This algorithm uses tree searching methods to look n steps ahead for the next best move. Even on a small 6 x 7 Connect 4 board there are 4,531,985,219,092 possible game positions – yes, that’s TRILLIONS! So getting the Pi to play the game effectively could be quite a challenge. It becomes a trade off between absolute perfect play, and reasonable time for each move. I eventually struck a balance between them where it now plays pretty intelligently but still completes each move in roughly 25 seconds which is acceptable for a flowing game.
Of course, the robot needs to be able to do some other things besides understanding how to play Connect 4. For starters, it has to be able to differentiate between red and yellow counters, and see where they are in the grid. Earlier this year, David showed off a Lego sorter he’d made with a visual sorting algorithm: here he is with our very own Philip Colligan (who is the fella saying “yep” a lot), demonstrating the visual sorting algorithm in action.
You can read David’s writeup of the Connect 4 build at his website – David, let us know if you put the code on GitHub!
25 comments
Toby
OMG! I was playing connect 4 today… and lost!
Will it beat a human, though?
Liz Upton
Apparently so – it’s really pretty good at the game!
Ben
Will it be at the Pi birthday party? I’d love to play a few games against it :-)
David Pride
Ben – Yes, it’ll be at the Pi Party – ready to take on allcomers (!)
Dave – good suggestion, and tried that :) Unfortunately the servos I have weren’t strong enough to lift the shutter even though it’s extremely light so went back to manual for the time being.
Cheers for comment folks, really appreciated,
DP.
“Blind Man” Bert Sierra
Actually, by my way of looking at it, the robot is playing a very weak game. But it’s hard to write strong heuristics for AI players in general, and Connect Four is no exception to the rule.
I have a more complete analysis of that conclusion here, on Facebook:
dobra-dobra
It’s a great project, but second movie is simply amazing and steals the show. How often you can see succesfull attempt on world record in yep per minute (ypm)?
David Pride
Most definitely. It’s beaten me on many occasions already :) As mentioned, it’s level of play is a trade off between how long it takes to calculate each move against how bored you would get as a player waiting for it. It could theroretically play a ‘perfect’ game each time, but you’d be waiting an awfully long time!
DP.
Hans Lepoeter
That’s neat, but whats with the scanning panel thing ? Could it be replaced with the camera ? Should be possible i guess ?
dobra-dobra
There is a camera below display. That panel is used as background.
David Pride
Dobra is correct, it uses the Pi Camera, the shutter / panel is to give a solid background for the object detection to work with, lighting is still critical but having the background there means it ‘only’ has to accurately identify red, yellow and a slightly grim shade of blue.
DP.
AndrewS
Maybe you could affix the button to the top of the Connect4 frame, so that lifting up the panel automatically presses against the button?
Gee ‘The Rabid Inventor’
Loving the vacuum florescent display :)
AndrewS
There’s more info on the maths behind Connect4 in https://www.youtube.com/watch?v=yDWPi1pZ0Po
David Pride
Oh no – Andrew S just leaked a major secret!
If you watch the video that he posted the link to, you’ll see why 4-Bot plays first ;-)
DP.
AndrewS
Sorry! ;-)
Dave
First let me say, this is a great project. I have one small suggestion. You could program it to flip up the when you press the button then carry out your current action, rather than flip up the board, press the button. You could get it to lower the board when it starts thinking.
That way your interaction is a button press, not a flip and a button press. Would make things a little easier to play.
Love it though. I can (and do) appreciate all of the hard work and time that must have gone into this. Great work
PS. the Gent in the second video say “yeah” a LOT! lol
dan3008
I wonder, do you think the software could be made to run quicker (or do more calculations) on a cluster of pi’s? Would be an intresting one to look into
AndrewS
Yeah, minimax is a tree-based search, so it should be easy to distribute different branches to different Pis, and then collate all the results at the end of your predefined search-time. (given that there are seven ‘slots’ on a Connect4 board, it probably makes sense to have your cluster-size be a power of 7)
But I guess if your algorithm (i.e. search depth) is “too good” then the computer becomes unbeatable, which probably makes it less fun to play against if you know you’re *always* going to lose? ;-)
“Blind Man” Bert Sierra
Key to minmax is also figuring out what measures to optimize. Since the game tree is relatively small by modern standards (about four trillion states, solved in the mid-nineties by brute force search), you might also consider using neural networks trained from optimal players, or genetic algorithm searches for optimal or near-optimal minimal AI strategies which would be minimax-based, but with the functions being minimized / maximized being computer-written, and you could also throw in a parameter which would say that quicker play would be better.
The computer can also make good use of the time between when it makes a move and waits for the scanner results to plan all the responses to the seven moves the human might make at each step. Thus, effectively, you can “hide” the computation time the computer is making for a response.
Again: since perfect play (“God’s Algorithm”) has been known since the 1990s, this would be the way to develop a strategy which would play an optimal or near-optimal game and yet would still fit within the memory and clock speed constraints of a Raspberry Pi, or possibly even an Arduino (much more arduous requirements for the algorithm there, of course).
“Blind Man” Bert Sierra
The proper way to keep the “fun” component there is to have perfect play always an option, or to allow the perfect player to coach players who want to analyze where they might be making mistakes. A perfect player can always be “dumbed down” by mixing in random moves with a selectable probability.
Better still, you would have heuristic players, such as I suspect this one is (it plays fairly poorly, actually) given different names, and then you would learn the weaknesses of each player and how to beat them. In theory, a computer player could do the same, exploiting the weaknesses of known human players to win even more quickly than perfect play might suggest.
“Blind Man” Bert Sierra
Actually, the computer could simply always play center first if playing first (traditionally this is the Red player, actually, not Yellow), and also know beforehand all seven proper responses to the seven moves a human might make if the human plays first (as Red).
That is a very simple opening “playbook” and then from there, from the time the computer drops its move to the time it receives the result from the scan of the human player’s move, then it could send out queries to GameSolver for what the seven optimal responses might be (requiring only that the Raspberry Pi be network connected).
The transcript of this game would be noted on GameSolver as http://connect4.gamesolver.org/?pos=44565532626225636, and by analyzing what GameSolver returns at each point it could play perfectly and ALSO hide the time it is thinking to the time the human is coming up with a move, effectively making the computation time require no delay whatsoever.
Computers are allowed to gang up on humans, right? That’s certainly what tends to happen in every sci-fi movie in which they show any intelligence at all. :-)
http://connect4.gamesolver.org/?pos=44565532626225636
CJ
this is awesome man great job!!!!
“Blind Man” Bert Sierra
[also posted to YouTube]
This is a superb design and knocks it out of the park. The scanner flip-up might have been better implemented as a fixed camera a foot away from the board, or so (akin to how Osmo games work). But aside from that one fact, I still love this project.
I’ve been thinking about GGP (General Game Playing) and ways for computers to come up with near-optimal play of arbitrary games fed “on the fly” into the system without encoding heuristics specific to any game; an advanced topic in AI. So I couldn’t resist putting the play of both players through analysis comparing against a perfect computer player (“God’s Algorithm” in combinatorial terms; which is a mathematical concept, not a religious one, btw).
My full analysis is on Facebook, but suffice to say the human player should have soundly beaten the computer. Indeed, aside from the first move, the robot makes five errors in a row which should have resulted in a win for red. In theory, the first player always wins if it plays perfect moves and no missteps. Connect Four games tend to end early with a lot of slots unfilled only when one player and/or the other are playing sub optimally. In my analysis, I’m not counting the deliberate error at the end which tosses the game suddenly back to yellow, since prior to that misstep red had a lock of the game in eleven moves or less.
I used GameSolver to examine the “perfect” moves — the transcript for the game there would be noted as:
http://connect4.gamesolver.org/?pos=44565532626225636
David Pride
Hi Bert,
Thanks for you’re obvious enthusiasm – really nice to see someone get a real kick out of something I’ve built. The online solver is a brilliant thing, very very cool. You’re right about the heuristics, it plays far from perfect game, but not tooooo shabby :) It’s also about to get a Pi 3 brain transplant which will also be extremely interesting. Others have also suggested a cluster which is another project that’s on my wish list.
The capture is done with the Pi camera, which is mounted just below the LCD screen, the lift up flap is just a solid colour background to help the camera.
We’ll be at the Pi Party if you fancy taking on the machine!
DP.
David Pride
UPDATE! – 4-Bot version 3.0 is complete.
Last night 4-Bot had a brain transplant and I upgraded it to a shiny new Pi 3 – how quick is that thing? :-D
This has significantly improved time to calculate the next move, previously the average was 5-7 seconds, which has now dropped to 2-3ish seconds having run a few quick tests last night.
Gotta love the Pi!
DP.
Comments are closed