[{"_1":2,"_173":-5,"_174":-5},"loaderData",{"_3":4,"_92":93},"root",{"_5":6,"_35":36,"_65":66},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20,"_34":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","isTeamOrgMember","ENV",{"_37":38,"_39":40,"_41":42,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":54,"_55":56,"_57":58,"_59":60,"_61":62,"_63":64},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","c2ca74b25698bc62f1250d595e4f42af9437a7d5","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_67":68},"__internal_clerk_state",{"_69":70,"_71":46,"_72":73,"_74":73,"_75":20,"_76":73,"_77":73,"_78":73,"_79":73,"_80":81,"_90":20,"_91":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_82":20,"_19":20,"_83":73,"_84":85,"_86":73,"_87":46,"_88":20,"_89":73},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_94":95,"_96":97,"_98":99,"_100":101,"_151":152,"_169":170,"_171":172},"handle","saolsen","name","connect4_ai","path","connect4_ai.wgsl","project",{"_102":103,"_96":97,"_104":105,"_106":-5,"_107":20,"_108":109,"_110":111,"_112":-5,"_12":113,"_114":115,"_116":117,"_118":117,"_119":-5,"_120":32,"_14":121,"_122":123,"_124":123,"_125":126,"_127":126,"_128":126,"_129":123,"_130":123,"_23":131,"_134":135,"_137":138,"_150":20},"id","088bb54e-b5d4-11f0-8260-0224a6c84d84","createdAt",["D",1761858272949],"deletedAt","legacyEnvVars","privacy","public","description","Parallel connect4 bot in a webgpu compute shader.","imageUrl","e1269f9c-67ab-446c-9c3f-debdc882a7b8","pinnedFileId","6cabdbd4-b5d5-11f0-a1d5-0224a6c84d84","pinPreview",true,"pinMigrated","screenshotVersion","likeCount","6af58753-71c6-4397-9d5b-2473eb888976","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_94":95,"_132":133},"profileImageUrl","https://images.clerk.dev/oauth_github/img_2QtXHzN3gDPhKsBOvKsst8LTxC5.png","org",{"_94":95,"_136":133,"_12":113},"avatar","branch",{"_139":140,"_96":44,"_102":141,"_142":103,"_143":-5,"_144":-5,"_145":-5,"_146":-5,"_147":-5,"_148":97,"_149":95},"version",1228,"088c2bb4-b5d4-11f0-8260-0224a6c84d84","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_102":153,"_96":99,"_154":155,"_156":-5,"_157":141,"_158":159,"_160":117,"_104":161,"_139":162,"_163":151,"_164":165,"_166":20,"_167":-5,"_98":168},"5e4b0846-ba65-11f0-9dee-0224a6c84d84","fileId","a87a0e22-b901-11f0-9479-0224a6c84d84","parentId","branchId","branchVersion",1220,"latest",["D",1762360498477],5,"fileType","content","const ROWS: u32 = 6;\nconst COLS: u32 = 7;\n\nstruct Connect4State {\n red_cols: array,\n yellow_cols: array,\n current_player: u32,\n in_progress: u32,\n winning_player: u32,\n}\n\nfn connect4_apply_action(current_state: Connect4State, player: u32, action: u32) -> Connect4State {\n var state: Connect4State = current_state;\n for (var row: u32 = 0u; row < ROWS; row = row + 1u) {\n let bit: u32 = 1u << row;\n if (((state.red_cols[action] | state.yellow_cols[action]) & bit) == 0u) {\n if (player == 1u) {\n state.red_cols[action] = state.red_cols[action] | bit;\n } else {\n state.yellow_cols[action] = state.yellow_cols[action] | bit;\n }\n break;\n }\n }\n\n // Check for a win or draw.\n var player_cols: array;\n if (player == 1u) {\n player_cols = state.red_cols;\n } else {\n player_cols = state.yellow_cols;\n };\n\n // Check vertical.\n for (var col: u32 = 0u; col < COLS; col = col + 1u) {\n for (var row: u32 = 0u; row < 3; row = row + 1u) { \n if (((player_cols[col] & (1u << (row + 0u))) != 0u) &&\n ((player_cols[col] & (1u << (row + 1u))) != 0u) &&\n ((player_cols[col] & (1u << (row + 2u))) != 0u) &&\n ((player_cols[col] & (1u << (row + 3u))) != 0u)) {\n state.in_progress = 0u;\n state.winning_player = player;\n return state;\n }\n }\n }\n // Check horizontal.\n for (var col: u32 = 0u; col < 4; col = col + 1u) {\n for (var row: u32 = 0u; row < ROWS; row = row + 1u) {\n if (((player_cols[col + 0u] & (1u << row)) != 0u) &&\n ((player_cols[col + 1u] & (1u << row)) != 0u) &&\n ((player_cols[col + 2u] & (1u << row)) != 0u) &&\n ((player_cols[col + 3u] & (1u << row)) != 0u)) {\n state.in_progress = 0u;\n state.winning_player = player;\n return state;\n }\n }\n }\n // Check diagonal up-right.\n for (var col: u32 = 0u; col < 4; col = col + 1u) {\n for (var row: u32 = 0u; row < 3; row = row + 1u) {\n if (((player_cols[col + 0u] & (1u << (row + 0u))) != 0u) &&\n ((player_cols[col + 1u] & (1u << (row + 1u))) != 0u) &&\n ((player_cols[col + 2u] & (1u << (row + 2u))) != 0u) &&\n ((player_cols[col + 3u] & (1u << (row + 3u))) != 0u)) {\n state.in_progress = 0u;\n state.winning_player = player;\n return state;\n }\n }\n }\n // Check diagonal down-right.\n for (var col: u32 = 0u; col < 4; col = col + 1u) {\n for (var row: u32 = 3u; row < 6; row = row + 1u) {\n if (((player_cols[col + 0u] & (1u << (row - 0u))) != 0u) &&\n ((player_cols[col + 1u] & (1u << (row - 1u))) != 0u) &&\n ((player_cols[col + 2u] & (1u << (row - 2u))) != 0u) &&\n ((player_cols[col + 3u] & (1u << (row - 3u))) != 0u)) {\n state.in_progress = 0u;\n state.winning_player = player;\n return state;\n }\n }\n }\n // Check for possible moves\n for (var col: u32 = 0u; col < COLS; col = col + 1u) {\n if (((state.red_cols[col] | state.yellow_cols[col]) & 0x3Fu) != 0x3Fu) {\n // Found a possible move.\n state.in_progress = 1u;\n state.winning_player = 0u;\n if (player == 1u) {\n state.current_player = 2u;\n } else {\n state.current_player = 1u;\n }\n return state;\n }\n }\n\n // Draw\n state.current_player = 0u;\n state.in_progress = 0u;\n state.winning_player = 0u;\n return state;\n}\n\nconst NODEHEADER_IN_USE_BIT: u32 = 1u << 31u;\nconst NODEHEADER_ACTIONS_MASK: u32 = 0x7Fu;\nconst NODEHEADER_ACTIONS_PUSHED_MASK: u32 = NODEHEADER_ACTIONS_MASK << 8u;\nconst NODEHEADER_ACTIONS_FINISHED_MASK: u32 = NODEHEADER_ACTIONS_MASK << 16u;\n\nfn node_header_actions_get(header: u32) -> u32 {\n return header & NODEHEADER_ACTIONS_MASK;\n}\nfn node_header_actions_set(header: u32, actions: u32) -> u32 {\n return (header & ~NODEHEADER_ACTIONS_MASK) | (actions & NODEHEADER_ACTIONS_MASK);\n}\n\nfn node_header_actions_pushed_get(header: u32) -> u32 {\n return (NODEHEADER_ACTIONS_PUSHED_MASK & header) >> 8u;\n}\nfn node_header_actions_pushed_set(header: u32, actions_pushed: u32) -> u32 {\n return (header & ~NODEHEADER_ACTIONS_PUSHED_MASK) | ((actions_pushed & NODEHEADER_ACTIONS_MASK) << 8u);\n}\n\nfn node_header_actions_finished_get(header: u32) -> u32 {\n return (NODEHEADER_ACTIONS_FINISHED_MASK & header) >> 16u;\n}\nfn node_header_actions_finished_set(header: u32, actions_finished: u32) -> u32 {\n return (header & ~NODEHEADER_ACTIONS_FINISHED_MASK) | ((actions_finished & NODEHEADER_ACTIONS_MASK) << 16u);\n}\n\nstruct StackEntry {\n state: Connect4State,\n actions: array,\n action_scores: array,\n action_count: i32,\n \n parent_node_i: i32,\n parent_action_i: i32,\n last_pushed_child_action_i: i32,\n depth: i32,\n}\n\nfn connect4_minimax(root_state: Connect4State, max_depth: i32) -> f32 {\n var result: f32 = 0.0;\n \n var stack: array;\n var stack_count: u32 = 0u;\n \n var root: StackEntry;\n root.state = root_state;\n root.action_count = 0;\n root.parent_node_i = -1;\n root.parent_action_i = -1;\n root.last_pushed_child_action_i = -1;\n root.depth = 0;\n\n stack[0] = root;\n stack_count = 1;\n\n while(stack_count > 0) {\n let top_i: i32 = i32(stack_count) - 1;\n let top: ptr = &stack[top_i];\n\n if (top.action_count == 0) {\n // Initialize actions.\n for (var col: u32 = 0u; col < COLS; col = col + 1u) {\n // Check if column is full.\n if ((top.state.red_cols[col] | top.state.yellow_cols[col]) == 0x3Fu) {\n continue;\n }\n top.actions[top.action_count] = col;\n top.action_count = top.action_count + 1;\n }\n }\n\n if (top.last_pushed_child_action_i < top.action_count - 1) {\n // Push next child.\n top.last_pushed_child_action_i = top.last_pushed_child_action_i + 1;\n let col: u32 = top.actions[top.last_pushed_child_action_i];\n let child_state: Connect4State = connect4_apply_action(top.state, top.state.current_player, col);\n\n if (child_state.in_progress == 0u || top.depth == max_depth - 1) {\n // Leaf node, score right away.\n var score: f32 = 0.0;\n if (child_state.winning_player == input_data.current_player) {\n score = 1.0;\n } else if (child_state.winning_player != 0u) {\n score = -1.0;\n }\n top.action_scores[top.last_pushed_child_action_i] = score;\n } else {\n // Push child onto stack.\n var child: StackEntry;\n child.state = child_state;\n child.action_count = 0;\n child.parent_node_i = top_i;\n child.parent_action_i = i32(top.last_pushed_child_action_i);\n child.last_pushed_child_action_i = -1;\n child.depth = top.depth + 1;\n\n stack[stack_count] = child;\n stack_count = stack_count + 1;\n }\n } else {\n // Compute score and pop.\n var score: f32;\n if (top.state.current_player == input_data.current_player) {\n score = -1000.0;\n for (var action_i: i32 = 0; action_i < top.action_count; action_i = action_i + 1) {\n score = max(score, top.action_scores[action_i]);\n }\n } else {\n score = 1000.0;\n for (var action_i: i32 = 0; action_i < top.action_count; action_i = action_i + 1) {\n score = min(score, top.action_scores[action_i]);\n }\n }\n\n // Write score to parent.\n if (top.parent_node_i == -1) {\n result = score;\n break;\n } else {\n let parent: ptr = &stack[top.parent_node_i];\n parent.action_scores[top.parent_action_i] = score;\n stack_count = stack_count - 1;\n }\n }\n }\n\n return result;\n}\n\nfn connect4_minimax_child(root_state: Connect4State, depth: i32, action_path: array, action_count: u32) -> f32 {\n // Traverses down to the specified child node and runs minimax from there.\n\n var state: Connect4State = root_state;\n for (var i: u32 = 0u; i < action_count; i = i + 1u) {\n let action: u32 = action_path[i];\n if ((state.red_cols[action] | state.yellow_cols[action]) == 0x3Fu) {\n if (state.current_player == input_data.current_player) {\n return -1000.0;\n } else {\n return 1000.0;\n }\n }\n state = connect4_apply_action(state, state.current_player, action);\n if (state.in_progress == 0u) {\n if (state.winning_player == input_data.current_player) {\n return 1.0;\n } else if (state.winning_player != 0u) {\n return -1.0;\n } else {\n return 0.0;\n }\n }\n }\n return connect4_minimax(state, depth);\n}\n\n// Expand out to the parallelism we have and then do a dfs minimax from there.\n// There are 7 workgroups, each workgroup has 49 threads.\n// So each thread is scoring a node 3 layers down from the root.\n// Once all the threads are done, reduce the scores up those layers to the root and return them.\n\n// Each dfs eval checks 5 moves ahead so all together we're doing an 8 move search.\n\nvar workgroup_scores: array;\nvar thread_scores: array;\n\n@group(0) @binding(0) var input_data: Connect4State;\n@group(0) @binding(1) var output_data: array;\n\n@compute @workgroup_size(49)\nfn main(\n @builtin(workgroup_id) workgroup_v : vec3,\n @builtin(local_invocation_index) local_invocation_index: u32,\n) {\n let workgroup_i: u32 = workgroup_v.x;\n let thread_i: u32 = local_invocation_index;\n\n let workgroup_action: u32 = workgroup_i;\n let thread_first_action: u32 = thread_i / 7u;\n let thread_second_action: u32 = thread_i % 7u;\n\n var child_action_path: array;\n child_action_path[0] = workgroup_action;\n child_action_path[1] = thread_first_action;\n child_action_path[2] = thread_second_action;\n\n let thread_score: f32 = connect4_minimax_child(input_data, 5, child_action_path, 3u);\n thread_scores[thread_i] = thread_score;\n\n workgroupBarrier();\n\n if (thread_i % 7u == 0u) {\n var action_score: f32 = -1000.0;\n for (var i: u32 = 0u; i < 7u; i = i + 1u) {\n let score: f32 = thread_scores[thread_i + i];\n action_score = max(action_score, score);\n }\n workgroup_scores[thread_i / 7u] = action_score;\n }\n\n workgroupBarrier();\n\n if (thread_i == 0u) {\n var final_score: f32 = 1000.0;\n for (var i: u32 = 0u; i < 7u; i = i + 1u) {\n let score: f32 = workgroup_scores[i];\n final_score = min(final_score, score);\n }\n output_data[workgroup_i] = final_score;\n }\n}\n\n// getting a problem where it always gives up if it could lose if the player plays perfectly.\n// weighting scores by depth helps with that.","deleted","label",[99],"permalink","https://www.val.town/x/saolsen/connect4_ai/code/connect4_ai.wgsl","extension","wgsl","actionData","errors"]