Mathematicians Finally Find the Infinite Card Game

[00:00] you folks want to play a card game and not a  fun one one that's provably very boring well I   guess it's boring if you care about being able to  control your own destiny if you don't care about   that could be fun it's a children's game called  beg of my neighbor it's been around for a very  

[00:15] long time Charles Dickens talks about it in the  1861 book Great Expectations and it could be older   than that it could be centuries older it might go  back to when playing cards as we know them first  

[00:27] came to Europe however mathematician were not able  to crack this game until well just last year we   answered the major question about it and um it's  not made the game any more [Music] fun some of you  

[00:49] may have played the game before it goes by a lot  of different names camera person Alex what did you   used to call it as a kid beat your neighbor Out  of Doors beat your neighbor Out of Doors I don't I   don't know understand this country so anyway it's  got different names you may know it to explain the  

[01:04] rules um so I met up with my friend Mitha in  London recently she runs the YouTube channel   Looking Glass Universe I said hey while we're  catching up in the pub uh do you fancy a card game   here's how it went we get half of the deck each  your player one so there's the beginning of your  

[01:20] deck the way this works your player one you go  first a single card in the middle there a number   we don't care number card we don't care number  card we don't care and we alternate until someone   does a face card the fo has to pop out of the coil  okay so aces are face cards in fact Ace is the  

[01:37] fourth face card cuz they go Jack queen king Ace  okay and I've now got a number of cards I can put   down and I have to get another face card otherwise  you win this this this trick all right which what  

[01:51] we call a round for some reason and so Ace is the  fourth face card so I have four so ready one two   and the problem is three oh an eight now you've  got four oh Jack a now Jack's are tough cuz that's  

[02:06] the first face card so I've only got one chance  to not lose this round and I got uh number card   so you get to pick up all of those all right in  order doesn't seem like a good thing whoever gets  

[02:18] the whole deck first wins oh okay so you need to  get these cards I need to get those cards whoever   wins around goes first on the next round all  right mither and I started playing the card game   and then we kept playing the card game game and we  kept playing the cars going backwards and forwards  

[02:33] neither one of us winning and it kept going this  must have taken ages and going and we started to   wonder how long can this game go on for one two  three yeah is that great we're having fun okay

[02:47] um okay so hey could we be here forever the first  reference to these questions is actually from the   1989 book The mathematics of games and towards  the back here it discusses begger my neighbor and  

[03:06] poses three questions how long is a game likely  to last can a game get into an infinite Loop if   it cannot can we hope to prove this spoiler we now  know the answer to B and C it can which means we  

[03:20] don't have to prove it can't but how long can a  game go on well all we really need to care about   is the starting arrangement of the car because  as mither and I were very aware playing this  

[03:33] in the pub you don't have to make any decisions  you have no choices nothing you do changes the   outcome of the game as long as you don't make any  mistakes it's completely deterministic whatever  

[03:45] order the cards are when they start determines  the outcome of the game as they very politely   say in here this is an automatic game with no  opportunity for skill which is why it is so  

[03:59] suitable for family play I mean I guess the point  is you don't have to have any skill to play it but   it does have all the illusion of the excitement of  a game like you've got to avoid going out on each  

[04:12] trick and you can see the decks getting bigger  and smaller so it feels like a fun interactive   game but it's not it's all predetermined  so of course I knock together some terrible   python code to see if I could find a really long  game by just randomly shuffling a deck of cards  

[04:30] playing the game forward and keeping track of  how long it went for and I did okay I got a game   that went for 4,513 cards that 630 tricks which I  thought was pretty impressive the current record  

[04:45] however is a game that went for 8,344 cards which  was over 1,000 1,164 tricks and actually here is a   plot of over time the current world world record  for longest game played and what you'll notice  

[05:05] is that they're roughly linear as we've had more  processing power to check more random games we've   just happened to find longer ones it's pretty  much exactly random and actually very early on  

