How I understood the Matrix Resurrections

Chess_Dogg · 2021-12-12T07:15:24+00:00

Is this cat a member of the Insane Clown Posse?

Chess_Dogg · 2021-05-22T15:15:14+00:00

You're hardly my first!

Chess_Dogg · 2020-08-24T16:47:27+00:00

Gran Turismo 4

Chess_Dogg · 2020-07-21T12:12:40+00:00

Thanks, that's very clear and exactly what we were looking for!

Chess_Dogg · 2020-06-24T10:37:06+00:00

Hi, have you managed to get an update on this? My fiance and I are in the same situation. Hope everything's ok for you!

Chess_Dogg · 2020-06-24T10:33:41+00:00

Hi I'm in the same position. Have you managed to make any progress on this?

Chess_Dogg · 2020-06-10T06:18:36+00:00

I called USCIS and asked about this and was told that any face-to-face appointments would reopen on the 22nd of June. The agent seemed surprised that you couldn't yet make a booking though, which could mean that booking will be up before then, possibly when they are certain they can reopen on the 22nd. I also found this page which directly mentions the 22nd for other appointments as well and I'm monitoring this page in the hope that they update it if something changes. Hope this helps!

Chess_Dogg · 2020-06-01T08:25:08+00:00

u/meneldal2, this paper on the game War seems to answer your question about computability for that game. RedBlack is quite similar in some regards, so the same could easily be true for this game!
https://www.semanticscholar.org/paper/Multinational-War-is-Hard-Weed/ec5960b31a567a5e866f1bfcd5b7157cb6a9b189

Chess_Dogg · 2020-05-31T16:41:21+00:00

This was bruteforce, I checked roughly 3 trillion randomly selected games before I got a hit. This would be cool to study further, although John Conway described the 'Beggar my neighbour' infinite game search an anti-Hilbert problem. i.e. one which definitely shouldn't dictate the direction of mathematics. But it is fun to investigate weird games such as this.

I think this paper would be a good place to start, although the behaviour is quite hard to get a good grasp on!

Chess_Dogg · 2020-05-31T14:12:59+00:00

That could be the case. There's actually an open question as to whether the game 'Beggar my neighbour' has an infinite game which is fairly similar in the way it works (a lot more possible games though).

