Game Theory Algorithms in Competitive Programming

Learn how to set up Sublime Text for competitive programming, create a project with new.cpp, input.txt, and output.txt, arrange three columns, and configure input/output redirection.

Learn to fix MacOs clang missing bits/stdc++.h by creating a master header stdc++.h that aggregates all C and C++ headers, enabling smooth submission and builds.

Learn how online judges validate code by testing input.txt and output.txt, with examples from Spoj, CodeChef, and Codeforces, and use #ifndef/#ifdef for local versus online compilation.

Create sublime snippets to map keyboard triggers to full code templates, using a tabTrigger like cpsimple to insert CP boilerplate and save time in contests.

Explore practical macros and typedefs to save time in competitive programming. Learn how to choose int versus long long, use pair and vector, and apply push_back for concise code snippets.

Explore a practical code template used in competitive programming, including common macros, vector operations, bulk input/output, debugging tips, and handling interactive problems.

Introduces combinatorial games as two-player, perfect-information, no chance-move games with finite positions; distinguishes impartial and partizan play, normal and misere rules, and terminal positions using Nim as example.

Explore a simple takeaway game with two optimal players, removing 1–3 stones from a pile, solved by backward induction and bottom-up dynamic programming to identify winning and losing positions.

Explore a simple take-away game under the misere rule, contrasting with the normal rule, and identify losing and winning positions; the pattern N mod 4 = 1 is losing.

Explore subtraction takeaway games by analyzing sets like {1,2,3,4,5} and {2,4}, and derive a six-term cycle where n mod 6 equals 0 or 1 is losing, otherwise winning for Alice.

Define n-positions and p-positions, identifying winning and losing positions for the current and next player. Apply a backward marking method from terminal positions to classify positions.

The lecture analyzes the empty and divide game, where one box is emptied and the other split into nonempty parts. It presents parity rules to identify winning and losing positions.

Explore the game of Nim, where players remove chips from a single pile, identify winning and losing positions with two or three piles and equal piles, and introduce Nim generalization.

Explore nim sum, the xor-based operation in game theory defined as addition without carry in binary, and learn its commutative, associative properties with zero as identity.

Explain the name sum concept by modeling game positions as sum of pile sizes, show zero name-sum positions are losing, and outline a winning strategy using the most significant bit.

Analyze how different games like nim and the name game map to nim heaps, with moves that reduce piles by left or downward moves, and learn winning and losing positions.

Represent games as directed acyclic graphs with positions and followers, identify terminal positions, and compute Sprague-Grundy values using mex of followers to distinguish winning and losing positions.

Learn how to compute the Sprague-Grundy function for dynamic subtraction games, using examples to derive Grundy values and practical strategies for competitive programming.

Learn to compute sprague-grundy values for impartial games in C++, using mex of reachable values, memoization, and dynamic programming to reveal patterns and fast solutions.

Explore how to represent and solve the sum of games using the Sprague-Grundy theorem, compute Grundy values, and determine winning and losing positions in competitive programming.

Solve a curated set of game theory problems to strengthen your understanding of competitive programming. Tackle around 30 problems of varying difficulty, write C++ solutions, and share code on GitHub.

Analyze the game of stones with moves of two, three, or five, identify winning and losing positions, and derive a repeating pattern for efficient winner determination.

Two players take turns reducing a tower's height to any smaller positive value; under optimal play, the starting number of towers and heights determine the winner.

Explains a two-player chessboard coin game on a 15 by 15 board, where players move the coin to four legal positions and determine winning states via memoized dynamic programming.

Explore the nim game, where two players remove any number of stones from a pile, with the last move winning; a zero nim-sum position favors the second player.

Learn misere nim strategies by analyzing pile states and the name sum, enabling you to force the last-move loss and handle special cases with ones.

Convert nimble into a nim game by treating odd coin counts on squares as heaps and ignoring even counts, then compute the nim-sum of those positions to decide the winner.

Alice and Bob's silly game has players pick prime from 1 to n and remove its multiples; moves equal primes up to n, parity decides winner, using sieve of Eratosthenes.

examine a Nim-like game where players remove or add chips to piles, revealing that adding then removing is reversible and the strategy reduces to the standard Nim solution.

Explore tower breakers revisited, where players alternate reducing a tower height and model moves as sums of prime powers, solved via sieve or factorization to predict the winner.

Explore a tower breaking game where players split a height x into multiple parts. Analyze optimal play using Grundy values and memoization to determine the winner.

Continue with the previous video on the tower problem, add the time limit and test cases, review and edit the earlier submission, and clarify the approach for tower breakers.

Explore zero move nim, a one-time move per player that lets you remove stones from a non-empty pile, and use brute-force patterns to derive winning strategies for competitive games.

Explore a two-player chessboard game on a 15x15 grid with multiple coins, and determine winning moves using Grundy numbers, mex, and memoized state evaluation.

Analyze a game on a digits square board by partitioning the board into subgames, selecting moves that create prime-filled boards, and using memoized Grundy-like values to decide winners.

Explore stone division game, where two players split piles into equal parts, determine winning or losing positions with a boolean strategy, and use memoization to optimize without full Grundy values.

Explains a chocolate in the box game where players remove chocolates from one non-empty container. Identify losing positions as zero sums and count optimal moves under optimal play.

Kitty and Katty explain a two-player block game where A and B are removed and replaced by A minus B until one block remains, with X influenced by modular arithmetic.