[05:19] even in the 1989 book people noticed that as  you're playing Begg of my neighbor it's kind   of got a halflife so roughly every 20 tricks  there's a 50% chance the game will have ended  

[05:32] and you just have an exponential decay because  of that which is quite neat because it's such   a neat exponential decay like radiation with a  halflife we can just use an off-the-shelf formula   to predict the longest game we will see for the  number of Starting Games we've checked now the  

[05:48] 250 in that equation is just the average number of  cards per game that's just the mean and then the   exponential drop off predicts that I checked well  I checked around 1 and a half billion games and if  

[06:00] you put in a billion you see yeah you should be  expecting somewhere around 5,000 is cards in the   maximum game and as computer power gets better and  better we can check more and more starting games  

[06:13] we will predictably find longer and longer games  which are still finite in nature but why can't   we just use a computer to check them all how many  starting Arrangements can there be well famously   there's a lot of ways to shuffle a deck of cards  in this case it's not nearly is bad because once I  

[06:30] take out all the face cards all of these cards are  fungible these are all indistinguishable we don't   care which is which these are just IR relevant  padding we just care about where these are so  

[06:43] if I was to put in let's say the Jacks first I've  got here 36 boring cards plus these four exciting   cards that will be 40 cards and so where these  go is just 40 choose four because we don't care  

[06:59] like we don't distinguish between the Jacks so  if we did 40 choose four imagine they shuffled   in that would give us all the combinations we've  now got 44 cards so 44 choose four to put in the  

[07:11] Queens 48 choose four to put in the Kings finally  52 choose for once the aces go in so as far as   begar my neighbors concerned there are only around  about 6.54 * 10 20 possible starting decks we've  

[07:28] only checked at the the moment up until about  10 to the 15 games so 10 to the 20 is still a   way off because the 10 to the 15 checks take  take a long time we're not there yet one day  

[07:43] we will have checked every single possible  game of Begg of my neighbor I don't know what   year that's going to happen in we could try and  extrapolate from the plot maybe it's Mor's Lorry   at some point we will know what the longest game  is in the meantime it's still an open challenge  

[08:00] see if you can find a longer game if you want  more information about the history of the records   I will link to a website below made by someone  called Richard man who is now a mass professor   at the University of Leeds although they started  the site well before that and it accidentally  

[08:14] became the central Focus point for current world  record for very long games of beggar my neighbor   and actually Richard has been very helpful putting  this video together he kindly answered all of my   questions so huge thanks to Richard by the way  if you want to try solving a puzzle of your own  

[08:30] that's not quite as involved as the ones in the  video this video is sponsored by Jane Street   fantastic financial company who sponsor lots of  my videos they are running the Academy of math and   programming soon amp applications open details  in the description and at the end of the video  

[08:44] I have one of their decommission puzzles you can  try it's I had a lot of fun solving it so that's   at the end however it occurred to me because  beggar my neighbor is completely deterministic   once you've shuffled the cards that's it you could  have a a championship where people competing don't  

[09:02] even have to show up I can just tell them oh  by the way here's the shuffle deck you were   allocated for your game and here's who won cuz  my code can work that out very quickly and then   I realized wait I could have a championship where  people don't even have to know that they were in  

[09:17] the championship so at the moment I have 2,561  supporters on patreon and I thought it be very   funny to have a standup Mass patreon wide champion  ship where everyone plays everyone else and so  

[09:34] I've written some code to do that I'm going to  set it running right now and if you support me   on patreon you're in the mix and you're about to  play everyone else okay here we go and start it's  

[09:49] happening the first ever official standup math  World beg of my neighbor card Championship 2025   happening right now at the rate of just over  10,000 games a second uh we'll come back when it's  

[10:07] done and we're done so all 2561 patreon supporters  played each other for a total of three, 278,000   180 games it actually took a little bit longer  than it should have so it should run in under five  

[10:23] minutes but at the same time I was exporting the  details of every single game into a separate text   file for every single patreon supporter so if you  do support me on patreon I will email you a text  