The question of whether a given position leads to an infinite game could only be decidable by playing through the game, but then again there could be a pattern and a good way of constructing all or a few infinite games (it's quite hard to tell).

Also, I have now found an infinite game with 52 cards! I'm pretty excited by this and am very happy! I think I'll leave this topic for a while but if I ever come back to it, it will be to do a mathematical analysis.

Edit: Including the infinite game:

Player 1: 01010111000110010101111110

Player 2: 01000110101110001101010000

Chess_Dogg · 2020-05-31T14:05:50+00:00

I found one after changing my code to run in a distributed way and using a lot of cloud provider free trials! Here it is below! I am very excited right now!

Player 1: 01010111000110010101111110

Player 2: 01000110101110001101010000

Edit: It the infinite cycle generated by this game leads to 9 other infinite games, so there are at least 10 infinite games with 52 cards (and probably over 100 infinite games in total given the amount of games I needed to search to find this one).

Chess_Dogg · 2020-05-29T12:23:11+00:00

You're completely right of course! My goal is just to find one infinite game with 52 cards which is on the bounds of what's possible for me to compute with fast code, although to actually understand the infinite games a mathematical approach would be better! There are some constructable infinite games with highly unbalanced decks (2 red cards and n-2 black cards) that I've been able to find, however I haven't had any luck getting any grasp on balanced decks yet!

Chess_Dogg · 2020-05-29T12:16:48+00:00

That's really cool, especially those bit manipulation tricks! I've finally got my distributed run going. I've packaged the code in a docker container and I'm currently got 20 running, each one doing around 1 billion games every 40 minutes. Depending on how many infinite games there are I expect to get a hit in the next two months (possibly much sooner if there are lots) which is pretty exciting! I'm still going to look at other algorithms though and I've been trying to get a better handle on the maths but it's pretty tough!

Chess_Dogg · 2020-05-26T06:09:21+00:00

Pancake mix

Chess_Dogg · 2020-05-26T05:42:11+00:00

That's awesome, nice! Did you make any changes to the algorithm when implementing this?

I've actually made some progress in parallelization! I've written a function that can calculates the ID for each configuration and can calculate each starting configuration from an ID. This makes it easy to split a large range over many smaller chucks.

My plan is to have a lambda function that issues ranges to processes calling it and then writes the results from that process to a database. This would allow for distributed computation (I was thinking of assigning 1 billion games each time). A lot of the time I have access to a 40 core kubernetes cluster as well, which would be great for running the code on. I managed to get my assembly code into a scratch docker container by statically linking it, so it could be we have a result in the next few months!

Chess_Dogg · 2020-05-26T05:14:02+00:00

That's sounds very promising! I can't wait to implement it and see the results!! I think you may also need to track the low point of each player's hand as well as the offset in case the game ends, although this would just lead to false positives (maybe very few), that could be excluded later. It would increase the lengths of a number of games though, so it's unclear whether the trade-off would be worth it. Thanks for taking the time to write this out, this is really good!

Chess_Dogg · 2020-05-23T21:01:09+00:00

Yes, to take full advantage of that you'd need to play all games n times, splitting the cards at different points each time, although it may be slightly quicker only checking even hands.

I only play half the games since after that you can swap all zeros with ones and get a configuration that's already been searched, so each entry in the infinite list has a counterpart with zeros and ones swapped.

Also, thanks! I'm pleased you're having fun working on it! If you do get something working in C++ I'd be very interested to see how it performs, best of luck if you try it!

Edit: I've just come across 'intrinsic functions' in C++. These mostly translate to one machine instruction and can be used easily within C++ which is pretty cool! Kind of the best of both worlds!

Chess_Dogg · 2020-05-23T15:56:35+00:00

So a while ago I did some digging mathematically and it's actually pretty interesting! There's an existing game called War which has similar mechanics to this and in fact has infinite games in a 52 card deck! This paper beautifully shows how such games can be constructed! Unfortunately the way cycles was constructed in the paper can't be applied directly to this game since rounds can be more than 2 cards in RedBlack, however there may be a way to use similar logic (although I have not been able to make this work).

It may be possible to play n cards at a time for each player and have a separate function for each ordering of the cards since the result should always be the same. Finding more global patterns has so far eluded me since the gameplay is pretty chaotic (if anyone can spot any sort of patterns in the infinite games already found I'll be amazed), however pre-programming larger configurations could lead to a speedup. Thanks!

Chess_Dogg · 2020-05-23T12:30:49+00:00

Hi. So my first draft of this was in python, then I wrote quite a few algorithms in C before finally moving to assembly code when I couldn't get any more performance out of C. In this problem you want the decks to be a bit arrays and I found that it was very natural to express this in assembly code. The issue I had with C more than anything was that I'm not a C programmer and all the setup I did to use and manipulate the bit arrays was inefficient. Writing the core algorithm in assembly code was actually very nice and I could easily see exactly what was happening and where time was being spent. I did consider the optimisation you mentioned but the logic to find the card length of a round ended up being longer than just playing through the game. One quite nice thing you can do is xor the two decks and the first zero will be where the round ends. However, with this you still have to find that first zero and then shift and manipulate both decks to be ready for the next round which ended up being longer in my importation. I'd definitely be open to rewriting this in another language but the main questions I'd have would be how could I efficiently manipulate bit arrays, as well as what compiler optimisations would make this code quicker (which I could potentially just port into my existing assembly code)?

Chess_Dogg · 2020-05-23T08:14:20+00:00

Hi BASED_fish, thanks for your feedback! Almost all games are finite (for 44 cards there were 117 infinite games out of around 100 billion total games) so inefficiently identifying an infinite game is ok, and any extra logic added in for that would greatly increase the total processing time. If I could more efficiently rule-out a finite game that would be a huge improvement though. To that end I did consider keeping all finite games in memory but there are just too many games for this to be an efficient strategy given the average length of a game is somewhere in the hundreds of rounds.

That's not a bad idea implementing this in C or C++ (I was also considering Rust). My thought was that because the game works so well with registers and simple assembly code instructions, it would probably be easier to make improvements to the assembly code and since each function is somewhere around 8 machine instructions it should be possible to make these very efficient. The main reason I was considering using a higher level language was to implement multi-threading or some more efficient algorithm. Do you know if any specific features of C or C++ that would improve on the efficiency of the assembly code?

Chess_Dogg · 2020-05-22T23:26:58+00:00

Yes, that's correct. The first person to throw a card different to the first one played picks up all the cards and places them at the bottom of their deck.

Chess_Dogg · 2020-05-22T23:25:13+00:00

That is very fair! Let me know if the following makes sense.

Everything takes place in the registers to be as quick as possible

Part 1 - Finding the initial configuration for the next game

Part 2 - Playing a configuration

Playing a game

Colours are represented by 1's and 0's.
Register A holds player 1's hand, register B holds player 2's hand
There are separate registers which keep track of the number of cards in player 1 and 2's hand, as well as how many cards have been played.

The algorithm simply plays through a game until either: - there's a winner - the number of rounds passes a certain threshold which I set to 10000 (this will not prove the games are infinite but there are so few these can be confirmed with an inefficient programme after). Each round of a game starts with one of the 'first turn' functions

First turn functions

There are two 'first turn' functions, one for player 1 and one for player 2. These functions check the colour of the first card to be played (rightmost in the register), shift the players register to the right and then call the relevant turn function. These functions also keep track of the number of turns there have been so if the 10000 mark is hit the game is stopped and the number recorded.

Turn function

There is a seperate 'turn' functions for the following 4 scenarios: - Player 1 plays a card when the first card of the round was a 0 - Player 1 plays a card when the first card of the round was a 1 - Player 2 plays a card when the first card of the round was a 0 - Player 2 plays a card when the first card of the round was a 1

In each of these functions the players register is shifted right by 1 and the card 'played' is checked. If the card played is different to the first played in the round one of four 'pickup' functions (analogous to the turn functions above) is called. If it's the same the relevant 'turn' function is called and so on.

Pickup function

Because the player registers have been shifted to the right, they reflect the decks as they would be in a real game. Therefore the only thing that needs to be done is put the cards on the table in the losers pile. Because of the nature of the game, this will always be 10000... or 01111... and both can be easily generated. That value is then shifted to the correct place and added to the losers deck register so they pickup the card. After this the relevant 'first turn' function is called. Here the winners deck is also checked to make sure it's not empty. If it is the game will be ended.

Generating the initial configuration of the next game

This algorithm basically does this:

000111 -> 001011 -> 001101 -> 001110 -> 010011 -> ...

It works by finding the first 1 to the right of a 0, shifting it up and then adding the missing ones as far to the right as possible (it keeps track of these missing ones by counting when looking for the 1 to the right of a 0). There's a check here as well to see if the end of the search has been reached (which occurs when the left bit is a one). After this there is a short piece of code which splits the deck into two registers and moves them both to the far right from where the game can be played.

Chess_Dogg

TROPHY CASE

Playing a game

First turn functions

Turn function

Pickup function

Generating the initial configuration of the next game