{"cells":[{"metadata":{},"cell_type":"markdown","source":"\n# Game of Life\n\n\n### This notebook \n* trying to solve True Target Problem \n* show some use cases for probabilistic extension of Game of Life\n* provides some useful function\n\n### Paragraphs\n* Task overview/Game Rules\n* True Target Problem\n* Probability Extension\n* Correct Loss Function\n* DataStream (useful function)\n* CNN_Model\n* Direct gradient optimization\n* Result evaluation (useful function)"},{"metadata":{},"cell_type":"markdown","source":"\n# Task overview/Game Rules\n\n*The game consists of a board of cells that are either on or off. One creates an initial configuration of these on/off states and observes how it evolves. There are four simple rules to determine the next state of the game board, given the current state:*\n\n* Overpopulation: if a living cell is surrounded by more than three living cells, it dies.\n* Stasis: if a living cell is surrounded by two or three living cells, it survives.\n* Underpopulation: if a living cell is surrounded by fewer than two living cells, it dies.\n* Reproduction: if a dead cell is surrounded by exactly three cells, it becomes a live cell.\n\n"},{"metadata":{},"cell_type":"markdown","source":"\n# True Target Problem\n\n\n\n\nOur goal is to predict the start_state that will come to target_stop_state in the delta iteration.\nBut the problem is that many start_state can lead us to target_stop_state.\n\nEven if we know one of start_state(lets call it start_state_0) that lead to stop_state\n\nWe cannot use start_state_0 as a target because there are many other start_states that lead to stop_state, and how is our model supposed to understand that we need to accurately predict start_state_0?\n\nHence, the real goal is stop_state.\n\nWe need to somehow build a model that will count the error as the difference between stop_state_prediction (predicting start_state through delta iterations) and stop_state_true.\n\nIn the case of neural networks, the problem is binary rules (the loss cannot flow through the forward iteration)"},{"metadata":{},"cell_type":"markdown","source":"\n# Probability Extension\n\nSo let's create a differentiable forward iteration\n\nNow the cells will not store a binary value (live / dead), but the probability that the cell is alive\n\nThe question is how to calculate the probability that the cell will be alive in the next iteration?\n\n\n\nAccording to the rules, the cell will be alive at the next iteration if \n* case1 - cell has 3 living neighbors\n* case2 - cell alive and has 2 living neighbors\n\nThis means that the probability that the cell is alive at the next iteration = probability of case1 + the probability of case2\n\nP(cell is alive at the next iteration) = P(cell has 3 living neighbors) + P(cell has 2 living neighbors)*P(cell alive)\n\n(a simple diagram of how to calculate the probability that a cell has one live neighbor can be found in the picture)"},{"metadata":{},"cell_type":"markdown","source":"\n# Correct Loss Function\n\n\n\nLet's implement probabilistic forward iteration\n\n### binary case"},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch\n\nneighbors_roll_axes = [(i,j) for i in range(-1,2) for j in range(-1, 2) if not (i==0 and j==0)]\n\n\ndef binary_forward_iteration(grid, delta=1):\n for _ in range(delta):\n neighbor_sum = torch.cat([torch.roll(torch.roll(grid, i, 2), j, 3) for i,j in neighbors_roll_axes], dim=1)\n neighbor_sum = neighbor_sum.sum(dim=1, keepdim=True)\n grid = ((neighbor_sum == 3) | ((grid==1) & (neighbor_sum == 2)))\n return grid","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### probabilistic case"},{"metadata":{"trusted":true},"cell_type":"code","source":"neighbors_roll_axes = [(i,j) for i in range(-1,2) for j in range(-1, 2) if not (i==0 and j==0)]\n\ncombination_alive2 = [(i,j) for i in range(8) for j in range(i)]\ncombination_alive2_dead6 = [([i,j]+[8+k for k in range(8) if (k!=i and k!=j)]) for i,j in combination_alive2]\n\ncombination_alive3 = [(i,j,k) for i in range(8) for j in range(i) for k in range(j)]\ncombination_alive3_dead5 = [([i,j,k]+[8+l for l in range(8) if (l!=i and l!=j and l!=k)]) for i,j,k in combination_alive3]\n\n\ndef get_neighbors(grid):\n return torch.stack([torch.roll(torch.roll(grid, i, 2), j, 3) for i,j in neighbors_roll_axes])\n\ndef n_neigbors_nearby_prob(neighbors, neighbor_nearby=2):\n if neighbor_nearby==2:\n combination = combination_alive2_dead6\n else:\n combination = combination_alive3_dead5\n neighbors = torch.cat([neighbors, 1 - neighbors])\n return torch.stack([neighbors[c].prod(dim=0) for c in combination]).sum(dim=0)\n\n\ndef probabilistic_forward_iteration_autograd(grid):\n neighbors = get_neighbors(grid)\n\n neighbors_p2 = n_neigbors_nearby_prob(neighbors, 2)\n neighbors_p3 = n_neigbors_nearby_prob(neighbors, 3)\n\n alive_prob = neighbors_p3 + neighbors_p2*grid\n return alive_prob","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### custom grad backward\n\nslower but use less memory"},{"metadata":{"trusted":true},"cell_type":"code","source":"neighbor_alive2_cell_alive = {}\nneighbor_alive2_cell_dead = {}\n\nneighbor_alive3_cell_alive = {}\nneighbor_alive3_cell_dead = {}\n\nfor cell in range(8):\n neighbor_alive2_cell_alive[cell] = [(cell,j) for j in range(8) if j!=cell]\n neighbor_alive2_cell_alive[cell] = [([j]+[8+k for k in range(8) if (k!=i and k!=j)]) for i,j in neighbor_alive2_cell_alive[cell]]\n \n neighbor_alive2_cell_dead[cell] = [(i,j) for i in range(8) for j in range(i) if i!=cell and j!=cell]\n neighbor_alive2_cell_dead[cell] = [([i,j]+[8+k for k in range(8) if (k!=i and k!=j and k!=cell)]) for i,j in neighbor_alive2_cell_dead[cell]]\n \n neighbor_alive3_cell_alive[cell] = [(i,j,cell) for i in range(8) for j in range(i) if i!=cell and j!=cell]\n neighbor_alive3_cell_alive[cell] = [([i,j]+[8+l for l in range(8) if (l!=i and l!=j and l!=k)]) for i,j,k in neighbor_alive3_cell_alive[cell]]\n\n neighbor_alive3_cell_dead[cell] = [(i,j,k) for i in range(8) for j in range(i) for k in range(j) if i!=cell and j!=cell and k!=cell]\n neighbor_alive3_cell_dead[cell] = [([i,j,k]+[8+l for l in range(8) if (l!=i and l!=j and l!=k and l!=cell)]) for i,j,k in neighbor_alive3_cell_dead[cell]]\n\n\ndef get_neighbors_backward(grad_output):\n return torch.stack([torch.roll(torch.roll(grad_output[idx], -i, 2), -j, 3) for idx, (i,j) in enumerate(neighbors_roll_axes)]).sum(dim=0)\n\n\ndef n_neigbors_nearby_prob_backward(grad_output, neighbors, neighbor_nearby=2):\n if neighbor_nearby==2:\n combination_cell_alive = neighbor_alive2_cell_alive\n combination_cell_dead = neighbor_alive2_cell_dead\n else:\n combination_cell_alive = neighbor_alive3_cell_alive\n combination_cell_dead = neighbor_alive3_cell_dead\n \n neighbors = torch.cat([neighbors, 1 - neighbors])\n coef = []\n for cell in range(8):\n cell_live_coef = torch.stack([neighbors[l].prod(dim=0) for l in combination_cell_alive[cell]]).sum(dim=0)\n cell_dead_coef = torch.stack([neighbors[d].prod(dim=0) for d in combination_cell_dead[cell]]).sum(dim=0)\n coef.append(cell_live_coef-cell_dead_coef)\n coef = torch.stack(coef)\n return coef*grad_output\n\n\nclass ProbabilisticForwardIteration(torch.autograd.Function):\n @staticmethod\n def forward(ctx, grid, delta=1):\n ctx.grid = grid\n return probabilistic_forward_iteration_autograd(grid)\n \n\n @staticmethod\n def backward(ctx, grad_out):\n grid = ctx.grid\n neighbors = get_neighbors(grid)\n neighbors_p2 = n_neigbors_nearby_prob(neighbors, neighbor_nearby=2) \n \n grad_n2_out = grad_out*grid\n grad_n3_out = grad_out\n \n grad_n2_inp = n_neigbors_nearby_prob_backward(grad_n2_out, neighbors, neighbor_nearby=2)\n grad_n3_inp = n_neigbors_nearby_prob_backward(grad_n3_out, neighbors, neighbor_nearby=3)\n \n grad_neighbors_out = grad_n2_inp + grad_n3_inp\n \n grad_neighbors_inp = get_neighbors_backward(grad_neighbors_out)\n \n grad_inp = grad_neighbors_inp + neighbors_p2*grad_out\n return grad_inp, None","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### probabilistic_forward_iteration"},{"metadata":{"trusted":true},"cell_type":"code","source":"def probabilistic_forward_iteration(grid, delta=1, autograd=True):\n \"\"\"autograd=False slower but use less memory\"\"\"\n if autograd:\n for _ in range(delta):\n grid = probabilistic_forward_iteration_autograd(grid)\n else:\n for _ in range(delta):\n grid = ProbabilisticForwardIteration.apply(grid)\n return grid","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# DataStream"},{"metadata":{"trusted":true},"cell_type":"code","source":"import numpy as np\n\nneighbors_roll_axes = [(i,j) for i in range(-1,2) for j in range(-1, 2) if not (i==0 and j==0)]\n\n\ndef generate_random_start_batch(batch_size):\n return np.random.randint(low=0, high=2, size=(batch_size, 1, 25, 25), dtype=bool)\n\ndef straight_iter_binary_numpy(grid, delta=1):\n for _ in range(delta):\n neighbor_sum = np.concatenate([np.roll(np.roll(grid, i, 2), j, 3) for i,j in neighbors_roll_axes], axis=1)\n neighbor_sum = neighbor_sum.sum(axis=1, keepdims=True)\n grid = ((neighbor_sum == 3) | ((grid==1) & (neighbor_sum == 2)))\n return grid\n\n\nclass DataStream():\n def __init__(self, delta=None, batch_size=128, drop_empty=False, drop_ch_dim=False):\n self.init_delta = delta\n self.batch_size = batch_size\n self.drop_empty= drop_empty\n self.drop_ch_dim = drop_ch_dim\n \n def __iter__(self):\n while True:\n x = generate_random_start_batch(self.batch_size)\n delta = self.init_delta if self.init_delta else np.random.randint(1,6)\n x = straight_iter_binary_numpy(x, 5+delta)\n \n if self.drop_empty:\n x = x[x.any(axis=2).any(axis=2).reshape(-1)]\n \n if self.drop_ch_dim:\n x = x[:,0,:,:]\n \n yield x.astype(float), delta","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"from torch import FloatTensor\nfrom torch.utils.data import IterableDataset, DataLoader\n\nclass DataStreamTorch(IterableDataset):\n def __init__(self, delta=None, batch_size=128, drop_empty=False, drop_ch_dim=False):\n self.ds = DataStream(delta, batch_size, drop_empty, drop_ch_dim)\n \n def __iter__(self):\n for x, delta in self.ds:\n yield FloatTensor(x), delta\n \n\ndef pass_collate(batch):\n return batch[0]\n\n\ndef get_datastream_loader(delta=None, batch_size=128, drop_empty=False, drop_ch_dim=False, num_workers=1):\n dataset = DataStreamTorch(delta, batch_size, drop_empty, drop_ch_dim)\n dataloader = DataLoader(dataset, batch_size=1, collate_fn=pass_collate, num_workers=num_workers)\n return dataloader","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# CNN Model\nclassic model\n\ndelta == 1"},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch.nn as nn\n\n\nclass Model(nn.Module):\n def __init__(self):\n super().__init__()\n self.relu = nn.ReLU()\n self.conv1 = nn.Conv2d(1, 512, 7, padding=3, padding_mode='circular')\n self.conv2 = nn.Conv2d(512, 256, 5, padding=2, padding_mode='circular')\n self.conv3 = nn.Conv2d(256, 256, 3, padding=1, padding_mode='circular')\n self.conv4 = nn.Conv2d(256, 1, 1)\n self.sigmoid = nn.Sigmoid()\n\n \n def forward(self, x):\n x = self.relu(self.conv1(x))\n x = self.relu(self.conv2(x))\n x = self.relu(self.conv3(x))\n x = self.sigmoid(self.conv4(x))\n return x","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch\nimport torch.nn as nn\n\n\nclass FixPredictBlock(nn.Module):\n def __init__(self):\n super().__init__()\n self.relu = nn.ReLU()\n self.conv1 = nn.Conv2d(5, 256, 5, padding=2, padding_mode='circular')\n self.conv2 = nn.Conv2d(256, 256, 3, padding=1, padding_mode='circular')\n self.conv3 = nn.Conv2d(256, 256, 1)\n self.conv4 = nn.Conv2d(256, 1, 3, padding=1, padding_mode='circular')\n self.sigmoid = nn.Sigmoid()\n\n \n def forward(self, x, x_prev_pred):\n with torch.no_grad():\n x_prev_pred_bin = x_prev_pred>0.5\n x_pred_bin = binary_forward_iteration(x_prev_pred_bin)\n x_pred = probabilistic_forward_iteration(x_prev_pred)\n x = torch.cat([x, x_prev_pred, x_prev_pred_bin.float(), x_pred, x_pred_bin.float()], dim=1)\n x = self.relu(self.conv1(x))\n x = self.relu(self.conv2(x))\n x = self.relu(self.conv3(x))\n x = self.sigmoid(self.conv4(x))\n return x\n\n\nclass Model(nn.Module):\n def __init__(self):\n super().__init__()\n self.fix_pred = FixPredictBlock()\n \n def forward(self, x, n_it=5):\n x_prev_pred = x\n for i in range(n_it):\n x_prev_pred = self.fix_pred(x, x_prev_pred)\n return x_prev_pred","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"from torch.nn import BCELoss\nfrom torch.optim import Adam\nfrom tqdm.notebook import trange, tqdm\n\nN_iter = 200\ndevice = 'cuda'\nloader = get_datastream_loader(batch_size=128, num_workers=8, drop_empty=True, delta=1)\nmodel = Model().to(device)\ncriterion = BCELoss()\noptimizer = Adam(model.parameters(), lr=1e-3)\n\ntqdm_loader = tqdm(loader)\nfor i, (stop_state, _) in enumerate(tqdm_loader):\n stop_state = stop_state.to(device)\n \n optimizer.zero_grad()\n start_state_prediction = model(stop_state)\n stop_state_prediction = probabilistic_forward_iteration(start_state_prediction)\n loss = criterion(stop_state_prediction, stop_state)\n loss.backward()\n optimizer.step()\n \n with torch.no_grad():\n bce = loss.item()\n start_state_alive = (start_state_prediction>0.5).float().mean().item()\n accuracy = ((stop_state_prediction > 0.5) == (stop_state>0.5)).float().mean().item()\n accuracy_true = (binary_forward_iteration(start_state_prediction>0.5)==(stop_state>0.5)).float().mean().item()\n \n tqdm_loader.postfix = 'bce: {:0.10f} | start_state_alive: {:0.5f} | accuracy: {:0.10f} | accuracy_true: {:0.10f}'\\\n .format(bce, start_state_alive, accuracy, accuracy_true)\n \n if i > N_iter:\n tqdm_loader.close()\n break\n\nfor param in model.parameters():\n param.requires_grad = False\n \nmodel.eval()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for batch in loader:\n stop_state = batch[0].cuda()\n break\n \nfor n_iter in [1,10,100]:\n acc = (stop_state == binary_forward_iteration(model(stop_state, n_iter) > 0.5)).float().mean().item()\n print(f'model n_iter={n_iter} accuracy: {acc}')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# Direct gradient optimization\n\nuse only loss(dont use stop_stape to predict start_state)"},{"metadata":{"trusted":true},"cell_type":"code","source":"import torch\nfrom torch import FloatTensor\nfrom torch.nn import BCELoss\nfrom torch.optim import Adam\nfrom tqdm.notebook import trange, tqdm\n\n\ndef direct_gradient_optimization(batch, n_iter, lr, device='cuda', reduse_alife=False):\n stop_state = batch\n start_state = nn.Parameter(torch.rand(stop_state.shape).to(device)-1)\n criterion = BCELoss()\n optimizer = Adam([start_state], lr=lr,)\n tqdm_loader = trange(n_iter)\n for _ in tqdm_loader:\n optimizer.zero_grad()\n start_state_prob = torch.sigmoid(start_state)\n stop_state_prediction = probabilistic_forward_iteration(start_state_prob, autograd=False)\n \n bce_loss = criterion(stop_state_prediction, stop_state)\n start_state_alive = start_state_prob.mean()\n if reduse_alife and start_state_alive.item() > 0:\n loss = bce_loss + start_state_alive\n else:\n loss = bce_loss\n \n loss.backward()\n optimizer.step()\n\n with torch.no_grad():\n bce = bce_loss.item()\n alive_cells = start_state_alive.item()\n accuracy = ((stop_state_prediction > 0.5) == (stop_state>0.5)).float().mean().item()\n accuracy_true = (binary_forward_iteration(start_state_prob>0.5)==(stop_state>0.5)).float().mean().item()\n\n tqdm_loader.postfix = 'bce: {:0.10f} | start_state_alive: {:0.5f} | accuracy: {:0.10f} | accuracy_true: {:0.10f}'.format(bce, alive_cells, accuracy, accuracy_true)\n \n return torch.sigmoid(start_state.detach())#.cpu().reshape(-1,625)\n\n\ndef direct_gradient_optimization_predict(data, delta, n_iter=100, lr=1, device='cuda'):\n data = FloatTensor(np.array(data)).reshape((-1, 1, 25, 25)).to(device)\n for i in range(delta-1):\n data = direct_gradient_optimization(data, n_iter, lr, reduse_alife=True)\n data = (data>0.5).float()\n \n data = direct_gradient_optimization(data, n_iter, 1, reduse_alife=False)\n return (data>0.5).detach().cpu().int().reshape(-1,625).numpy()","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Prediction using direct gradient optimization"},{"metadata":{"trusted":true},"cell_type":"code","source":"import pandas as pd\n\ntest = pd.read_csv('../input/conways-reverse-game-of-life-2020/test.csv', index_col='id')\nsubmission = pd.read_csv('../input/conways-reverse-game-of-life-2020/sample_submission.csv', index_col='id')","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"for delta in range(1,6):\n mask = test['delta']==delta\n data = test[mask].iloc[:,1:]\n submission[mask] = direct_gradient_optimization_predict(data, delta, 100, 1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"submission.to_csv('submission.csv')\nsubmission","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"\n# Result evaluation\n* calk accurate lb score\n* shows statistics for each delta"},{"metadata":{"trusted":true},"cell_type":"code","source":"from matplotlib import pyplot as plt\n\ndef evaluate_results(test, submission):\n test = test.copy()\n test['socre'] = 0\n for delta in range(1,6):\n mask = test['delta']==delta\n data = FloatTensor(submission[mask].to_numpy()).reshape(-1,1,25,25)\n for _ in range(delta):\n data = binary_forward_iteration(data)\n data = data.reshape(-1,625).numpy()\n result = test.loc[mask].iloc[:,1:-1] == data\n test.loc[mask, 'socre'] = result.mean(axis=1)\n \n print(f\"Delta {delta} score: {test.loc[mask, 'socre'].mean()}\")\n test.loc[mask, 'socre'].hist(bins=30)\n \n plt.show()\n \n print(f\"LB : {1-test['socre'].mean()}\")","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"evaluate_results(test, submission)","execution_count":null,"outputs":[]}],"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}