[10:37] document and it will have your complete breakdown  and we'll start by having a look at some of those   so I'm going to pick I've got a folder here with  2 and a half th000 text files and here's what the   text files look like this is the one for Lis flow  so hello Lis flow thank you for your support here  

[10:52] are your standup Mass official 2025 Begg of my  neighbor World card championship results and   look at this it's got every single other patreon  supporter cuz you played everyone and it's got   exactly what happened in the game pick a game at  random here you lost against Craig F oh sorry to  

[11:09] hear that in a game that lasted 13 tricks required  87 cards to be played quite a quick game and then   I give the starting hands for both players zero  that's just like the cards that could be anything  

[11:21] and then 1 two 3 and four are for Jack queen  king Ace so the number just represents how many   cards the other person can play you can swap in  you can recreate the exact hands if you want and  

[11:34] play any of these believe me when I wrote the  code and I was testing all of this I did then   go through and manually play some of these games  to make sure they worked oh you won against ASDF   I didn't censor one-word names and you know who  has one of them three blue one brown yes Grant  

[11:50] supports me on patreon which means every other  patreon supporter you've now played three blue   one Brown in a game of beggar my neighbor now in  here everyone's names are censored they won't be  

[12:02] in yours though so you can search through and  see did you win or did you lose when you played   Grant but what you all want to know is who won the  championship let's find out I'm going to pull in  

[12:15] everyone's results and then rank everyone from  most games one right down to Fest and Fest is   Connor sorry Connor you only won 1,25 games you  were just beaten out by Don Luigi who W 1,26 and  

[12:31] then you can see it gradually goes up this is  like very very fast patreon credits I'd like to   thank everyone that you're watching them fly by  oh and who's at the top Jeremy congratulations   Jeremy with 1374 games six games out before  second place you are the official winner of  

[12:49] the 2025 World beg of my neighbor standup Mass  Championship honorable mentions Johan and David   so that's finite games speaking of which we can  check back in with myself and Mitha playing in the  

[13:05] pub past Matt and past Mitha are still going and I  can guarantee they are playing a finite game isn't   that convenient however we don't care about finite  games we need to move on to infinite games we want  

[13:18] a game that's going to last forever and when this  was discovered last year in 2024 while someone   named Braden Cella I was so excited everyone was  because we didn't think this was was going to be  

[13:30] possible for a very long time people have been  looking for this Loop even before the mention in   the book from the80s back in the 60s we believe  the mathematician John Conway came across this   game realized that an infinite Loop would be super  interesting couldn't find one and they speculated  

[13:48] that it would be very difficult to do it and they  named it an anti-h Hilbert problem and the Hilbert   problems were problems which were very important  and everyone should start working on them in math   itics an anti-h Hilbert problem Conway said was a  problem which is very difficult but no one should  

[14:06] be bothered doing like it was so pointless  people shouldn't even bother dealing with it   Braden however didn't listen to them Braden gave  it a go and here's what he found my name is Bren   cassella I graduated with a degree in computer  science I really was curious about what made some  

[14:26] problems difficult because you know not really  understanding a lot of math you think we can do   so much with it and understand so much you know  what really can't we do and why can't we do it so  

[14:40] I looked up unsolved problems in mathematics and  found one that was very um you know approachable   and understandable Bren very kindly had a call  with me so he could talk me through the details   of what he managed to achieve and I think I've got  my head around it now the first key point is that  

[14:58] long but finite games actually give us no Insight  whatsoever into Infinite games because those long   games they just happen to have the right amount  of noise or whatever so that they can survive  

[15:11] the half-life process for a very long time but  every single state they're going through so at   the end of each trick once the players have their  cards back we can consider that a snapshot of the   game that's the current state of the game and  every single state it goes through is different  

[15:28] until eventually one player wins so the final  state is that one player has the null pile for   an infinite game we need to have a state reappear  because there's only a finite number of states and  

