{"cells":[{"metadata":{"_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","papermill":{"duration":0.016889,"end_time":"2020-11-14T02:46:38.228686","exception":false,"start_time":"2020-11-14T02:46:38.211797","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Game of Life - Random Forest\n\nHere we train a Random Forest Classifier to predict the Reverse Game of Life\n\nTODO: use LightGBM with custom loss function\n- https://lightgbm.readthedocs.io/en/latest/\n- https://towardsdatascience.com/custom-loss-functions-for-gradient-boosting-f79c1b40466d"},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:38.277806Z","iopub.status.busy":"2020-11-14T02:46:38.274556Z","iopub.status.idle":"2020-11-14T02:46:38.289136Z","shell.execute_reply":"2020-11-14T02:46:38.288432Z"},"papermill":{"duration":0.045916,"end_time":"2020-11-14T02:46:38.289277","exception":false,"start_time":"2020-11-14T02:46:38.243361","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"# Source: https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/utils/util.py\nfrom typing import Dict\n\nimport numpy as np\nimport pandas as pd\nfrom fastcache import clru_cache\n\n\n@clru_cache(None)\ndef csv_column_names(key='start'):\n    return [ f'{key}_{n}' for n in range(25**2) ]\n\n\ndef csv_to_delta(df, idx):\n    return int(df.loc[idx]['delta'])\n\ndef csv_to_delta_list(df):\n    return df['delta'].values\n\n\ndef csv_to_numpy(df, idx, key='start') -> np.ndarray:\n    try:\n        columns = csv_column_names(key)\n        board   = df.loc[idx][columns].values\n    except:\n        board = np.zeros((25, 25), dtype=np.int8)\n    board = board.reshape((25,25))\n    return board.astype(np.int8)\n\n\ndef csv_to_numpy_list(df, key='start') -> np.ndarray:\n    try:\n        columns = csv_column_names(key)\n        output  = df[columns].values.reshape(-1,25,25)\n    except:\n        output  = np.zeros((0,25,25), dtype=np.int8)\n    return output.astype(np.int8)\n\n\n# noinspection PyTypeChecker,PyUnresolvedReferences\ndef numpy_to_dict(board: np.ndarray, key='start') -> Dict:\n    assert len(board.shape) == 2  # we want 2D solutions_3d[0] not 3D solutions_3d\n    assert key in { 'start', 'stop' }\n\n    board  = np.array(board).flatten().tolist()\n    output = { f\"{key}_{n}\": board[n] for n in range(len(board))}\n    return output\n\n\ndef numpy_to_series(board: np.ndarray, key='start') -> pd.Series:\n    solution_dict = numpy_to_dict(board, key)\n    return pd.Series(solution_dict)\n\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)]","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:38.347976Z","iopub.status.busy":"2020-11-14T02:46:38.322017Z","iopub.status.idle":"2020-11-14T02:46:39.45501Z","shell.execute_reply":"2020-11-14T02:46:39.453946Z"},"papermill":{"duration":1.153819,"end_time":"2020-11-14T02:46:39.455196","exception":false,"start_time":"2020-11-14T02:46:38.301377","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"# Source: https://github.com/JamesMcGuigan/ai-games/blob/master/puzzles/game_of_life/utils/game.py\n\n# Functions for implementing Game of Life Forward Play\nfrom typing import List\nfrom typing import Union\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: Union[List[np.ndarray],np.ndarray]) -> List[np.ndarray]:\n    \"\"\" Parallel version of life_step() but for an array of boards \"\"\"\n    return np.array( 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_steps_delta(boards: np.ndarray, deltas: np.ndarray) -> np.ndarray:\n    \"\"\" Parallel version of life_step() but for an array of boards \"\"\"\n    return np.array( Parallel(-1)( delayed(life_step_delta)(board, delta) for (board, delta) in zip(boards, deltas) ) )\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: int, shape=(25,25)) -> np.ndarray:\n    generated_boards = Parallel(-1)( delayed(generate_random_board)(shape) for _ in range(count) )\n    return np.array(generated_boards, dtype=np.int8).reshape((-1, *shape))\n","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:39.48521Z","iopub.status.busy":"2020-11-14T02:46:39.484439Z","iopub.status.idle":"2020-11-14T02:46:40.672043Z","shell.execute_reply":"2020-11-14T02:46:40.671108Z"},"papermill":{"duration":1.204658,"end_time":"2020-11-14T02:46:40.672181","exception":false,"start_time":"2020-11-14T02:46:39.467523","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"import os\nimport sys\nimport pandas as pd\nimport numpy as np\n# from xgboost.sklearn import XGBClassifier\nfrom sklearn.ensemble import RandomForestClassifier\nfrom scipy import signal","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:40.703732Z","iopub.status.busy":"2020-11-14T02:46:40.702966Z","iopub.status.idle":"2020-11-14T02:46:51.302381Z","shell.execute_reply":"2020-11-14T02:46:51.301745Z"},"papermill":{"duration":10.617899,"end_time":"2020-11-14T02:46:51.302517","exception":false,"start_time":"2020-11-14T02:46:40.684618","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"train_df      = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/train.csv',             index_col='id').astype(np.int8)\ntest_df       = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/test.csv',              index_col='id').astype(np.int8)\n# submission_df = pd.read_csv('/kaggle/input/conways-reverse-game-of-life-2020/sample_submission.csv', index_col='id').astype(np.int8)","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:51.334183Z","iopub.status.busy":"2020-11-14T02:46:51.333112Z","iopub.status.idle":"2020-11-14T02:46:51.336049Z","shell.execute_reply":"2020-11-14T02:46:51.336649Z"},"papermill":{"duration":0.022116,"end_time":"2020-11-14T02:46:51.336812","exception":false,"start_time":"2020-11-14T02:46:51.314696","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"# DOCS: https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html\n# DOCS: https://mljar.com/blog/random-forest-memory/\n# DOCS: https://medium.com/swlh/post-pruning-decision-trees-using-python-b5d4bcda8e23\nclassifier_1 = RandomForestClassifier(\n    max_depth=25,     # max_depth affects memory usage   \n    ccp_alpha=0.005,  # prune tree\n    warm_start=True,\n    n_jobs=-1,\n    verbose=0,\n)\n\nclassifier_2 = RandomForestClassifier(\n    max_depth=100,     # max_depth affects memory usage   \n    ccp_alpha=0.005,  # prune tree\n    warm_start=True,\n    n_jobs=-1,\n    verbose=0,\n)\n\n\n### https://www.kaggle.com/c/santander-product-recommendation/discussion/25506\n### You can also use XGBClassifier sklearn-valid API and put it as a classifier in OneVsRestClassifier, according to:\n### http://scikit-learn.org/stable/modules/multiclass.html\n# classifier = XGBClassifier(\n#     learning_rate=0.1,\n#     n_estimators=1000,\n#     max_depth=5,\n#     min_child_weight=1,\n#     gamma=0,\n#     subsample=0.8,\n#     colsample_bytree=0.8,\n#     objective='multi:softprob',\n#     nthread=4,\n#     num_class=625,\n#     seed=27\n# )    ","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:51.374876Z","iopub.status.busy":"2020-11-14T02:46:51.373829Z","iopub.status.idle":"2020-11-14T02:46:51.377578Z","shell.execute_reply":"2020-11-14T02:46:51.376951Z"},"papermill":{"duration":0.028591,"end_time":"2020-11-14T02:46:51.377713","exception":false,"start_time":"2020-11-14T02:46:51.349122","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"def preprocess_X(X, deltas):\n    if isinstance(deltas, int): deltas = np.ones((X.shape[0],1)) * deltas\n    deltas = np.array(deltas).reshape(-1,1)\n        \n    count_neighbours = np.array([[1,1,1],[1,0,1],[1,1,1]], dtype=np.int8)\n    X = np.array([ \n        [ \n            X[n], \n            signal.convolve2d(X[n], count_neighbours, boundary='wrap', mode='same') \n        ] \n        for n in range(len(X)) \n    ], dtype=np.int8)\n    X = X.reshape(X.shape[0], -1)\n    X = np.concatenate([ X, deltas ], axis=1)\n    return X\n\ndef preprocess_Y(Y):\n    Y = Y.reshape(Y.shape[0], -1)\n    return Y","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def tree_accuracy( Y_actual, Y_pred ):\n    return np.mean( np.count_nonzero( Y_actual.reshape(-1,625) == Y_pred.reshape(-1,625), axis=1 ) / 625 )","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.012073,"end_time":"2020-11-14T02:46:51.402378","exception":false,"start_time":"2020-11-14T02:46:51.390305","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Train\n\nTODO: generate random board data"},{"metadata":{"trusted":true},"cell_type":"code","source":"if os.environ.get('KAGGLE_KERNEL_RUN_TYPE', 'Localhost') == 'Interactive':\n    train_df = train_df[:100]\n    test_df  = test_df[:100]","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:51.43549Z","iopub.status.busy":"2020-11-14T02:46:51.434735Z","iopub.status.idle":"2020-11-14T02:46:53.69551Z","shell.execute_reply":"2020-11-14T02:46:53.694704Z"},"papermill":{"duration":2.280868,"end_time":"2020-11-14T02:46:53.695638","exception":false,"start_time":"2020-11-14T02:46:51.41477","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"train_deltas = train_df['delta'].to_numpy()\ntrain_X_raw  = csv_to_numpy_list( train_df, key='stop'  )\ntrain_Y_raw  = csv_to_numpy_list( train_df, key='start' )","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T02:46:53.727733Z","iopub.status.busy":"2020-11-14T02:46:53.727012Z","iopub.status.idle":"2020-11-14T03:15:09.619642Z","shell.execute_reply":"2020-11-14T03:15:09.617053Z"},"papermill":{"duration":1695.910876,"end_time":"2020-11-14T03:15:09.619791","exception":false,"start_time":"2020-11-14T02:46:53.708915","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"%%time\ntrain_X = preprocess_X(train_X_raw, train_deltas)\ntrain_Y = preprocess_Y(train_Y_raw)\nprint(f'train_X.shape: {train_X.shape}, train_Y.shape: {train_Y.shape}')\n\nclassifier_1.fit(train_X, train_Y)\n\ntrain_Y_pred = classifier_1.predict(train_X).reshape(-1,25,25)\ntrain_X_pred = life_steps_delta(train_Y_pred, train_deltas)\n\nprint('train_Y_accuracy: ', tree_accuracy(train_Y_raw, train_Y_pred))\nprint('train_X_accuracy: ', tree_accuracy(train_X_raw, train_X_pred))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"%%time\ntrain_X2 = np.concatenate([\n    train_X,\n    train_Y_pred.reshape(-1,625),\n    train_X_pred.reshape(-1,625),\n    # (train_X_raw != train_X_pred).reshape(-1,625),\n    # preprocess_X(train_X_pred, train_df['delta']),    \n    # preprocess_X(train_Y_pred, train_df['delta']),    \n], axis=1)\nclassifier_2.fit(train_X2, train_Y)\ntrain_Y2_pred = classifier_2.predict(train_X2).reshape(-1,25,25)\ntrain_X2_pred = life_steps_delta(train_Y2_pred, train_deltas)\nprint('train_Y2_accuracy: ', tree_accuracy(train_Y_raw, train_Y2_pred))\nprint('train_X2_accuracy: ', tree_accuracy(train_X_raw, train_X2_pred))","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.015077,"end_time":"2020-11-14T03:15:09.650679","exception":false,"start_time":"2020-11-14T03:15:09.635602","status":"completed"},"tags":[]},"cell_type":"markdown","source":"# Submission"},{"metadata":{"trusted":true},"cell_type":"code","source":"test_deltas = test_df['delta'].to_numpy()\ntest_X_raw  = csv_to_numpy_list( test_df, key='stop'  )\ntest_X      = preprocess_X(test_X_raw, test_deltas)\n\ntest_Y_pred = classifier_1.predict(test_X).reshape(-1,25,25)\ntest_X_pred = life_steps_delta(test_Y_pred, test_deltas).reshape(-1,25,25)\n\nprint('test_X_accuracy: ', tree_accuracy(test_X_raw, test_X_pred))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"test_X2 = np.concatenate([\n    test_X,\n    test_Y_pred.reshape(-1,625),\n    test_X_pred.reshape(-1,625),\n    # (test_X_raw != test_X_pred).reshape(-1,625),\n    # preprocess_X(test_X_pred, test_df['delta']),    \n    # preprocess_X(test_Y_pred, test_df['delta']),    \n], axis=1)\ntest_Y2_pred = classifier_2.predict(test_X2).reshape(-1,25,25)\ntest_X2_pred = life_steps_delta(test_Y2_pred, test_df['delta']).reshape(-1,25,25)\n\nprint('test_X2_accuracy: ', tree_accuracy(test_X_raw, test_X2_pred))","execution_count":null,"outputs":[]},{"metadata":{"execution":{"iopub.execute_input":"2020-11-14T03:18:41.943688Z","iopub.status.busy":"2020-11-14T03:18:41.685017Z","iopub.status.idle":"2020-11-14T03:20:18.546459Z","shell.execute_reply":"2020-11-14T03:20:18.547072Z"},"papermill":{"duration":97.276444,"end_time":"2020-11-14T03:20:18.547241","exception":false,"start_time":"2020-11-14T03:18:41.270797","status":"completed"},"tags":[],"trusted":true},"cell_type":"code","source":"submission_df = pd.DataFrame([ numpy_to_series(test_Y2_pred[n].reshape(25,25)) \n                               for n in range(len(test_Y2_pred)) ])\nsubmission_df.index = test_df.index\nsubmission_df.to_csv('submission.csv')\nsubmission_df","execution_count":null,"outputs":[]},{"metadata":{"papermill":{"duration":0.017676,"end_time":"2020-11-14T03:20:18.583184","exception":false,"start_time":"2020-11-14T03:20:18.565508","status":"completed"},"tags":[]},"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 implementions of the Game of Life Foward 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}