{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"markdown","source":"# It's Easy for Neural Networks To Learn The Game of Life\n\nThis notebook is a response to the recently published paper: \n\n**It's Hard for Neural Networks To Learn the Game of Life** by Jacob M. Springer, Garrett T. Kenyon\n- https://arxiv.org/abs/2009.01398 \n\n> Efforts to improve the learning abilities of neural networks have focused mostly \n> on the role of optimization methods rather than on weight initializations. \n> Recent findings, however, suggest that neural networks rely on lucky random initial weights of subnetworks \n> called \"lottery tickets\" that converge quickly to a solution. \n\n> To investigate how weight initializations affect performance, we examine small convolutional networks \n> that are trained to predict n steps of the two-dimensional cellular automaton Conway's Game of Life, \n> the update rules of which can be implemented efficiently in a 2n+1 layer convolutional network. \n\n> We find that networks of this architecture trained on this task rarely converge. \n> Rather, networks require substantially more parameters to consistently converge. \n> In addition, near-minimal architectures are sensitive to tiny changes in parameters: \n> changing the sign of a single weight can cause the network to fail to learn. \n\n> Finally, we observe a critical value d_0 such that training minimal networks with examples \n> in which cells are alive with probability d_0 dramatically increases the chance of convergence to a solution. \n> We conclude that training convolutional neural networks to learn the input/output function represented \n> by n steps of Game of Life exhibits many characteristics predicted by the lottery ticket hypothesis, namely, \n> that the size of the networks required to learn this function are often significantly larger than the minimal network \n> required to implement the function.\n\nWhich was further discussed in the blog post:\n- https://bdtechtalks.com/2020/09/16/deep-learning-game-of-life/\n\n\n# Update\n\nGame of Life forwards can be solved with only 10 neurons and 13 weights!\n\nSee the [Smallest Possible Solution](https://www.kaggle.com/jamesmcguigan/its-easy-for-neural-networks-to-learn-game-of-life#Smallest-Possible-Solution) section."},{"metadata":{},"cell_type":"markdown","source":"# Previous Attempts\n\n\n\nThe first attempt at getting a neural network to train to 100% accuracy had 128 CNN layers, which is greatly oversized compared to the theoretical minimum. \nHowever it reliably trains from random weight initialization and acted as proof of concept that a neural network can indeed be trained to 100% accuracy.\n- https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-first-attempt\n\nA second attempt was made to create a miniamalist neural network `2*(3x3) + 2 + 1` and manually hardcode the weights, which turned into a tutorial for how to implement counting and boolean logic gates using linear algebra.\n- https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-hardcoding-network-weights\n\n\nIt turns out (explained below) that minimal network architecture required for the Forward Game of Life function is actually `1*(3x3) + 2 + 1`"},{"metadata":{},"cell_type":"markdown","source":"\n# Training from Randomized Weights\n\nHaving manually found solutions for a minimalist neural network architecture, \nthe question is if such a network can be trained using gradient decent starting from random weight initialization?\n\n\nThe choice of activation function has great significance here.\n\nWhen using hardcoded weights, I ran experiments trying to train individual layers from random with the rest hardcoded and compared the results when using different activation functions.\n\nReLU1 and Tanh where able to solve only the final 1x1 output layer. LeakyReLU could also solve the middle 2-channel 1x1 layer. However all three had difficulty with solving the 3x3 Sum2D layer starting from randomized weights.\n\n[PReLU](https://medium.com/@shoray.goel/prelu-activation-e294bb21fefa) is a version of LeakyReLU, but with a parametrized weight for the negative slope. \nThis feature greatly improves its ability to solve the Game of Life Forwards problem and can (usually) solve the entire network starting from `nn.init.kaiming_normal_()` initialized weights.\n\nKaiming is similar to Xavier initalization, but corrects for the asymmetric nature of the ReLU function.\n- https://towardsdatascience.com/weight-initialization-in-neural-networks-a-journey-from-the-basics-to-kaiming-954fb9b47c79\n\n\nI tested  variety of minimalist architectures to discover the smallest network capable of reliably \nsolving the Game of Life forward play problem, and the frequency of which \"lottery ticket\" initialization causes non-convergence."},{"metadata":{},"cell_type":"markdown","source":"# Minimalist Network Architectures\n\nNetwork architectures where chosen with 1, 2 or 4 convolutional 3x3 layers, \nboth with and without passthrough of the original board state after the convolutional layer.\n\nIn hindsight it may have been better to use ReLU1 as the final activation function rather than sigmoid \nas we are outputting binary values.\n\n\n\n[GameOfLifeForward_11N.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_11N.py) - 1\\*(3x3) + 1\n```\nConv2d(1, 2, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nConv2d(2, 2, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(2, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid() \n```\n\n\n[GameOfLifeForward_1N.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_1N.py) - 1\\*3x3 + 2 + 1 (without passthrough)\n```\nConv2d(1, 1, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nConv2d(2, 2, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(2, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid()\n```\n\n\n[GameOfLifeForward_1.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_1.py) - 1\\*3x3 + 2 + 1 (with passthrough)\n```\nConv2d(1, 1, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nx = torch.cat([ x, input ], dim=1)\nConv2d(2, 2, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(2, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid()\n```\n\n\n\n[GameOfLifeForward_2N.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_2N.py) - 2\\*3x3 + 2 + 1 (without passthrough)\n```\nConv2d(1, 2, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nConv2d(2, 2, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(2, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid() \n```\n\n[GameOfLifeForward_2.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_2.py) - 2\\*3x3 + 2 + 1 (with passthrough)\n```\nConv2d(1, 2, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nx = torch.cat([ x, input ], dim=1)\nConv2d(3, 2, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(2, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid() \n```\n\n[GameOfLifeForward_4.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_4.py) - 4\\*3x3 + 4 + 1 (with passthrough)\n```\nConv2d(1, 4, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nConv2d(5, 4, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(4, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid() \n```\n\n[GameOfLifeForward_128.py](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/GameOfLifeForward_128.py) - 128\\*3x3 + 16 + 8 + 1 - original implementation\n```\nConv2d(1, 128, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\nnn.PReLU()\nConv2d(128, 16, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(16, 8, kernel_size=(1, 1), stride=(1, 1))\nnn.PReLU()\nConv2d(9, 1, kernel_size=(1, 1), stride=(1, 1))\nnn.sigmoid() \n```"},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","collapsed":true,"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":false},"cell_type":"markdown","source":"# Training\n- Source: [logs/GameOfLifeForward.sh](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward.sh)\n- Source: [logs/GameOfLifeForward.stats.sh](https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward.stats.sh)\n\nEach network was trained a total of 10 times, with weights reinitialized each time using `nn.init.kaiming_normal_()`\n\nTraining was continued until it had correctly predicted 100,000 boards in a row to 100% accuracy, which was confirmed externally by unit test.\n\nA 20 minute timeout was introduced after observing that the networks would usually converge within 7 minutes,\nor else get stuck in a local minimum and never converge even after an hour of runtime. \nThe maximum observed runtime (after timeout was introduced) for a convergent result was 13 minutes (about 2x average runtime). \n\nDropout was disabled for GameOfLifeForward_128 as it caused excessive (hour+) training times \nas it tried to build in sufficient redundancy into the network to transition from 99.999% accuracy \nto 100% accuracy.\n\nResults are as follows:\n\n```\nGameOfLifeForward_11N | 9/10 successes  | epochs =  201 / 6284 /  9248 | time seconds =  20 / 563 / 762 (min/avg/max)\nGameOfLifeForward_1N  | 6/10 successes  | epochs = 3376 / 4771 /  7097 | time seconds = 262 / 370 / 552 (min/avg/max)\nGameOfLifeForward_1   | 9/10 successes  | epochs = 2254 / 5313 / 10318 | time seconds = 183 / 420 / 807 (min/avg/max)\nGameOfLifeForward_2N  | 8/10 successes  | epochs = 3245 / 4604 /  6924 | time seconds = 252 / 356 / 533 (min/avg/max)\nGameOfLifeForward_2   | 9/10 successes  | epochs = 3047 / 4878 /  8587 | time seconds = 239 / 379 / 669 (min/avg/max)\nGameOfLifeForward_4   | 10/10 successes | epochs = 2027 / 3308 /  5061 | time seconds = 160 / 263 / 420 (min/avg/max)\nGameOfLifeForward_128 | 10/10 successes | epochs =  441 /  508 /   570 | time seconds =  52 /  80 /  93 (min/avg/max)\n```\n\nAs we can see larger network sizes generally train faster are less subject to lottery ticket initialization.\nPassthrough of the original board state reduces the frequency of \"lottery ticket\" weight initialization fails."},{"metadata":{},"cell_type":"markdown","source":"# Smallest Possible Solution\n\nGame of Life forwards can be solved with only 10 neurons and 13 weights!\n\nWhat is interesting is that PReLU likes a negative weight of about -0.5 or -0.66 which creates a V-shaped activation function because it is looking for the equilibrium point in the middle of: \n```\nAlLeast(cell + neighbours == 3) and AtMost(neighbours == 3)\n```\n\nCompare this to standard ReLU's L shape function, and the Z-shaped Tanh/Sigmoid functions, which can't make the required shape to solve this function with so few weights.\n\nAnother curious observation is that I actually got a 90% success rate on training from random (with one timeout after 60 minutes). All the successful log files report the same basic design pattern with the weights shifted in one direction or the other by 10-20%.\n\nThis is now the other side of the effect described the paper. The network is now so simple at this point that there is only one valid matrix solution to the problem. \n\nIf I look at the GameOfLifeForward_1N logs, with an extra layer of 2 neurons in the middle, there are actually three different solution designs proposed. This only has a 40% training success rate. Lottery ticket initialization must mean starting off significantly closer to one solution rather than the others, else the network may start off in a saddle point and gets stuck deciding which solution to optimize for as it gets pulled in contradictory directions. \n- https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward_1N.1.log \n- https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward_1N.8.log \n- https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward_1N.10.log \n\nThen as you start to add an excessive number of neurons to the network (4*(3x3) + 4 + 1), the training success rate returns to 100%. The cost function has suddenly become far more multi-dimensional, there are many more local-minima, and there are far more moving parts to jiggle around. This I assume it becomes much easier to find an actual slope alone one dimension, or that the stochastic nature of the training data finds it much easier to push the network off any accidental saddle points it might find. The probability of finding a true saddle point in multi-dimensional space is much smaller than when constrained to very few dimensions.\n\nThis is the actual minimum network architecture and weights. It passed a 10,000 board unit test. \n\n```\nepoch: 6900 | board_count: 3450000 | loss: 0.0246548884 | accuracy = 1.0000000000 | time: 0.974ms/board |  11m 23s \nFinished Training: GameOfLifeForward_11N - 6945 epochs in 687.9s\nGameOfLifeForward_11N.savefile(): /home/jamie/code/ai-games/puzzles/game_of_life/neural_networks/models/GameOfLifeForward_11N.pth = 2.2 kB\n--------------------\nGameOfLifeForward_11N\nGameOfLifeForward_11N(\n  (criterion): MSELoss()\n  (layers): ModuleList(\n    (0): Conv2d(1, 1, kernel_size=(3, 3), stride=(1, 1), padding=(1, 1), padding_mode=circular)\n    (1): Conv2d(1, 1, kernel_size=(1, 1), stride=(1, 1))\n  )\n  (dropout): Dropout(p=0.0, inplace=False)\n  (activation): PReLU(num_parameters=1)\n)\nactivation.weight [-0.6601397]\n\nlayers.0.weight\n[[[[-0.8748493  -0.87457496 -0.8745291 ]\n   [-0.8742993  -0.6293647  -0.8741275 ]\n   [-0.8746812  -0.87455815 -0.874589  ]]]]\nlayers.0.bias      [2.6234446]\n\nlayers.1.weight [[[[-3.8328729]]]]\nlayers.1.bias      [1.6233934]\n```\n- https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/neural_networks/hardcoded/logs/GameOfLifeForward_11N.1.log "},{"metadata":{},"cell_type":"markdown","source":"# Implemention Code"},{"metadata":{"trusted":true},"cell_type":"code","source":"! apt-get install -qq tree moreutils parallel time\n! (yes will cite | parallel --citation) 2> /dev/null","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Download code from github"},{"metadata":{"trusted":true},"cell_type":"code","source":"# Download git repository and copy to local directory\n!rm -rf /ai-games/\n!git clone https://github.com/JamesMcGuigan/ai-games/ /ai-games/\n# !cd /ai-games/; git checkout -q d60ea6e40ffa4f27f19837f306482791f0f7f5b3\n!cd /ai-games/; git log -n1 ","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"Copy over relevant files only into notebook working directory.\n\nContents can be seen in the Kaggle generated Output Files section below the notebook"},{"metadata":{"trusted":true},"cell_type":"code","source":"%%bash\n\nrm -rf /kaggle/working/*\ncd /ai-games/puzzles/game_of_life; \nfor FILE in $(\n    /ai-games/kaggle_compile.py neural_networks/train.py neural_networks/tests/test_GameOfLifeHardcoded.py | grep START | awk '{ print $3 }';\n    find neural_networks/ -type f -name '*.sh';\n    find neural_networks/ -type f -name '__init__.py';\n); do\n    mkdir -p /kaggle/working/$(dirname $FILE)\n    touch    /kaggle/working/$(dirname $FILE)/__init__.py\n    cp    -f ${FILE} \"/kaggle/working/${FILE}\"\ndone\n# cp  /ai-games/puzzles/game_of_life/neural_networks/hardcoded/logs/* /kaggle/working/neural_networks/hardcoded/logs/\n\ncd /kaggle/working/\ntree","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Training and Logfile Generation "},{"metadata":{},"cell_type":"markdown","source":"Train each network 10 times from random weight initalization, with a 20 minute timeout.\n\nLogfiles can be found in the Output section of the notebook in the `neural_networks/hardcoded/logs/` directory.\n\nThese contain a printout of the various neural network architectures, the network weights both before and after training, as well continious loss and accuracy metrics.\n\nThe logs when this code was run on my localhost laptop can be found here:\n- https://github.com/JamesMcGuigan/ai-games/tree/master/puzzles/game_of_life/neural_networks/hardcoded/logs\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"!cat neural_networks/hardcoded/logs/GameOfLifeForward.sh","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"!neural_networks/hardcoded/logs/GameOfLifeForward.sh","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Statistics"},{"metadata":{},"cell_type":"markdown","source":"Using awk, we can generate statistics directly from the log files\n\nThe results can be compared those generated on my localhost GPU laptop:\n```\nGameOfLifeForward_11N |  9/10 successes | epochs =  201 / 6284 /  9248 | time seconds =   20 /  563 /  762 (min/avg/max)\nGameOfLifeForward_1N  |  6/10 successes | epochs = 3376 / 4771 /  7097 | time seconds =  262 /  370 /  552 (min/avg/max)\nGameOfLifeForward_1   |  9/10 successes | epochs = 2254 / 5313 / 10318 | time seconds =  183 /  420 /  807 (min/avg/max)\nGameOfLifeForward_2N  |  8/10 successes | epochs = 3245 / 4604 /  6924 | time seconds =  252 /  356 /  533 (min/avg/max)\nGameOfLifeForward_2   |  9/10 successes | epochs = 3047 / 4878 /  8587 | time seconds =  239 /  379 /  669 (min/avg/max)\nGameOfLifeForward_4   | 10/10 successes | epochs = 2027 / 3308 /  5061 | time seconds =  160 /  263 /  420 (min/avg/max)\nGameOfLifeForward_128 | 10/10 successes | epochs =  441 /  508 /   570 | time seconds =   52 /   80 /   93 (min/avg/max)\n```"},{"metadata":{"trusted":true},"cell_type":"code","source":"!cat neural_networks/hardcoded/logs/GameOfLifeForward.stats.sh","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"!neural_networks/hardcoded/logs/GameOfLifeForward.stats.sh","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Further Reading\n\nI have written an interactive playable demo of the forward version of this game in React Javascript:\n- https://life.jamesmcguigan.com/\n\n\nThis notebook is part of series exploring the Neural Network implementations of the Game of Life Forward Problem\n- [Pytorch Game of Life - First Attempt](https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-first-attempt)\n- [Pytorch Game of Life - Hardcoding Network Weights](https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-hardcoding-network-weights)\n- [Its Easy for Neural Networks To Learn Game of Life](https://www.kaggle.com/jamesmcguigan/its-easy-for-neural-networks-to-learn-game-of-life)\n\nThis is preliminary research towards the harder Reverse Game of Life problem, for which I have already designed a novel Ouroboros loss function:\n- [OuroborosLife - Function Reversal GAN](https://www.kaggle.com/jamesmcguigan/ouroboroslife-function-reversal-gan)\n\n\nI also have an extended series of Notebooks exploring different approaches to the Reverse Game of Life problem\n\nMy first attempt was to use the Z3 Constraint Satisfaction SAT solver. This gets 100% accuracy on most boards, but there are a few which it cannot solve. This approach can be slow for boards with large cell counts and large deltas. I managed to figure out how to get cluster compute working inside Kaggle Notebooks, but this solution is estimated to require 10,000+ hours of CPU time to complete.    \n- [Game of Life - Z3 Constraint Satisfaction](https://www.kaggle.com/jamesmcguigan/game-of-life-z3-constraint-satisfaction)\n\nSecond approach was to create a Geometrically Invarient Hash function using Summable Primes, then use forward play and a dictionary lookup table to create a database of known states. For known input/output states at a given delta, the problem is reduced to simply solving the geometric transform between inputs and applying the same function to the outputs. The Hashmap Solver was able to solve about 10% of the test dataset.\n- [Summable Primes](https://www.kaggle.com/jamesmcguigan/summable-primes)\n- [Geometric Invariant Hash Functions](https://www.kaggle.com/jamesmcguigan/geometric-invariant-hash-functions)\n- [Game of Life - Repeating Patterns](https://www.kaggle.com/jamesmcguigan/game-of-life-repeating-patterns)\n- [Game of Life - Hashmap Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-hashmap-solver)\n- [Game of Life - Image Segmentation Solver](https://www.kaggle.com/jamesmcguigan/game-of-life-image-segmentation-solver)"}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}