[15:42] because it's completely deterministic from one  state to the next when you're playing the game   if you hit a state that's happened before you'll  be in an infinite Loop and that Loop is probably   not going to be as long as these you know hundreds  over a thousand different games so actually we're  

[16:00] looking for some different properties so actually  analyzing the long games not going to help what   will help however is analyzing smaller easier to  find infinite games here's an example of a tiny  

[16:15] game where I'm going to give the both players  only three cards so there's one deck there and   the other one you know I'm going to use Reds  for the unimportant cards and two black jacks  

[16:29] so I've put them this way up so you can kind of  monitor what's happening in each player's deck   this player will go first puts a jack this person  will then play and then lose so they will put it   over here then they will play they'll play they'll  lose so that goes over there and if you're paying  

[16:48] close attention we've now got the situation where  it's you know uh unimportant unimportant or number   number jack number jack number but as soon as we  start playing again play play play one is exactly  

[17:02] the same state that swapped and we can keep doing  that play play play back down there and so this   tiny like toy version of the game will carry on  infinitely because you're just swapping from the  

[17:17] same state well basically the few cards are going  backwards and forwards and you will stay in this   Loop infinitely this is an infinite game here's  another game that repeats but instead of three   cards each we're going to have four cards each so  we're gradually getting closer to where we have  

[17:31] 26 cards each that's going to take a while okay  so we play the first trick that's the result of   the first trick very familiar Jack and a number  card over here this player won though so all of  

[17:44] these get put onto their pile and that's worth  remembering it goes number number King number jack   number and again that could be any face card apart  from a jack up next short boring round they've won  

[17:58] the trip brick and that's suspicious it's exactly  the two hands we started with they have swapped we   could carry again they'll swap back and that will  keep repeating over and over and the kind of the  

[18:10] key thing to take away from this other than these  games repeat is that you've got this suspicious   Jack in a number that keeps showing up and then  you got this other big chunk of cards that seems  

[18:24] to just get passed around by going to these super  small versions of the game it makes it very easy   to find games which repeat infinitely however  they're so small there's very little insight into  

[18:39] why they're repeating we want to find a middle  ground with enough cards that there's some insight   to be gleaned but not so many that we can't find  any and a lot of people go straight to the middle  

[18:51] of the deck in fact this is where Braden started  looking for hands which have 13 cars each and   lead to infinite game that however is impossible  there are no cuz there's small enough options that  

[19:04] we can check them all there are no infinite games  using exactly half the deck but there is one very close so here's an infinite game that was  known about at least by the late '90s there  

[19:21] a paper from 99 I link to below and it's two  more cards than half the deck so there are 14   each total of 20 8 I'm going to play through a  trick or two and we'll see if we can spot any patterns it's the one thing to  notice at this point we played  

[19:43] for a little while player one oh Lion  Share of the deck player two it's got   a nothing card a Jack and a nothing  card but what's going to happen next

[20:05] okay we a little bit later on and now we've swap  sides player one is down to the something Jack   something and player two has all of the cards  in a very familiar order and this is going to  

[20:17] keep repeating and it's very interesting we've  kind of got a Jack and a single one over there H   anyway leaving that for now what Braden thought  they would do is see if they could get smaller  

[20:30] games that repeat and combine them into bigger  ones and you can just kind of mush them together   so that as you're playing along you kind of have  one repeating and then the other one repeating   and so you can take smaller repeating games and  build up into bigger and bigger repeating games  

[20:45] and that's exactly what Braden did the issue was  you need to build them up in such a way that you   eventually hit exactly 52 cards so they have to  be the right sizes obviously have to be combined   in a way that they work and you need to make sure  you've got the correct distribution of the Court  

[21:02] cards or the face cards you have to have four of  each and not every combination of ones that repeat   that produce a repeating pattern necessarily have  those properties so Bren had to write some code to  

[21:14] search for all the ways you can put the different  repeating bits together such that you then spit   out another repeating pattern and then check that  it's a standard deck check that it's the correct  

