{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Pytorch Game of Life - Hardcoding Network Weights\n\n\nMy first attempt at getting a neural network to train to 100% accuracy was documented here: \n- https://www.kaggle.com/jamesmcguigan/pytorch-game-of-life-first-attempt\n\nThis model, with 128 CNN layers, is greatly oversized compared to the theoretical minimum, \nbut it reliably trains from random weight initialization acted as proof of concept that a \nneural network can indeed be trained to 100% accuracy.\n\nA minimist network architecture can consists of only 1 or 2 CNN 3x3 channels and only 3 three neurons arranged in 2 layers.\n\nThis notebook is a tutorial on hardcoding neural network weights, and how to implement counting and boolean logic gates using linear algebra.\n\nInspired by the paper **It's Hard for Neural Networks To Learn the Game of Life** by Jacob M. Springer and Garrett T. Kenyon\n- https://arxiv.org/abs/2009.01398"},{"metadata":{},"cell_type":"markdown","source":"# Base Class and Utility Functions\n\nNeural network base class for handling save/autoload, freeze/unfreeze, and casting between data formats"},{"metadata":{"trusted":true},"cell_type":"code","source":"from __future__ import annotations\n\nimport math\nimport os\nimport re\nfrom abc import ABCMeta\nfrom typing import List\nfrom typing import TypeVar\nfrom typing import Union\n\nimport humanize\nimport numpy as np\nimport torch\nimport torch.nn as nn\n\ndevice   = torch.device(\"cuda:0\") if torch.cuda.is_available() else torch.device(\"cpu\")\n__file__ = './notebook.py'  # hardcode for jupyer notebook \n\n# Source: https://stackoverflow.com/questions/8290397/how-to-split-an-iterable-in-constant-size-chunks\ndef batch(iterable, n=1):\n    l = len(iterable)\n    for ndx in range(0, l, n):\n        yield iterable[ndx:min(ndx + n, l)]\n\n\n# noinspection PyTypeChecker\nT = TypeVar('T', bound='GameOfLifeBase')\nclass GameOfLifeBase(nn.Module, metaclass=ABCMeta):\n    \"\"\"\n    Base class for GameOfLife based NNs\n    Handles: save/autoload, freeze/unfreeze, casting between data formats, and training loop functions\n    \"\"\"\n    def __init__(self):\n        super().__init__()\n        self.loaded    = False  # can't call sell.load() in constructor, as weights/layers have not been defined yet\n        self.device    = torch.device(\"cuda:0\") if torch.cuda.is_available() else torch.device(\"cpu\")\n        self.criterion = nn.MSELoss()\n\n\n    def weights_init(self, layer):\n        ### Default initialization seems to work best, at least for Z shaped ReLU1 - see GameOfLifeHardcodedReLU1_21.py\n        if isinstance(layer, (nn.Conv2d, nn.ConvTranspose2d)):\n            ### kaiming_normal_ corrects for mean and std of the relu function\n            ### xavier_normal_ works better for ReLU6 and Z shaped activations\n            if isinstance(self.activation, (nn.ReLU, nn.LeakyReLU, nn.PReLU)):\n                nn.init.kaiming_normal_(layer.weight)\n                # nn.init.xavier_normal_(layer.weight)\n                if layer.bias is not None:\n                    # small positive bias so that all nodes are initialized\n                    nn.init.constant_(layer.bias, 0.1)\n        else:\n            # Use default initialization\n            pass\n\n\n\n    ### Prediction\n\n    def __call__(self, *args, **kwargs) -> torch.Tensor:\n        if not self.loaded: self.load()  # autoload on first function call\n        return super().__call__(*args, **kwargs)\n\n    def predict(self, inputs: Union[List[np.ndarray], np.ndarray, torch.Tensor]) -> np.ndarray:\n        \"\"\"\n        Wrapper function around __call__() that returns a numpy int8 array for external usage\n        Will auto-detect the largest batch size capable of fitting into GPU memory\n        Output is squeezed, so will work both for single board, as well as a batch\n        \"\"\"\n        inputs     = self.cast_inputs(inputs)  # cast to 4D tensor\n        batch_size = len(inputs)               # keep halving batch_size until it is small enough to fit in CUDA memory\n        while True:\n            try:\n                outputs = []\n                for input in batch(inputs, batch_size):\n                    output = self(input)\n                    output = self.cast_int(output).detach().cpu().numpy()\n                    outputs.append(output)\n                outputs = np.concatenate(outputs).squeeze()\n                return outputs\n            except RuntimeError as exception:  # CUDA out of memory exception\n                torch.cuda.empty_cache()\n                if batch_size == 1: raise exception\n                batch_size = math.ceil( batch_size / 2 )\n\n\n\n    ### Training\n\n    def loss(self, outputs, expected, input):\n        return self.criterion(outputs, expected)\n\n    def accuracy(self, outputs, expected, inputs) -> float:\n        # noinspection PyTypeChecker\n        return torch.sum(self.cast_int(outputs) == self.cast_int(expected)).cpu().numpy() / np.prod(outputs.shape)\n\n\n\n    ### Freeze / Unfreeze\n\n    def freeze(self: T) -> T:\n        if not self.loaded: self.load()\n        for name, parameter in self.named_parameters():\n            parameter.requires_grad = False\n        return self\n\n    def unfreeze(self: T) -> T:\n        if not self.loaded: self.load()\n        for name, parameter in self.named_parameters():\n            parameter.requires_grad = True\n        return self\n\n\n\n    ### Load / Save Functionality\n\n    @property\n    def filename(self) -> str:\n        return os.path.join( os.path.dirname(__file__), 'models', f'{self.__class__.__name__}.pth')\n\n\n    # DOCS: https://pytorch.org/tutorials/beginner/saving_loading_models.html\n    def save(self: T) -> T:\n        os.makedirs(os.path.dirname(self.filename), exist_ok=True)\n        torch.save(self.state_dict(), self.filename)\n        print(f'{self.__class__.__name__}.savefile(): {self.filename} = {humanize.naturalsize(os.path.getsize(self.filename))}')\n        return self\n\n\n    def load(self: T, load_weights=True) -> T:\n        ### Disable loading of weights for Notebook Demo\n        # if load_weights and os.path.exists(self.filename):\n        #     try:\n        #         self.load_state_dict(torch.load(self.filename))\n        #         print(f'{self.__class__.__name__}.load(): {self.filename} = {humanize.naturalsize(os.path.getsize(self.filename))}')\n        #     except Exception as exception:\n        #         # Ignore errors caused by model size mismatch\n        #         print(f'{self.__class__.__name__}.load(): model has changed dimensions, reinitializing weights\\n')\n        #         self.apply(self.weights_init)\n        # else:\n        #     if load_weights: print(f'{self.__class__.__name__}.load(): model file not found, reinitializing weights\\n')\n        #     else:            print(f'{self.__class__.__name__}.load(): reinitializing weights\\n')\n        #     self.apply(self.weights_init)\n\n        self.loaded = True    # prevent any infinite if self.loaded loops\n        self.to(self.device)  # ensure all weights, either loaded or untrained are moved to GPU\n        self.eval()           # default to production mode - disable dropout\n        self.freeze()         # default to production mode - disable training\n        return self\n\n    def print_params(self):\n        print(self.__class__.__name__)\n        print(self)\n        for name, parameter in sorted(self.named_parameters(), key=lambda pair: pair[0].split('.')[0] ):\n            print(name)\n            print(re.sub(r'\\n( *\\n)+', '\\n', str(parameter.data.cpu().numpy())))  # remove extranious newlines\n            print()\n\n\n\n    ### Casting\n\n    def cast_bool(self, x: torch.Tensor) -> torch.Tensor:\n        # noinspection PyTypeChecker\n        return (x > 0.5)\n\n    def cast_int(self, x: torch.Tensor) -> torch.Tensor:\n        return self.cast_bool(x).to(torch.int8)\n\n    def cast_int_float(self, x: torch.Tensor) -> torch.Tensor:\n        return self.cast_bool(x).to(torch.float32).requires_grad_(True)\n\n\n    def cast_to_tensor(self, x: Union[np.ndarray, torch.Tensor]) -> torch.Tensor:\n        if torch.is_tensor(x):\n            return x.to(torch.float32).to(device)\n        if isinstance(x, list):\n            x = np.array(x)\n        if isinstance(x, np.ndarray):\n            x = torch.from_numpy(x).to(torch.float32)\n            x = x.to(device)\n            return x  # x.shape = (42,3)\n        raise TypeError(f'{self.__class__.__name__}.cast_to_tensor() invalid type(x) = {type(x)}')\n\n\n    # DOCS: https://towardsdatascience.com/understanding-input-and-output-shapes-in-convolution-network-keras-f143923d56ca\n    # pytorch requires:    contiguous_format = (batch_size, channels, height, width)\n    # tensorflow requires: channels_last     = (batch_size, height, width, channels)\n    def cast_inputs(self, x: Union[List[np.ndarray], np.ndarray, torch.Tensor]) -> torch.Tensor:\n        x = self.cast_to_tensor(x)\n        if x.dim() == 1:             # single row from dataframe\n            x = x.view(1, 1, math.isqrt(x.shape[0]), math.isqrt(x.shape[0]))\n        elif x.dim() == 2:\n            if x.shape[0] == x.shape[1]:  # single 2d board\n                x = x.view((1, 1, x.shape[0], x.shape[1]))\n            else: # rows of flattened boards\n                x = x.view((-1, 1, math.isqrt(x.shape[1]), math.isqrt(x.shape[1])))\n        elif x.dim() == 3:                                        # numpy  == (batch_size, height, width)\n            x = x.view((x.shape[0], 1, x.shape[1], x.shape[2]))   # x.shape = (batch_size, channels, height, width)\n        elif x.dim() == 4:\n            pass  # already in (batch_size, channels, height, width) format, so do nothing\n        return x\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# ReLU1\n\nWhen working with binary data, the logic can be greatly simplified if we implement `ReLU1 = min(max(0.0, x),1.0)`  "},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch.nn as nn\nimport torch.nn.functional as F\n\n\nclass ReLU1(nn.Module):\n    def forward(self, x):\n        return F.relu6(x * 6.0) / 6.0\n\nclass ReLUX(nn.Module):\n    def __init__(self, max_value: float=1.0):\n        super(ReLUX, self).__init__()\n        self.max_value = float(max_value)\n        self.scale     = 6.0 / self.max_value\n\n    def forward(self, x):\n        return F.relu6(x * self.scale) / self.scale","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# GameOfLifeHardcoded Base Class\n\nThis baseclass shows the common network architure that will be extended for the different examples below "},{"metadata":{"trusted":true},"cell_type":"code","source":"from abc import ABCMeta\nfrom typing import TypeVar\n\nimport torch.nn as nn\n\n# from neural_networks.GameOfLifeBase import GameOfLifeBase\n# from neural_networks.modules.ReLUX import ReLU1\n\n\n# noinspection PyTypeChecker\nT = TypeVar('T', bound='GameOfLifeHardcoded')\nclass GameOfLifeHardcoded(GameOfLifeBase, metaclass=ABCMeta):\n    \"\"\"\n    This implements the life_step() function as a minimalist Neural Network function with hardcoded weights\n    Subclasses implement the effect of different activation functions and weights\n    \"\"\"\n    def __init__(self):\n        super().__init__()\n\n        self.input      = nn.Conv2d(in_channels=1, out_channels=1, kernel_size=(1, 1), bias=False)\n        self.counter    = nn.Conv2d(in_channels=1, out_channels=2, kernel_size=(3,3),\n                                    padding=1, padding_mode='circular', bias=False)\n        self.logics     = nn.ModuleList([\n            nn.Conv2d(in_channels=2, out_channels=2, kernel_size=(1,1))\n        ])\n        self.output     = nn.Conv2d(in_channels=2, out_channels=1, kernel_size=(1,1))\n        self.activation = nn.Identity()\n        self.trainable_layers = [ 'input' ]  # we need at least one trainable layer\n        self.criterion  = nn.MSELoss()\n\n\n    def forward(self, x):\n        x = input = self.cast_inputs(x)\n\n        x = self.input(x)     # noop - a single node linear layer - torch needs at least one trainable layer\n        x = self.counter(x)   # counter counts above 6, so no ReLU6\n\n        for logic in self.logics:\n            x = logic(x)\n            x = self.activation(x)\n\n        x = self.output(x)\n        # x = torch.sigmoid(x)\n        x = ReLU1()(x)  # we actually want a ReLU1 activation for binary outputs\n\n        return x\n\n\n\n    # Load / Save Functionality\n\n    def load(self, load_weights=False):\n        return super().load(load_weights=False)\n    \n    def load_state_dict(self, **kwargs):\n        return self\n\n    def save(self):\n        return self\n\n    def unfreeze(self: T) -> T:\n        super().unfreeze()\n        self.freeze()\n        for trainable_layer_name in self.trainable_layers:\n            for name, parameter in self.named_parameters():\n                if name.startswith( trainable_layer_name ):\n                    parameter.requires_grad = True\n        return self","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Manually Hardcoded Weights\n\n\nI decided to create a minimalist neural network with hardcoded weights.\n\nThe boolean rules of the Game of Life requires counting the number of neighbouring cells,\ncomparing it to the value of the center cell, and then performing a less than or greater than operation.\n\nThe rules can be expressed one of two ways:\n```\nAND(\n    z3.AtLeast( past_cell, *past_neighbours, 3 ): n >= 3\n    z3.AtMost(             *past_neighbours, 3 ): n <  4\n)\n```\n```\nSUM(\n    Alive && neighbours >= 2\n    Alive && neighbours <= 3\n    Dead  && neighbours >= 3\n    Dead  && neighbours <= 3\n) >= 2\n```"},{"metadata":{},"cell_type":"markdown","source":"# AtLeast/AtMost Ruleset\n\n```\nAND(\n    z3.AtLeast( past_cell, *past_neighbours, 3 ): n >= 3\n    z3.AtMost(             *past_neighbours, 3 ): n <  4\n)\n```"},{"metadata":{},"cell_type":"markdown","source":"# GameOfLifeHardcodedReLU1_21"},{"metadata":{"trusted":true},"cell_type":"code","source":"from abc import ABCMeta\n\nimport torch\nimport torch.nn as nn\n\n# from neural_networks.hardcoded.GameOfLifeHardcoded import GameOfLifeHardcoded\n# from neural_networks.modules.ReLUX import ReLU1\n\n\nclass GameOfLifeHardcodedReLU1_21(GameOfLifeHardcoded, metaclass=ABCMeta):\n    \"\"\"\n    This uses ReLU1 as binary true/false activation layer to implement the game of life rules using 2 nodes:\n    AND(\n        z3.AtLeast( past_cell, *past_neighbours, 3 ): n >= 3\n        z3.AtMost(             *past_neighbours, 3 ): n <  4\n    )\n\n    This network trained from random weights:\n    - is capable of: learning weights for the output layer after 400-600 epochs (occasionally much less)\n    - has trouble learning the self.logic[0] AND gate weights (without lottery ticket initialization)\n\n    This paper discusses lottery-ticket weight initialization and the issues behind auto-learning hardcoded solutions:\n    - Paper: It's Hard for Neural Networks To Learn the Game of Life - https://arxiv.org/abs/2009.01398\n\n    See GameOfLifeHardcodedReLU1_41 for an alternative implementation using 4 nodes\n    \"\"\"\n    def __init__(self):\n        super().__init__()\n\n        self.trainable_layers  = [ 'input', 'logics', 'output' ]\n        self.input   = nn.Conv2d(in_channels=1, out_channels=1, kernel_size=(1, 1), bias=False)  # no-op trainable layer\n        self.counter = nn.Conv2d(in_channels=1, out_channels=2, kernel_size=(3,3),\n                                  padding=1, padding_mode='circular', bias=False)\n        self.logics  = nn.ModuleList([\n            nn.Conv2d(in_channels=2, out_channels=2, kernel_size=(1,1))\n        ])\n        self.output  = nn.Conv2d(in_channels=2, out_channels=1, kernel_size=(1,1))\n        self.activation = ReLU1()\n\n\n    def load(self, load_weights=False):\n        super().load(load_weights=load_weights)\n\n        self.input.weight.data   = torch.tensor([[[[1.0]]]])\n        self.counter.weight.data = torch.tensor([\n            [[[ 0.0, 0.0, 0.0 ],\n              [ 0.0, 1.0, 0.0 ],\n              [ 0.0, 0.0, 0.0 ]]],\n\n            [[[ 1.0, 1.0, 1.0 ],\n              [ 1.0, 0.0, 1.0 ],\n              [ 1.0, 1.0, 1.0 ]]]\n        ])\n\n        self.logics[0].weight.data = torch.tensor([\n            [[[ 1.0 ]], [[  1.0 ]]],   # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n            [[[ 0.0 ]], [[ -1.0 ]]],   # n <  4   # z3.AtMost(             *past_neighbours, 3 ),\n        ])\n        self.logics[0].bias.data = torch.tensor([\n            -3.0 + 1.0,               # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n            +3.0 + 1.0,               # n <= 3   # z3.AtMost(             *past_neighbours, 3 ),\n        ])\n\n        # Both of the statements need to be true, and ReLU1 enforces we can't go above 1\n        self.output.weight.data = torch.tensor([[\n            [[  1.0 ]],\n            [[  1.0 ]],\n        ]])\n        self.output.bias.data = torch.tensor([ -2.0 + 1.0 ])  # sum() >= 2\n\n        self.to(self.device)\n        return self\n\n\n    ### kaiming corrects for mean and std of the ReLU function (V shaped), but we are using ReLU1 (Z shaped)\n    ### normal distribution seems to perform slightly better than uniform\n    ### default initialization actually seems to perform better than both kaiming and xavier\n    # nn.init.xavier_uniform_(layer.weight)   # 600, 141, 577, 581, 583, epochs for output to train\n    # nn.init.kaiming_uniform_(layer.weight)  # 664, 559, 570, 592, 533\n    # nn.init.kaiming_normal_(layer.weight)   # 450, 562, 456, 164, 557\n    # nn.init.xavier_normal_(layer.weight)    # 497, 492, 583, 461, 475\n    # default (pass) initialization:          # 232, 488,  43, 333,  412\n    def weights_init(self, layer):\n        if isinstance(layer, (nn.Conv2d, nn.ConvTranspose2d)):\n            pass  # use default initialization\n\n\n\nif __name__ == '__main__':\n    import numpy as np\n\n    model = GameOfLifeHardcodedReLU1_21()\n    model.print_params()\n\n    board = np.array([\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n        [0,1,1,1,0],\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n    ])\n    result1 = model.predict(board)\n    result2 = model.predict(result1)\n    assert np.array_equal(board, result2)\n    print('Test passed!')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# GameOfLifeHardcodedTanh"},{"metadata":{"trusted":true},"cell_type":"code","source":"from typing import TypeVar\n\nimport torch\nimport torch.nn as nn\nfrom torch import tensor\n\n# from neural_networks.hardcoded.GameOfLifeHardcoded import GameOfLifeHardcoded\n\n# noinspection PyTypeChecker\nT = TypeVar('T', bound='GameOfLifeHardcodedTanh')\nclass GameOfLifeHardcodedTanh(GameOfLifeHardcoded):\n    \"\"\"\n    This uses Tanh as binary true/false activation layer to implement the game of life rules using 4 nodes:\n    AND(\n        z3.AtLeast( past_cell, *past_neighbours, 3 ): n >= 3\n        z3.AtMost(             *past_neighbours, 3 ): n <  4\n    )\n\n    Tanh() is both applied to input data as well as being the activation function for the output\n    ReLU1  is still being used as the activation function for the logic_games layers\n\n    In theory, the idea was that this would hopefully make this implementation more robust when dealing with\n    non-saturated inputs (ie 0.8 rather than 1.0).\n    A continual smooth gradient may (hopefully) assist OuroborosLife in using this both as a loss function\n    and as a hidden layer inside its own CNN layers. I suspect a ReLU gradient of 0 may be causing problems.\n\n    In practice, the trained tanh solution converged to using two different order of magnitude scales,\n    similar to the manual implementation GameOfLifeHardcodedReLU1_41.py.\n\n    I am unsure if this is make the algorithm more or less stable to non-saturated 0.8 inputs.\n    However the final tanh() will produce mostly saturated outputs.\n\n    Trained solution\n        input.weight      1.0\n        logics.0.weight  [[  2.163727,  2.2645657  ]\n                          [ -0.018100, -0.29718676 ]]\n        logics.0.bias     [ -2.189014,  2.1635942  ]\n        output.weight     [  8.673016,  9.106407   ]\n        output.bias        -15.924878,\n\n\n    See GameOfLifeHardcodedReLU1_21 for an alternative implementation using only 2 nodes\n    \"\"\"\n    def __init__(self):\n        super().__init__()\n\n        self.trainable_layers  = [ 'logics', 'outputs' ]\n        self.counter = nn.Conv2d(in_channels=1, out_channels=2, kernel_size=(3,3),\n                                  padding=1, padding_mode='circular', bias=False)\n        self.logics  = nn.ModuleList([\n            nn.Conv2d(in_channels=2, out_channels=4, kernel_size=(1,1))\n        ])\n        self.output  = nn.Conv2d(in_channels=4, out_channels=1, kernel_size=(1,1))\n\n\n    def forward(self, x):\n        x = input = self.cast_inputs(x)\n\n        x = torch.tanh(x)    # tanh\n        x = self.input(x)    # noop - a single node linear layer - torch needs at least one trainable layer\n        x = self.counter(x)  # counter counts above 6, so no ReLU6\n\n        for logic in self.logics:\n            x = logic(x)\n            x = torch.tanh(x)\n            # x = ReLU1()(x)  # ReLU1 is needed to make the logic gates work\n\n        x = self.output(x)\n        x = torch.tanh(x)\n\n        return x\n\n\n    def load(self: T) -> T:\n        super().load()\n        # self.input.weight.data   = tensor([[[[ 1.0498226 ]]]])\n        self.input.weight.data   = tensor([[[[ 1.0 ]]]])\n        self.counter.weight.data = tensor([\n            [[[ 0.0, 0.0, 0.0 ],\n              [ 0.0, 1.0, 0.0 ],\n              [ 0.0, 0.0, 0.0 ]]],\n\n            [[[ 1.0, 1.0, 1.0 ],\n              [ 1.0, 0.0, 1.0 ],\n              [ 1.0, 1.0, 1.0 ]]]\n        ]) / self.activation(tensor([ 1.0 ]))\n\n        self.logics[0].weight.data = tensor([\n            [[[  2.077 ]], [[  2.197 ]]],   # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n            [[[ -0.020 ]], [[ -0.250  ]]],  # n <  4   # z3.AtMost(             *past_neighbours, 3 ),\n        ])\n        self.logics[0].bias.data = tensor([\n            -2.022,              # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n             1.978,              # n <= 3   # z3.AtMost(             *past_neighbours, 3 ),\n        ])\n\n        # Both of the statements need to be true. Tanh after logics has the domain (-1,1)\n        # Weights here also need to be sufficiently large to saturate sigmoid()\n        self.output.weight.data = tensor([[\n            [[ 9.0 ]],\n            [[ 9.0 ]],\n        ]])\n        self.output.bias.data = tensor([ -16.0 ])  # sum() > 1.5 as tanh()'ed inputs may not be at full saturation\n\n        self.to(self.device)\n        return self\n\n\nif __name__ == '__main__':\n    import numpy as np\n\n    model = GameOfLifeHardcodedTanh()\n    model.print_params()\n\n    board = np.array([\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n        [0,1,1,1,0],\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n    ])\n    result1 = model.predict(board)\n    result2 = model.predict(result1)\n    assert np.array_equal(board, result2)\n    print('Test passed!')\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# Counting Neighbours\n\nThe original value of the board can either be solved via passthrough of the original board state,\nor implemented below as 3x3 convolution layer with only the center weight set to 1.0:\n```\nx = torch.cat([ x, input ], dim=1)   \n```\n\nThe summing of neighbours (and passthrough of the original cell) can be expressed using 3x3 convolutions.\n\nThe input data is binary 1 or 0, so the convolution will output +1 for every Alive cell found \nin the specified position. The result is simply a count of neighbours, which is conceptually similar\nto [AvgPool2d](https://pytorch.org/docs/stable/generated/torch.nn.AvgPool2d.html) \\* 9, but\nwithout downsampling the board size. \n```\nself.counter.weight.data = torch.tensor([\n    [[[ 0.0, 0.0, 0.0 ],\n      [ 0.0, 1.0, 0.0 ],\n      [ 0.0, 0.0, 0.0 ]]],\n\n    [[[ 1.0, 1.0, 1.0 ],\n      [ 1.0, 0.0, 1.0 ],\n      [ 1.0, 1.0, 1.0 ]]]\n])\n```\n\n# GreaterThan (>) and LessThan (<)\n\nGreaterThan (>) and LessThan (<) and  can be expressed with the combination of ReLU1 plus a bias.\n```\nself.logics[0].weight.data = torch.tensor([\n    [[[ 1.0 ]], [[  1.0 ]]],   # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n    [[[ 0.0 ]], [[ -1.0 ]]],   # n <  4   # z3.AtMost(             *past_neighbours, 3 ),\n])\nself.logics[0].bias.data = torch.tensor([\n    -3.0 + 1.0,               # n >= 3   # z3.AtLeast( past_cell, *past_neighbours, 3 ),\n    +3.0 + 1.0,               # n <= 3   # z3.AtMost(             *past_neighbours, 3 ),\n])\nReLU1 = nn.ReLU6()(x * 6.0) / 6.0\n```\n\nIf the cell is alive, and has 5 neighbours, then \n- logics[0][0] = (1.0 * Alive + 1.0 * 5 Neighbours) + (-3.0 + 1.0) bias = +4.0  # positive if n >= 3\n- logics[0][1] = (0.0 * Alive - 1.0 * 5 Neighbours) + (+3.0 + 1.0) bias = -1.0  # positive if n <= 3\n\nIf the cell is dead, and has 3 neighbours, then \n- logics[0][0] = (0.0 * Alive + 1.0 * 3 Neighbours) - (-3.0 + 1.0) bias = +1.0  # positive if n >= 3\n- logics[0][1] = (0.0 * Alive - 1.0 * 3 Neighbours) + (+3.0 + 1.0) bias = +1.0  # positive if n <= 3 \n\nA +-3.0 bias will convert a neighbours count of 3 to 0.0, so we need to add +1.0 in the direction\nof the bias to produce a positive > +1.0 output when the condition is satisfied. \n\n\n# ReLU1\n\nNow that we have encoded the AtLeast/AtMost conditions as positive or negative numbers,\nwe need a logical AND gate to assert that both conditions are true.\n\nA standard ReLU will set any negative values to 0.0, but returns the distance\naway from the bias point in the positive direction.  \nThis V shaped activation does not allow for a simple implementation of a logical AND gate.\n\nFor binary logic, a ReLU1 activation `min(max(0,n),1)` is Z shaped (like Sigmoid and Tanh) \nand outputs in the domain `[0,1]` discarding any information about distances greater than 1.0 \naway from the bias point. When working with binary data, this effectively implements cast to boolean."},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch.nn as nn\nimport torch.nn.functional as F\n\n\nclass ReLU1(nn.Module):\n    def forward(self, x):\n        return F.relu6(x * 6.0) / 6.0\n\nclass ReLUX(nn.Module):\n    def __init__(self, max_value: float=1.0):\n        super(ReLUX, self).__init__()\n        self.max_value = float(max_value)\n        self.scale     = 6.0 / self.max_value\n\n    def forward(self, x):\n        return F.relu6(x * self.scale) / self.scale","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# AND Logic Gate\n\nGiven the presence of ReLU1, the logic for the AND gate is simple.\n- Both of the input statements need to be true. \n- ReLU1 enforces that the inputs will be in the domain `[0,1]`.\n- The maximum sum from the weights is 2.0\n- A bias of -1.0 will return 1.0 if both are True, or `<= 0` for False\n- ReLU1 activation on the output will conver this to either 1.0 or 0.0\n\n```\nself.output.weight.data = torch.tensor([[\n    [[  1.0 ]],\n    [[  1.0 ]],\n]])\nself.output.bias.data = torch.tensor([ -2.0 + 1.0 ])  # sum() >= 2\n```\n\nThe [GameOfLifeHardcodedTanh.py](GameOfLifeHardcodedTanh.py) implementation follows similar logic \nbut with numbers suited to Tanh() which is a continuous function which outputs in the domain `(-1,1)`"},{"metadata":{},"cell_type":"markdown","source":"# AND/OR Ruleset\n\nThe ruleset is classically expressed using boolean logic:\n```\nAlive && ( neighbours >= 2 && neighbours <= 3 ) ||\nDead  && ( neighbours >= 3 && neighbours <= 3 )\n```\n\nOR(AND, AND) requires three layers to properly express, however this logic can be\nequivalently expressed in only two layers using SUM(AND):\n```\nSUM(\n    Alive && neighbours >= 2\n    Alive && neighbours <= 3\n    Dead  && neighbours >= 3\n    Dead  && neighbours <= 3\n) >= 2\n```\n\nThis requires a slightly larger network with 4 channels, one for each condition.  "},{"metadata":{},"cell_type":"markdown","source":"# GameOfLifeHardcodedReLU1_41 "},{"metadata":{"trusted":true},"cell_type":"code","source":"from abc import ABCMeta\n\nimport torch\nimport torch.nn as nn\n\n# from neural_networks.hardcoded.GameOfLifeHardcoded import GameOfLifeHardcoded\n# from neural_networks.modules.ReLUX import ReLU1\n\n\nclass GameOfLifeHardcodedReLU1_41(GameOfLifeHardcoded, metaclass=ABCMeta):\n    \"\"\"\n    This uses ReLU1 as binary true/false activation layer to implement the game of life rules using 4 nodes:\n    SUM(\n        Alive && neighbours >= 2\n        Alive && neighbours <= 3\n        Dead  && neighbours >= 3\n        Dead  && neighbours <= 3\n    ) >= 2\n\n    Alive! is implemented as -10 weight, which is greater than maximum value of the 3x3-1=8 counter convolution\n    sum() >= 2 works because Dead and Alive are mutually exclusive conditions\n\n    See GameOfLifeHardcodedReLU1_21 for an alternative implementation using only 2 nodes\n    \"\"\"\n\n    def __init__(self):\n        super().__init__()\n\n        self.trainable_layers  = [ 'input', 'output' ]\n        self.input   = nn.Conv2d(in_channels=1, out_channels=1, kernel_size=(1, 1), bias=False)  # no-op trainable layer\n        self.counter = nn.Conv2d(in_channels=1, out_channels=2, kernel_size=(3,3),\n                                  padding=1, padding_mode='circular', bias=False)\n        self.logics  = nn.ModuleList([\n            nn.Conv2d(in_channels=2, out_channels=4, kernel_size=(1,1))\n        ])\n        self.output  = nn.Conv2d(in_channels=4, out_channels=1, kernel_size=(1,1))\n        self.activation = ReLU1()\n\n\n\n    def load(self, load_weights=False):\n        super().load(load_weights=load_weights)\n\n        self.input.weight.data   = torch.tensor([[[[1.0]]]])\n        self.counter.weight.data = torch.tensor([\n            [[[ 0.0, 0.0, 0.0 ],\n              [ 0.0, 1.0, 0.0 ],\n              [ 0.0, 0.0, 0.0 ]]],\n\n            [[[ 1.0, 1.0, 1.0 ],\n              [ 1.0, 0.0, 1.0 ],\n              [ 1.0, 1.0, 1.0 ]]]\n        ])\n\n        self.logics[0].weight.data = torch.tensor([\n            [[[  10.0 ]], [[  1.0 ]]],  # Alive && neighbours >= 2\n            [[[  10.0 ]], [[ -1.0 ]]],  # Alive && neighbours <= 3\n            [[[ -10.0 ]], [[  1.0 ]]],  # Dead  && neighbours >= 3\n            [[[ -10.0 ]], [[ -1.0 ]]],  # Dead  && neighbours <= 3\n        ])\n        self.logics[0].bias.data = torch.tensor([\n            -10.0 - 2.0 + 1.0,  # Alive +  neighbours >= 2\n            -10.0 + 3.0 + 1.0,  # Alive + -neighbours <= 3\n              0.0 - 3.0 + 1.0,  # Dead  +  neighbours >= 3\n              0.0 + 3.0 + 1.0,  # Dead  + -neighbours <= 3\n        ])\n\n        # Both of the Alive or Dead statements need to be true\n        #   sum() >= 2 works here because the -10 weight above makes the two clauses mutually exclusive\n        # Otherwise it would require a second layer to formally implement:\n        #   OR( AND(input[0], input[1]), AND(input[3], input[4]) )\n        self.output.weight.data = torch.tensor([[\n            [[  1.0 ]],\n            [[  1.0 ]],\n            [[  1.0 ]],\n            [[  1.0 ]],\n        ]])\n        self.output.bias.data = torch.tensor([ -2.0 + 1.0 ])  # sum() >= 2\n\n        self.to(self.device)\n        return self\n\n\n\nif __name__ == '__main__':\n    import numpy as np\n\n    model = GameOfLifeHardcodedReLU1_41()\n    model.print_params()\n\n    board = np.array([\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n        [0,1,1,1,0],\n        [0,0,0,0,0],\n        [0,0,0,0,0],\n    ])\n    result1 = model.predict(board)\n    result2 = model.predict(result1)\n    assert np.array_equal(board, result2)\n    print('Test passed!')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# AND( bool, > )\n\nThe counter weights remain the same:\n```\nself.counter.weight.data = torch.tensor([\n    [[[ 0.0, 0.0, 0.0 ],\n      [ 0.0, 1.0, 0.0 ],\n      [ 0.0, 0.0, 0.0 ]]],\n\n    [[[ 1.0, 1.0, 1.0 ],\n      [ 1.0, 0.0, 1.0 ],\n      [ 1.0, 1.0, 1.0 ]]]\n])\n```\n\nThe `Alive|Dead &&` logic can be encoded in the same layer as the GreaterThan (>) and LessThan (<) logic,\nby using different orders of magnitudes for the weights.\n\nThe output domain for the 3x3 counter convolution is `[0, 8]`.\n\nIf we set a weight of +-10 for the center cell, then this value is high enough to \ncompletely offset the maximum value is 8 from the neighbours count. \nThis allows us to implement `AND( bool, > )` within a single layer.\n\n```\nself.logics[0].weight.data = torch.tensor([\n    [[[  10.0 ]], [[  1.0 ]]],  # Alive && neighbours >= 2\n    [[[  10.0 ]], [[ -1.0 ]]],  # Alive && neighbours <= 3\n    [[[ -10.0 ]], [[  1.0 ]]],  # Dead  && neighbours >= 3\n    [[[ -10.0 ]], [[ -1.0 ]]],  # Dead  && neighbours <= 3\n])\nself.logics[0].bias.data = torch.tensor([\n    -10.0 - 2.0 + 1.0,  # Alive +  neighbours >= 2\n    -10.0 + 3.0 + 1.0,  # Alive + -neighbours <= 3\n      0.0 - 3.0 + 1.0,  # Dead  +  neighbours >= 3\n      0.0 + 3.0 - 1.0,  # Dead  + -neighbours <= 3\n])\n```\n\nIf the cell is alive, and has 5 neighbours, then \n- logics[0][0] = ( 10.0 * Alive + 1.0 * 5 Neighbours) + (-10.0 - 2.0 + 1.0) bias = +15.0 - 11.0 == +4.0\n- logics[0][1] = ( 10.0 * Alive - 1.0 * 5 Neighbours) + (-10.0 + 3.0 + 1.0) bias =  +5.0 -  6.0 == -1.0\n- logics[0][2] = (-10.0 * Alive + 1.0 * 5 Neighbours) + (  0.0 - 3.0 + 1.0) bias =  -5.0 -  2.0 == -7.0\n- logics[0][3] = (-10.0 * Alive - 1.0 * 5 Neighbours) + (  0.0 + 3.0 + 1.0) bias =  -5.0 +  4.0 == -1.0\n\n\nIf the cell is dead, and has 3 neighbours, then \n- logics[0][0] = ( 10.0 * Dead + 1.0 * 3 Neighbours) + (-10.0 - 2.0 + 1.0) bias =  +3.0 - 11.0 ==  -6.0\n- logics[0][1] = ( 10.0 * Dead - 1.0 * 3 Neighbours) + (-10.0 + 3.0 + 1.0) bias =  -3.0 -  6.0 == -11.0\n- logics[0][2] = (-10.0 * Dead + 1.0 * 3 Neighbours) + (  0.0 - 3.0 + 1.0) bias =  +3.0 -  2.0 ==  +3.0\n- logics[0][3] = (-10.0 * Dead - 1.0 * 3 Neighbours) + (  0.0 + 3.0 - 1.0) bias =  -3.0 +  4.0 ==  +1.0\n\nThe top two expressions can only be True/Positive if we have a +10 contribution from the Alive cell.\nThe bottom two expressions will automatically be False/Negative when Alive == -10\n\nReLU1 then converts to: Positive = 1.0 and Negative = 1.0\n\n\n## SUM( AND )\n\nBoth of the Alive or Dead statements (2 clauses each) needs to be True.\n\nThis can be implemented as  `sum() >= 2`, given the following preconditions:\n- The -10 weight above makes the groups of clauses mutually exclusive\n- Each clause group has the same size \n    - for imbalanced group sizes, clauses could be duplicated to make the group sizes the same\n\nWithout these preconditions, a second layer would be required to formally implement:\n- OR( AND(input[0], input[1]), AND(input[3], input[4]) )\n\n```\nself.output.weight.data = torch.tensor([[\n    [[  1.0 ]],\n    [[  1.0 ]],\n\n    [[  1.0 ]],\n    [[  1.0 ]],\n]])\nself.output.bias.data = torch.tensor([ -2.0 + 1.0 ])  # sum() >= 2\n```\n"},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","collapsed":true,"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":false},"cell_type":"markdown","source":"# Unit Tests\n\nTo validate that these solutions are indeed correct and reliable, \nthe following unit test successfully asserts 100% correct results \nover a sequence of 10,000 randomly generated boards. "},{"metadata":{"trusted":true},"cell_type":"code","source":"# Functions for implementing Game of Life Forward Play\nfrom typing import List\n\nimport numpy as np\nimport scipy.sparse\nfrom joblib import delayed\nfrom joblib import Parallel\nfrom numba import njit\n\n\n# Source: https://www.kaggle.com/ianmoone0617/reversing-conways-game-of-life-tutorial\ndef life_step_numpy(X: np.ndarray):\n    \"\"\"Game of life step using generator expressions\"\"\"\n    nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)\n                     for i in (-1, 0, 1) for j in (-1, 0, 1)\n                     if (i != 0 or j != 0))\n    return (nbrs_count == 3) | (X & (nbrs_count == 2))\n\n\n# Source: https://www.kaggle.com/ianmoone0617/reversing-conways-game-of-life-tutorial\ndef life_step_scipy(X: np.ndarray):\n    \"\"\"Game of life step using scipy tools\"\"\"\n    from scipy.signal import convolve2d\n    nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X\n    return (nbrs_count == 3) | (X & (nbrs_count == 2))\n\n\n\n# NOTE: @njit doesn't like np.roll(axis=) so reimplement explictly\n@njit\ndef life_neighbours_xy(board: np.ndarray, x, y, max_value=3):\n    size_x = board.shape[0]\n    size_y = board.shape[1]\n    neighbours = 0\n    for i in (-1, 0, 1):\n        for j in (-1, 0, 1):\n            if i == j == 0: continue    # ignore self\n            xi = (x + i) % size_x\n            yj = (y + j) % size_y\n            neighbours += board[xi, yj]\n            if neighbours > max_value:  # shortcircuit return 4 if overpopulated\n                return neighbours\n    return neighbours\n\n\n@njit\ndef life_neighbours(board: np.ndarray, max_value=3):\n    size_x = board.shape[0]\n    size_y = board.shape[1]\n    output = np.zeros(board.shape, dtype=np.int8)\n    for x in range(size_x):\n        for y in range(size_y):\n            output[x,y] = life_neighbours_xy(board, x, y, max_value)\n    return output\n\n\n@njit\ndef life_step_njit(board: np.ndarray) -> np.ndarray:\n    \"\"\"Game of life step using generator expressions\"\"\"\n    size_x = board.shape[0]\n    size_y = board.shape[1]\n    output = np.zeros(board.shape, dtype=np.int8)\n    for x in range(size_x):\n        for y in range(size_y):\n            cell       = board[x,y]\n            neighbours = life_neighbours_xy(board, x, y, max_value=3)\n            if ( (cell == 0 and      neighbours == 3 )\n              or (cell == 1 and 2 <= neighbours <= 3 )\n            ):\n                output[x, y] = 1\n    return output\n\nlife_step = life_step_njit  # create global alias\ndef life_steps(boards: List[np.ndarray]) -> List[np.ndarray]:\n    \"\"\" Parallel version of life_step() but for an array of boards \"\"\"\n    return Parallel(-1)( delayed(life_step)(board) for board in boards )\n\n\n@njit\ndef life_step_delta(board: np.ndarray, delta):\n    for t in range(delta): board = life_step(board)\n    return board\n\n\ndef life_step_3d(board: np.ndarray, delta):\n    solution_3d = np.array([ board ], dtype=np.int8)\n    for t in range(delta):\n        board       = life_step(board)\n        solution_3d = np.append( solution_3d, [ board ], axis=0)\n    return solution_3d\n\n\n# RULES: https://www.kaggle.com/c/conway-s-reverse-game-of-life/data\ndef generate_random_board(shape=(25,25)):\n    # An initial board was chosen by filling the board with a random density between 1% full (mostly zeros) and 99% full (mostly ones).\n    # DOCS: https://cmdlinetips.com/2019/02/how-to-create-random-sparse-matrix-of-specific-density/\n    density = np.random.random() * 0.98 + 0.01\n    board   = scipy.sparse.random(*shape, density=density, data_rvs=np.ones).toarray().astype(np.int8)\n\n    # The starting board's state was recorded after the 5 \"warmup steps\". These are the values in the start variables.\n    for t in range(5):\n        board = life_step(board)\n        if np.count_nonzero(board) == 0:\n            return generate_random_board(shape)  # exclude empty boards and try again\n    return board\n\ndef generate_random_boards(count, shape=(25,25)):\n    generated_boards = Parallel(-1)( delayed(generate_random_board)(shape) for _ in range(count) )\n    return generated_boards\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"import pytest \n\nmodels = [\n    GameOfLifeHardcodedReLU1_41(),\n    GameOfLifeHardcodedReLU1_21(),\n    GameOfLifeHardcodedTanh(),\n]\n\n# @pytest.mark.parametrize(\"model\", models)\ndef test_GameOfLifeHardcoded_generated_boards(model):\n    inputs   = generate_random_boards(100_000)\n    expected = life_steps(inputs)\n    outputs  = model.predict(inputs)\n    assert np.array_equal( outputs, expected )  # assert 100% accuracy\n\nfor model in models:\n    test_GameOfLifeHardcoded_generated_boards\n    print(f'{model.__class__.__name__:27s} - 100,000 tests passed')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Profiler\n\nIn CPU mode, a neural network in batch mode is as fast as calling a C-compiled function repeatedly in a loop, and doesn't suffer from @njit first-run compiletime. \n\nWith CUDA GPU enabled, a neural network can be an order of magnitude faster than CPU executed C code.\n\nHowever if using a neural network to predict boards individually, there is signifcant overhead in terms of python function calls and datatype casting, making it 2-3x slower than a C function call."},{"metadata":{"trusted":true},"cell_type":"code","source":"def profile_GameOfLifeHardcoded():\n    import timeit\n    import operator\n    # from utils.game import generate_random_boards, life_step, life_step_1, life_step_2\n\n    gameOfLifeHardcodedReLU1_41 = GameOfLifeHardcodedReLU1_41().load().to(device)\n    gameOfLifeHardcodedReLU1_21 = GameOfLifeHardcodedReLU1_21().load().to(device)\n    gameOfLifeHardcodedTanh     = GameOfLifeHardcodedTanh().load().to(device)\n    \n    for batch_size in [1, 1_000]:\n        boards  = generate_random_boards(batch_size)\n        number  = 10\n        timings = {\n            'GameOfLifeHardcodedReLU1_41() - batch': timeit.timeit(lambda:   gameOfLifeHardcodedReLU1_41.predict(boards),                      number=number),\n            'GameOfLifeHardcodedReLU1_21() - batch': timeit.timeit(lambda:   gameOfLifeHardcodedReLU1_41.predict(boards),                      number=number),\n            'GameOfLifeHardcodedTanh()     - batch': timeit.timeit(lambda:   gameOfLifeHardcodedTanh.predict(boards),                          number=number),\n            'GameOfLifeHardcodedReLU1_41() - loop':  timeit.timeit(lambda: [ gameOfLifeHardcodedReLU1_21.predict(board) for board in boards ], number=number),\n            'GameOfLifeHardcodedReLU1_21() - loop':  timeit.timeit(lambda: [ gameOfLifeHardcodedReLU1_21.predict(board) for board in boards ], number=number),\n            'GameOfLifeHardcodedTanh()     - loop':  timeit.timeit(lambda: [ gameOfLifeHardcodedTanh.predict(board)     for board in boards ], number=number),\n            'life_step() - njit':                    timeit.timeit(lambda: [ life_step_njit(board)                      for board in boards ], number=number),\n            'life_step() - numpy':                   timeit.timeit(lambda: [ life_step_numpy(board)                     for board in boards ], number=number),\n            'life_step() - scipy':                   timeit.timeit(lambda: [ life_step_scipy(board)                     for board in boards ], number=number),\n        }\n        print(f'{device} | batch_size = {len(boards)}')\n        for key, value in sorted(timings.items(), key=operator.itemgetter(1)):\n            print(f'- {key:37s} = {value/number/len(boards) * 1_000:6.3f}ms')\n        print()\n        \n        \ndevice = torch.device(\"cpu\")\nprofile_GameOfLifeHardcoded()\n\nif torch.cuda.is_available():\n    device = torch.device(\"cuda:0\")\n    profile_GameOfLifeHardcoded()","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}