[21:27] number of cards and check that you've got four of  each of the four different face cards so I end up   finding all of these standard deck games none of  them ever become balanced so n none are ever valid  

[21:41] you can never actually get to those ones Braden  had found an infinite Loop of game States about 60   or so game States all the way around none of them  were perfectly balanced none of them had two packs  

[21:55] of 26 cards each so then Braden took each of those  States and revers them and while forwards you   always go to one specific State afterwards on the  way back there actually multiple previous states  

[22:09] that could have fed into that so Braden took each  of the different states in the loop reversed them   all as far back as they could go for where there  were valid states that could lead into them and   discovered none discovered absolutely no balanced  set so they had found the infinite game there was  

[22:28] just no way to start it so like fine they  found another infinite game with a regulation   deck no balance starting points they ended up  finding about 10 different infinite games with  

[22:40] a regulation decks worth of cards but across all  10 or so of them there were no starting points   Braden was Finding infinite games but there were  games that could never begin so what's a computer  

[22:53] scientist to do Braden was finding all these  infinite gains that there was no way to start   them I have to say what an arbitrary constraint  that is these are all perfectly valid Solutions   almost indistinguishable from the correct solution  we just happen to have a game where you deal equal  

[23:10] number of cards to each player when you start if  we didn't have that constraint these would all   work in fact if we didn't have this distribution  of cards like the certain number of different   types of face cards in a deck then it would be  different it's just what we discover in terms  

[23:27] of the structure and just putting in zeros  and ones and twos and threes and fours into   different orders to see which repeat according  to these rules the fact that one particular   group of constraints on that leads to a card  game that people actually play I think is very  

[23:42] interesting but there's no reason for those to be  the rules and Braden was finding great solutions   they were just falling apart at this one last  hurdle but it meant that the ones that they   were finding were on the right track they had  to find one with a single Balan state in there  

[23:58] somewhere and the wonderful side effect of finding  all these uh false positives if you will is that   Braden was learning a lot about what these games  look like when they are an infinite game and so  

[24:10] what they did was pull apart these games look at  the structure underneath them and then find a new   way to build up a new infinite game here's what  bradden noticed during the course of an infinite  

[24:22] game there would be a state at some point which  was kind of like the key State and that's where   player two would a Jack and have some kind of  unnecessary number card on the end players one  

[24:34] hand would have a bunch of cards at the beginning  which I'm just going to represent as a mash of   cards here some number of cards then a Jack  and then another pile of cards here and then   a Jack and then another pile of cards and then  a Jack and then a number card and these piles of  

[24:52] Cs or these runs of cars between the Jacks Braden  referred to as pieces so you'd have one piece here   Jack piece Jack piece Jack number card and  these pieces these runs of cards between the  

[25:04] Jacks pretty much operate independently when I was  saying before you could combine games which repeat   together by like smooshing them together this  is the same idea but these don't individually   have to be games that would repeat on their own  these are just units pieces as such of cards  

[25:21] that move together during this infinite game and  the cards interestingly during the course of the   game these pieces would kind of move over over to  the other player and then move back like this was   like storage for the pieces and they'll transfer  over then transfer back and eventually the whole  

[25:36] system would repeat I will link to the paper below  it's actually still a work in progress I will link   to the current version on archive they're still  fleshing out exactly how they're going to explain   it but in short instead of searching for other  games that repeat infinitely and trying to put  

[25:51] them together they could just try and find these  individual pieces and then make sure initially   that they're the right size and distribution of  cards to get a standard deck and then check all   the states they go through and all the feed in  states to find one that's perfectly balanced and  

[26:06] to simplify their life slightly they didn't even  bother with the third one CU you can force the   third one to just be two nothing cards so that  simplifies what we're looking for and then over   here once they locked one in like one that six  long that greatly reduces the permutations for  

[26:24] the possible cards that you would need to find  another one and they came up with a very clever   wave using filters to be a to search for these  pieces pretty much in isolation and then run their   code to combine them all together and eventually  it worked and here it is the infinite game any  

[26:40] one of these starting hands with little Dogg ear  means the top player goes first plane boxes bottom   player goes first these are all perfectly balanced  regulation deck games they all feed into that same  

[26:53] Central Loop of 62 different states which will  repeat forever a phenomenal achievement to find   and for those of you wondering the game mither and  I were playing was not the infinite game it was   a finite one we were playing the longest no and  finite game if that disappoints you my good friend  

[27:09] Matthew scroggs has made a masteron bot which  is playing the infinite game you can see here   every 3 hours it posts the next move between who  iuma Alice and Bob playing the infinite game and  

[27:23] it started in April last year once the infinite  game had been discovered now Tech technically   it's already looped six times about to Loop  seven times according to the pure math version   but we don't care what the number cards are but  as you can see Matt showing the exact cards and  

[27:39] they take a lot longer to repeat if you want every  single card to get back exactly where it was and   we care about what they are see this post here on  the 5th of April 2024 that's the first one in the  

[27:51] official cycle and this exact move will happen  again with identical decks on the 5th of January   in the year 2034 although Matt scrs is pretty  convinced the bot will break around 2029 and  

[28:06] he won't bother fixing it if you've enjoyed this  journey using math and computer science you first   of all will enjoy the puzzle I promised coming  in a second and if you're graduating from high   school this year 2025 you might enjoy Jane streets  amp that's their Academy of math and programming a  

[28:24] five-week residential Course in New York City for  high school students who are going into University   either later this year or next year and you want  to do some more math and computer science for   five weeks it's so good every day you're solving  puzzles like the puzzle I gave to Mitha when we  

[28:44] met up before we played the card game in the pub  the puzzle setup is that you're trying to guess a   number someone is thinking of and they're saying  higher or lower except if they say the same thing   three times in a row three highs or three low  was you lose this turns what would have been a  

[29:01] standard binary search puzzle into something much  more intricate interesting and as we discovered   difficult well let's lock in binary search 10 all  right that's your second guess mhm and it's still  

[29:14] three it's still three consecutive yeah okay so  when I say lower okay now you're like uhoh okay   I'm in trouble well then I have to guess one cuz  you have to go one yeah cuz I don't want to L you   still got two more guesses up your sleeve yeah so  that's a problem but because you got six guesses  

[29:30] there's enough risk you might have to go racing  back up again so this cuz you're coming up has   to favor up Y Cool okay okay yeah oh nice that's  kind of interesting that you have to like favor   the direction that you like yeah and so that's all  six guesses now what if we'd said lower here yeah  

[29:50] and we got here I say high oh no yeah I'll put  the exact wording of the individual questions you   have to solve below but in general you're trying  to work out a strategy and here we're trying to   crack the maximum range of numbers you can always  correctly identify the guest from if you have six  

[30:07] guesses as you can see we've picked 20 as the  midpoint and we're assuming the first guess is   lower by symmetry you get the top range as well  and it was fun I love standing around a whiteboard   trying to solve a mass problem coming up with  new notation bouncing backwards and forwards on  

[30:22] different ways to solve it and if you enjoy this  sort of thing you're going to love amp based in   New York City James Street cover all the cost of  attending amp as well as a $5,000 scholarship for   students who face some kind of barrier in their  education it's a lot of fun and get to meet  

[30:37] me I come and give a talk that's pretty exciting  applications for amp close on the 12th of March so   either you apply or tell someone you think should  apply thank you J Street huge thanks to myth and   for being so tolerant and playing that game with  me doj a channel Looking Glass Universe I'll link  

[30:53] to it below and thanks to you for watching  and if you're still watching this late in   the video you either are a patreon supporter or  you should be a patreon supporter come on if you   supported me on patreon you would have been in the  championship who knows what I'm going to do next  

[31:09] probably this again that was fun thank thanks  for joining me for this yeah no this was great   so what do we do next well hey if you enjoyed the  excitement of this have I got a card game for you

[31:21] okay e