Meta tags:
author=Gwern, FeepingCreature, nshepperd, Khoth;
description=Timothy Falcon’s quantitative-finance interview problem #14 asks for the optimal stopping strategy when playing a card-drawing game of  𝑙 cards where red = +$1 & black = −$1; the value approaches 0.5 × √𝑙. I re-solve it with dynamic programming in R, and others in Neat, Haskell & C, with increasing efficiency.;
keywords=cs/c, cs/haskell, cs/r, statistics/decision;

Headings (most frequently used words):

dynamic, programming, dp, bottom, up, neat, array, blocks, problem, 14, solutions, non, optimal, stopping, version, spreadsheet, answer, top, down, faster, approximating, backlinks, similar, links, bibliography, haskell, parallel, simulation, check, diagonal, diagonalization, skipping,

Text of the page (most frequently used words):
the (234), int (184), cards (98), value (73), and (67), for (67), dia (65), work (58), return (53), good (47), that (43), thread (38), bad (35), with (34), you (34), red (34), can (33), black (33), void (31), this (30), rem_black (30), rem_red (29), float (29), count (28), include (28), winnings (26), state (26), prevdia (25), num_blocks (24), define (24), threads (23), problem (22), prev_dia (22), cash (22), block_size (22), like (21), which (21), else (21), one (20), are (20), optimal (20), card (20), work_item_t (20), config (20), data (19), version (18), cur (18), time (17), bool (17), max (17), because (17), step (17), col (16), row (16), error (15), values (15), game (15), khoth (14), but (14), 000 (14), expected (14), limit (14), base_r (14), cur_dia (14), bottom (14), payoff (14), ascent (14), curdia (14), array (14), while (13), 22e (13), square (13), root (13), feepingcreature (13), base_b (13), will (13), approximation (12), has (12), all (12), states (12), programming (12), struct (12), each (12), then (11), log (11), true (11), size (11), not (11), table (11), there (11), only (11), cpu (11), r0_edge (11), num_threads (11), b0_edge (11), main (11), blocks (11), auto (11), clang (10), out (10), std (10), exact (10), space (10), possible (10), from (10), faster (10), core (10), num_cards (10), value_if_stop (10), value_if_go (10), diag_arr (10), head (10), tail (10), pred (10), active (10), import (10), dynamic (10), rounds (10), diagonal (9), down (9), spreadsheet (9), when (9), calc (9), dia1 (9), dia2 (9), configs (9), tab (9), dpcalc (9), expectedvalue (9), key (9), null (8), some (8), gcc (8), multiple (8), squared (8), sqrt (8), frame (8), 100 (8), double (8), block (8), than (8), done_sem (8), put_work (8), work_sem (8), r_ix (8), b_ix (8), work_queue_len (8), stdio (8), look (8), pblack (8), false (8), threadconfig (8), outcome (8), play (8), playpayoff (8), winning (8), stopping (8), what (7), would (7), enough (7), deck (7), could (7), type (7), final (7), draw (7), more (7), they (7), where (7), printf (7), r_progress (7), must (7), stop (7), much (7), how (7), evaluation (7), using (7), blacks (7), haskell (7), mut (7), function (7), neat (7), cache (7), playing (7), links (6), used (6), 165 (6), pthread (6), case (6), volatile (6), intercept (6), small (6), probability (6), problems (6), estimate (6), min (6), initial (6), have (6), before (6), into (6), parallel (6), implementation (6), calculate (6), block_b (6), put_work_mutex (6), b_progress (6), work_queue (6), get (6), ret (6), grab_work_mutex (6), triangle (6), code (6), bool_set_spin (6), bool_wait_spin (6), drawn (6), dia_from (6), dia_to (6), malloc (6), sizeof (6), math (6), evaluate (6), any (6), tmp (6), still (6), solve (6), new (6), top (6), montecarlo (6), simulation (6), similar (5), backlinks (5), think (5), performance (5), native (5), use (5), march (5), ofast (5), optimization (5), few (5), kelly (5), coefficients (5), 22974 (5), residual (5), standard (5), lsqrt (5), available (5), 133 (5), just (5), counts (5), know (5), way (5), larger (5), level (5), should (5), every (5), higher (5), run (5), skipped (5), block_r (5), independently (5), may (5), check (5), optimized (5), nshepperd (5), print (5), reds (5), fromintegral (5), games (5), policy (5), strategy (5), simulategame (5), bibliography (4), here (4), require (4), pgo (4), parallelism (4), help (4), complexity (4), 076 (4), coin (4), flip (4), makes (4), doesn (4), further (4), gets (4), bigger (4), looks (4), constant (4), does (4), statistic (4), adjusted (4), degrees (4), freedom (4), median (4), residuals (4), summary (4), 133787000 (4), rbind (4), 133m (4), fit (4), increases (4), fits (4), seems (4), too (4), element_blank (4), strip (4), theme (4), 100000 (4), gwern (4), decision (4), 2022 (4), calculation (4), thus (4), such (4), arithmetic (4), calculations (4), long (4), might (4), after (4), 038 (4), better (4), large (4), also (4), sem_wait (4), workers (4), worker_thread (4), sem_init (4), handle_work_done (4), do_block (4), thread_id (4), get_work (4), arg (4), get_black_val (4), get_red_val (4), pthread_mutex_unlock (4), sem_post (4), pthread_mutex_lock (4), pthread_mutex_t (4), pthread_mutex_initializer (4), sem_t (4), div_round_up (4), stdbool (4), left (4), depend (4), take (4), sem (4), upindex (4), leftindex (4), calc_thread (4), stdlib (4), other (4), them (4), your (4), fourteen (4), retval (4), vector (4), sum (4), zheng (4), playvalue (4), end (4), quit (4), memoise (4), random (4), answer (4), specific (4), walk (4), day (3), javascript (3), given (3), generate (3), slower (3), both (3), 787 (3), near (3), plotting (3), approximations (3), almost (3), negative (3), grows (3), slowly (3), text (3), position (3), 000000 (3), llogsqrt (3), predict (3), llog (3), 100k (3), quite (3), make (3), problem14 (3), compute (3), needs (3), fixed (3), now (3), ever (3), overhead (3), becomes (3), been (3), again (3), provide (3), computed (3), days (3), threadripper (3), minutes (3), original (3), big (3), 400 (3), since (3), runs (3), pthread_create (3), pthread_t (3), solution (3), remaining (3), don (3), need (3), skipping (3), instead (3), col_base (3), row_base (3), descent_task (3), descent (3), right (3), ascent_task (3), soon (3), processes (3), thousands (3), millions (3), vectorize (3), without (3), even (3), total_return (3), iters (3), rand (3), module (3), changing (3), back (3), start (3), set (3), memoization (3), leave (3), class (3), base (3), han (3), statecache (3), simply (3), choices (3), easy (3), 624475549 (3), being (3), sampling (3), replacement (3), solved (3), 296 (3), 322 (3), cell (3), bet (3), solutions (3), brownian (3), interview (3), naive (3), question (3), annotation (2), site (2), hairsp (2), page (2), disabled (2), never (2), close (2), machine (2), isn (2), smart (2), 0m0 (2), user (2), profiling (2), prof (2), fprofile (2), last (2), actually (2), who (2), win (2), bit (2), relative (2), slightly (2), often (2), 573 (2), 563 (2), largest (2), zero (2), well (2), points (2), terms (2), issues (2), somewhere (2), ignoring (2), background (2), geom_point (2), none (2), legend (2), ylab (2), xlab (2), aes (2), geom_line (2), qplot (2), 91897 (2), 978735 (2), 525 (2), 154 (2), etc (2), 0186936 (2), 522088 (2), 22973 (2), 106 (2), 331 (2), things (2), seq (2), net (2), approximating (2), hard (2), course (2), bound (2), guess (2), truncation (2), perhaps (2), sub (2), precision (2), something (2), below (2), ability (2), wasted (2), point (2), scenarios (2), payoffs (2), same (2), computers (2), parallelization (2), range (2), dependencies (2), gpu (2), calculated (2), intermediate (2), speedup (2), skip (2), turns (2), comparing (2), 009 (2), yields (2), arrays (2), presumably (2), around (2), runtime (2), uintptr_t (2), intptr_t (2), meh (2), nasty (2), put (2), asymmetry (2), locking (2), arsed (2), making (2), nice (2), typedef (2), lazy (2), stdint (2), semaphore (2), whole (2), simple (2), most (2), off (2), half (2), looking (2), gives (2), wall (2), breaking (2), evaluated (2), different (2), evaluates (2), many (2), finish (2), efficiency (2), upper (2), worker_task (2), param (2), marker (2), visualization (2), aid (2), synchronization (2), split (2), keep (2), cores (2), spinlock (2), hits (2), constantly (2), own (2), parts (2), his (2), laptop (2), next (2), starts (2), approach (2), diagonalization (2), actual (2), operations (2), modern (2), multi (2), computer (2), far (2), between (2), simplest (2), easiest (2), took (2), write (2), first (2), tops (2), 143 (2), hours (2), milliseconds (2), compiled (2), rather (2), probably (2), avx (2), means (2), instructions (2), ought (2), later (2), pattern (2), factors (2), run_game (2), argv (2), argc (2), fill_array (2), break (2), should_stop (2), rand_lim (2), divisor (2), note (2), was (2), 41984711742427 (2), 15997372030584 (2), requested (2), immediately (2), roots (2), tuple (2), ask (2), length (2), shuffle (2), monte (2), carlo (2), over (2), action (2), decide (2), nothing (2), macro (2), hashmap (2), result (2), string (2), language (2), library (2), simulategamelog (2), runif (2), ith (2), sample (2), see (2), quitvalue (2), fact (2), lets (2), choice (2), confirm (2), correct (2), 000000000 (2), returns (2), entire (2), probabilities (2), sequence (2), sound (2), computational (2), analysis (2), shows (2), 3333 (2), 6571 (2), 1667 (2), 1429 (2), 4524 (2), 125 (2), 1111 (2), 841 (2), 048 (2), 09091 (2), 08333 (2), 377 (2), 07692 (2), 202 (2), 3889 (2), 603 (2), 674 (2), 084 (2), 484 (2), 146 (2), 9049 (2), 618 (2), 264 (2), 624 (2), maximum (2), coldwell (2), non (2), corresponds (2), quantitative (2), finance (2), prices (2), stock (2), their (2), bridge (2), counterintuitive (2), rule (2), dollar (2), high (2), efficient (2), implementations (2), adblock, public, service, announcement, quote, send, anonymous, feedback, references, topic, enabled, load, hurt, apparently, sys, 043s, 0m7, 486s, real, 540s, merge, default_, profraw, output, llvm, profdata, dev, trick, sometimes, squeeze, another, did, 03s, compile, reason, replacing, declarations, compiles, _atomic, calculates, omniscient, player, knew, order, expect, howe, 2014, adjusts, drops, multiplier, smaller, offset, converge, numbers, soak, zig, zag, staircase, discretization, sees, 25955e, 00245711, 22048e, 93756e, 2694354, 736, 46229e, 54948e, 10346355, 00010533, 00071383, 00105519, 00453808, 6038, compare, changes, consistent, suspiciously, along, tiny, misfit, term, vanishes, asymptotically, wonder, logarithmic, 294, hidden, erroneous, everywhere, adding, additional, unnecessary, indicate, serious, reveals, wildly, inaccurate, early, hitting, compared, perfectly, ggtitle, 313131, 5b6b6b, 999999, scale_color_manual, dashed, linetype, base_size, theme_bw, color, 11482e, 68411, 91493e, 45612e, 063, 40946e, 66876e, 225, 66931e, 72306e, 917, 34388, 34909, 15215, 34937, 80501, 100m, 5220, 16509, 10b, 52208, 100b, 165098, 080028, 522, 10m, 1650, 28726e, 00187101, 22088e, 45212e, 1512369, 327, 86936e, 70052e, 505, 163, 05298383, 00071444, 00047093, 00121099, 01869362, 185369, 889734, 889729, 19828, 6267169, 0409405, 430, 545, 6454973, 3724555, 286, 62279, 98638, 00526, 96333, 107, 14550, delete, entry, easier, logs, https, doc, statistics, bottomup, values0to22974, txt, read, spend, figure, heuristic, once, falls, represent, number, spent, floating, format, truncating, estimates, avoid, full, rollouts, suspect, turn, calculating, wide, beam, width, through, devoted, increasingly, astronomically, unlikely, contribute, tinier, massive, penalties, lurking, old, network, latency, less, issue, parallelizing, across, useful, cluster, local, done, minimal, control, flow, scream, low, cuda, ensure, stay, gpus, why, shortcut, begin, storing, pre, algorithm, power, caching, short, analytical, expressions, possibilities, october, 184, 78162, finetuned, 32303, 0017, 0146229, 522048, kicks, thought, static, balks, messed, 818, 2m10s, found, closer, bumped, safe, linker, halving, profile, guided, 1000, worse, cuts, lower, skips, computations, doubles, speed, fastest, total, under, 85s, diagonalized, expose, profitable, improves, locality, assigns, nested, within, diagonally, phase, become, setup, moderately, severe, manual, tweaking, suggested, diagram, wise, appears, 075847, ryzen, 1950, 76ya, amd, atomic_store, atomic_load, _mm_pause, col_from, col_to, stdatomic, immintrin, busy, hasn, yet, finishes, computing, necessary, grab, resume, its, computation, little, delay, provides, parallelized, tries, pending, separate, separately, spin, until, moves, 001, reduces, lock, creating, communicating, vastly, greater, addition, division, multiplication, anything, involving, ipc, safely, assumed, cost, equivalent, hundreds, above, worthwhile, difference, programmer, myself, takes, seconds, versions, programmers, advice, however, care, wait, illustrates, potential, ran, substantially, got, 17s, evaluating, due, poor, vectorization, reported, second, 512, fopt, info, vec, 200000, particular, single, depending, previous, cannot, nor, compiler, forfeit, our, despite, reasonably, lots, distant, prior, call, loops, refer, batch, subset, chosen, moving, seem, vmaxp, simd, threaded, traversal, illustration, asymptotic, improved, avg, atoi, srand, shitty, cares, char, rand_max, implemented, fourteen2, show, lambdas, golfed, 624475, 572700, 520043, 466309, 411082, 354246, 295858, 235999, 174761, 112214, 048282, 982391, 913208, 840810, 765412, 687397, 607228, 524702, 434110, 335373, 229437, 119048, 850000, 666667, 500000, fmax, port, 624475548993925, rational, ord, fractional, qualified, ratio, decimal, factor, linear, patient, reasonable, 974, file, least, requesting, bunch, repl, continually, shrinking, tree, structure, follows, sort, wave, ripple, won, revisit, discarded, throw, move, forth, those, understand, sets, logical, dependency, enables, requests, desired, comes, drawback, taking, store, metal, struggle, possibly, tens, gigabytes, memory, 10_000, 10_000_000, typeof, extern, listcomprehension, notes, converted, flat, especially, stops, tracking, tracks, reporting, marginal, free, based, results, confirms, wrote, written, custom, ylim, coord_cartesian, facet_wrap, ggplot2, rep, implicit, boundary, trajectories, simulating, fairly, risky, usually, wins, 6243913, 10000000, replicate, mean, 62447555, attain, claimed, specified, two, doing, instantly, worth, 21519192, stack, 295858627, 354246421, 411081973, 466309395, 520043731, 572700079, 840809473, 913207824, 982391061, 048281891, 112213746, 174760756, 235998731, 229437229, 335372960, 434110334, 524701769, 607227911, 687397226, 765411833, 500000000, 666666667, 850000000, 119047619, sapply, balanced, slow, tricky, part, tripped, initially, yielded, accidentally, leaving, dependent, vice, versa, push, towards, middle, hint, remains, were, reversion, always, ride, luck, itself, borrowing, dynamics, recursion, instant, yes, brute, force, optimally, combinatorially, infeasible, illusory, reduce, reused, harder, perfect, example, variables, boundaries, forced, reasoning, opaque, buried, clear, construct, scale, sizes, trades, growing, logarithm, walks, involve, 6667, 343, 444, 067, 5357, 7937, 119, 2857, 9091, 229, 656, 232, 3917, 5606, 7639, 015, 335, 754, 299, 2222, 3455, 4889, 6581, 8618, 114, 434, 356, 3091, 4336, 5779, 7483, 9542, 208, 919, 427, 101, 1818, 2797, 3896, 5152, 6608, 8334, 042, 607, 998, 499, 152, 2555, 3538, 4647, 5916, 7394, 9144, 124, 687, 569, 199, 1538, 2352, 3242, 4234, 5356, 6643, 8143, 9914, 455, 765, 151, 635, 241, 07143, 2179, 2992, 4892, 7338, 886, 065, 276, 531, 223, 696, 026, 06667, 1333, 2029, 2778, 3596, 4504, 5521, 6678, 8006, 9546, 135, 348, 913, 291, 753, 328, 059, 0625, 2593, 3346, 4173, 5092, 6126, 7301, 8648, 417, 982, 355, 811, 378, 094, 05882, 1176, 1785, 2431, 3128, 3888, 4726, 5659, 671, 7903, 9267, 268, 741, 418, 429, 127, 05556, 1684, 2289, 2937, 364, 4409, 5259, 6208, 7275, 8484, 9866, 332, 549, 806, 112, 928, 479, 05263, 1053, 1594, 2163, 2769, 3422, 4133, 4913, 5776, 7823, 045, 206, 393, 612, 869, 175, 541, 986, 528, 1513, 205, 2619, 3229, 4609, 5401, 6278, 7256, 8355, 9598, 102, 265, 453, 673, 931, 236, 601, 041, 574, 219, 006, 04762, 09524, 144, 1948, 2485, 3058, 3674, 4342, 5072, 5876, 6767, 7759, 8874, 013, 157, 511, 732, 659, 095, 249, 027, 04545, 1374, 1856, 2364, 2903, 3481, 4105, 4782, 5523, 6339, 7243, 825, 9381, 066, 211, 568, 049, 354, 716, 661, 284, 051, 04348, 08696, 1313, 1773, 2254, 2764, 3308, 3892, 5211, 5963, 6791, 7708, 873, 9876, 117, 431, 846, 411, 771, 196, 706, 04167, 1258, 1696, 2155, 2638, 3152, 3701, 4292, 4933, 6393, 7233, 8164, 036, 167, 315, 678, 902, 162, 466, 824, 246, 751, 1207, 1626, 2064, 2523, 301, 3528, 4084, 4683, 5332, 6039, 6814, 7667, 861, 9661, 216, 366, 536, 731, 956, 217, 876, 03846, 116, 1562, 198, 2418, 288, 3371, 3895, 4458, 5065, 5723, 6441, 7227, 8091, 011, 415, 587, 783, 927, 03704, 07407, 1117, 1503, 1903, 2322, 2762, 3228, 3724, 4254, 4824, 5439, 6107, 6835, 7632, 8509, 9479, 056, 176, 311, 464, 637, 834, 061, spread, sheet, either, currently, holding, gamble, former, avoidance, doubt, represented, beginning, concludes, 562, 949, 953, 421, 312, 989, 816, 513, 0813295, allocating, covers, guarantees, pick, hit, otherwise, broke, explained, ensemble, strategies, matching, scott, suppose, betting, amount, odds, investment, guarantee, choosing, passively, exposed, slings, arrows, outrageous, fortune, potentially, earn, minimum, artificial, ends, special, process, required, cover, financial, bonds, whose, redemption, share, affected, drives, price, selling, exercising, exercised, trade, money, general, ekström, wanntorp, 2009, american, option, options, pinning, coupon, bond, stas, volkov, fun, construction, throws, loop, neutralize, shouldn, cut, losses, wrong, quitting, knows, coming, chance, exploit, eke, profit, following, pays, fines, want, returned, maximizing, discusses, gambling, 2006, nigel, million, conjecture, 002, change, powerful, improving, shockingly, careful, individual, made, build, providing, verified, these, limiting, treated, stage, about, draws, finite, goal, fluctuated, likely, aspects, importance, certain, certainty, finished, timothy, falcon, asks, drawing, approaches, others, increasing, theory, substack, patreon, blog, support, link, popups, popovers, transclusions, collapsible, sections, tablesorting, image, zooming, enable, sidenotes, website, features, warning, content,

Text of the page (random words):
ire game is that the p of good bad is itself dependent on the state the more of the good cards that get used up the higher the probability of a bad draw and vice versa so the probabilities are constantly changing to push back towards the middle the ev being higher than the correct ev is a hint as to the error if the p remains at 0 5 the entire game perhaps because we were sampling with replacement instead then the value will be higher because there will be no reversion from using up the good cards we can always ride good luck still higher my slow but easy r implementation library memoise f function good bad winnings if good 0 return winnings else if bad 0 return winnings good else return good good bad mv good 1 bad winnings 1 1 good good bad mv good bad 1 winnings 1 mf memoise f v function good bad winnings returns c winnings mf good bad winnings max returns mv memoise v estimate value of all possible balanced games 0 26 sapply 0 26 function t mv t t 0 grows as 𝒪 cards 1 0 000000000 0 500000000 0 666666667 0 850000000 1 000000000 1 119047619 1 229437229 1 335372960 1 434110334 1 524701769 1 607227911 1 687397226 1 765411833 14 1 840809473 1 913207824 1 982391061 2 048281891 2 112213746 2 174760756 2 235998731 2 295858627 2 354246421 2 411081973 2 466309395 2 520043731 2 572700079 27 2 624475549 this is an easy enough problem that with no further optimization the code runs near instantly all the way up to 143 cards worth 6 21519192 where it hits a stack limit we confirm that han zheng s value 2 62 is correct simulation check the value function lets us play an optimal game by simply comparing the value of the two possible choices quit and keep playing and doing the choice with the larger value this means we can double check with a simulation that the optimal policy does in fact attain the claimed value of the specified game 26 26 0 simulategame function good bad winnings if good 0 bad 0 return winnings else quitvalue winnings playvalue mv good bad winnings if quitvalue playvalue return winnings else if runif 1 good good bad good 0 simulategame good 1 bad winnings 1 else if bad 0 simulategame good bad 1 winnings 1 else simulategame good bad winnings mv 26 26 0 1 2 62447555 mean replicate 10000000 simulategame 26 26 0 1 2 6243913 simulating 49 sample games we can see how while the optimal strategy looks fairly risky it usually wins in the end simulation of winnings over a sample of 49 games of 26 26 using the optimal stopping strategy one can see the implicit decision boundary where trajectories stop simulategamelog function cards ith df data frame id ith rounds seq 1 cards 2 winnings rep na cards 2 rounds 0 good cards bad cards winning 0 playing true while playing if good 0 bad 0 playing false else playvalue mv good bad winning if winning playvalue playing false else if runif 1 good good bad good 0 winning winning 1 good good 1 else if bad 0 winning winning 1 bad bad 1 df rounds rounds rounds rounds rounds 1 df winnings rounds winning return df df data frame for i in 0 48 df rbind df simulategamelog 26 i library ggplot2 p qplot x rounds y winnings data df p facet_wrap id geom_line aes x rounds y winnings size 3 xlab card draw ylab winnings theme legend position none coord_cartesian ylim c 7 5 geom_point size i 6 theme strip background element_blank strip text x element_blank neat feepingcreature independently wrote a faster version written in his custom d like programming language neat module fourteen import std math import std stdio struct state float cash int red black float pred return red 1 0f red black float pblack return black 1 0f red black float expectedvalue statecache cache string key cash red black if cache table has key return cache table key base case if red 0 black 0 return 0 mut float playpayoff 0 if red 0 playpayoff pred state cash 1 red 1 black expectedvalue cache if black 0 playpayoff pblack state cash 1 red black 1 expectedvalue cache cache table key max cash playpayoff return cache table key class statecache float string table this void main float result state cash 0 red 26 black 26 expectedvalue new statecache print expected return of game result this version also confirms han zheng s value neat array feepingcreature notes that this is slower than it needs to be and can be converted from the hashmap memoization to a faster flat array especially if like zheng s spreadsheet one stops tracking winnings and only tracks good bad so the value function is reporting the marginal value of the state feepingcreature s faster winnings free array based version with a monte carlo simulation to double check results module fourteen macro import std macro listcomprehension import std math import std stdio extern c int rand struct state int red black float pred return red 1 0f red black float pblack return black 1 0f red black class dpcalc float nothing table this table new typeof table 27 27 float expectedvalue state state with state int key red 27 black table key case float f return f nothing base case if red 0 black 0 return 0 mut float playpayoff 0 if red 0 playpayoff pred expectedvalue state red 1 black 1 if black 0 playpayoff pblack expectedvalue state red black 1 1 float payoff max 0 0f playpayoff table key payoff return payoff class policy dpcalc dpcalc this this dpcalc play leave decide state state auto payoff dpcalc expectedvalue state if payoff 0 return play else return leave void main auto dpcalc new dpcalc auto policy new policy dpcalc float expected dpcalc expectedvalue state red 26 black 26 print expected return of game expected mut double sum int count montecarlo mut red black cards for _ in 0 26 cards red for _ in 0 26 cards black for i in 0 10_000_000 mut float cash 0 mut auto state state red 26 black 26 cards shuffle for card in cards auto action policy decide state if action leave break if card red cash 1 state red 1 else cash 1 state black 1 montecarlo sum cash montecarlo count 1 if i 10_000 0 print montecarlo sum count print monte carlo montecarlo sum count over montecarlo count games void shuffle t mut t array for i in 0 array length 1 auto j i rand array length i auto tmp array i array i array j array j tmp bottom up dp the top down dynamic programming is the simplest easiest to understand one just sets up the logical dependency enables memoization and requests the desired value it comes with a performance drawback of taking 𝒪 l 2 time space because it must define evaluate and store every possible state 𝑆 tuple value as it might be requested at any time so even a close to the metal implementation will struggle if you ask for the value of games with thousands of cards it will take a long time to run and use possibly tens of gigabytes of memory but like in the kelly coin flip problem we can note that most 𝑆 will not be requested ever again at least if the user isn t requesting a bunch of values eg at a repl because the game has a continually shrinking as cards get used up tree structure and that evaluation follows a sort of wave or ripple back from the root final states like 0 0 or 10 0 to the initial 26 26 since the evaluation won t revisit them they can be discarded immediately if we start at the root final states then evaluate the set of states before them now that we know the next state throw out the roots and move back 1 level to evaluate the state of states before those and so on and so forth this bottom up evaluation will still be 𝒪 l 2 time the constant factor can be optimized by further changing the evaluation pattern but only 𝒪 l linear space so if one was patient one could evaluate up to millions of cards probably in a reasonable time like a few days i have evaluated up to l 22 974 available as a text file haskell nshepperd implementation in haskell using data vector import data decimal import data ratio import data vector import qualified data vector as v solve fractional a ord a int int a solve r b go r b where tab v generate 27 r v generate 27 b go r b look r b tab v r v b go 0 b 0 stop when there s only black cards go r 0 fromintegral r take all the remaining red cards go r b max 0 fromintegral r fromintegral r b look r 1 b 1 fromintegral b fromintegral r b look r b 1 1 solve 26 26 rational 41984711742427 15997372030584 41984711742427 15997372030584 2 624475548993925 c feepingcreature port of nshepperd s haskell version compiled with gcc gcc wall ofast march native o problem14 lm problem14 c include stdio h include stdlib h include math h define at r b tab r 2 blacks 1 b float calc int reds int blacks int r int b float tab return r 0 b r fmax 0 r 1 0 r b at r 1 b 1 b 1 0 r b at r b 1 1 int main for int i 0 i 100000 i int reds i blacks i float tab malloc sizeof float 2 blacks 1 for int r 0 r reds r for int b 0 b blacks b at r b calc reds blacks r b tab printf f n at reds blacks return 0 0 000000 0 500000 0 666667 0 850000 1 000000 1 119048 1 229437 1 335373 1 434110 1 524702 1 607228 1 687397 1 765412 1 840810 1 913208 1 982391 2 048282 2 112214 2 174761 2 235999 2 295858 2 354246 2 411082 2 466309 2 520043 2 572700 2 624475 and feepingcreature s code golfed version using lambdas to show off module fourteen2 import std math float solve auto tab new float 27 27 auto look r b tab r 27 b auto go r b 0 if r 0 else r if b 0 else max 0 0 f r 1 0 f r b look r 1 b 1 b 1 0 f r b look r b 1 1 for r in 0 27 for b in 0 27 tab r 27 b go r b return look 26 26 void main print solve c array c array version by khoth note not 𝒪 l space because the optimization was not implemented include stdio h include stdlib h include time h define max x y x y x y float outcome 27 27 0 black 1 red 1 int cash int rem_black int rem_red return rem_red rem_black void fill_array void for int rem_black 0 rem_black 26 rem_black for int rem_red 0 rem_red 26 rem_red if rem_red 0 outcome rem_black rem_red 0 else if rem_black 0 outcome rem_black rem_red rem_red else float p float rem_black float rem_black rem_red float value_if_stop cash rem_black rem_red float value_if_go p outcome rem_black 1 rem_red 1 p outcome rem_black rem_red 1 outcome rem_black rem_red max value_if_stop value_if_go int should_stop int rem_black int rem_red return cash rem_black rem_red outcome rem_black rem_red 0 limit int rand_lim int limit int divisor rand_max limit int retval do retval rand divisor while retval limit return retval int draw int rem_black int rem_red int ret rem_black rand_lim rem_black rem_red return ret int run_game void int rem_black 26 int rem_red 26 while rem_black rem_red if should_stop rem_black rem_red break if draw rem_black rem_red rem_black else rem_red return cash rem_black rem_red int main int argc char argv srand time null shitty but who cares fill_array printf value f n outcome 26 26 if argc 2 int iters atoi argv 1 int total_return 0 for int i 0 i iters i total_return run_game printf avg return f n float total_return iters c diagonal bottom up the need to calculate all the possible states makes it hard to get around the asymptotic in bottom up evaluation but the constant factors can still be improved diagonal traversal pattern illustration by feepingcreature in particular the evaluation is single threaded with every calculation depending on the previous one this means that the cpu cannot run the arithmetic in parallel nor can the compiler simd vectorize it to use avx instructions like vmaxp we forfeit much of the performance of our cpu core this is despite the problem looking reasonably parallel lots of states are distant and don t seem like they ought to depend on each other what they actually depend on are just a few prior states which we might call diagonal states so because the loops to only refer to up and left states many of the later states can be computed independently of each other in one big parallel batch as long as the right subset of later states is chosen moving on the diagonal feepingcreature s diagonal evaluation include stdbool h include stdio h include stdlib h include math h define fp double fp calc int cards int r int b int dia bool ascent fp prevdia int main int cards 200000 fp prevdia malloc sizeof fp cards 1 fp curdia malloc sizeof fp cards 1 visualization aid b 0 1 2 r 0 0 1 2 1 0 1 1 2 0 0 0 ascent for int row 0 row cards row for int dia 0 dia row dia int r row dia int b dia curdia dia calc cards r b dia true prevdia fp tmp curdia curdia prevdia prevdia tmp descent for int col 1 col cards col for int dia 0 dia cards col dia int r cards dia int b col dia curdia dia calc cards r b dia false prevdia fp tmp curdia curdia prevdia prevdia tmp printf expected value is f n prevdia 0 return 0 fp calc int cards int r int b int dia bool ascent fp prevdia if r 0 return 0 else if b 0 return r else red drawn int upindex ascent dia dia 1 black drawn int leftindex ascent dia 1 dia fp pred fp r r b fp pblack 1 pred fp payoff pred prevdia upindex 1 pblack prevdia leftindex 1 if payoff 0 return payoff return 0 the initial version ran substantially faster when compiled with clang clang ofast march native fourteen c lm o fourteen rather than gcc feepingcreature s laptop got 6s vs 17s for evaluating 100 000 100 000 due to poor gcc auto vectorization as reported by fopt info vec all this second version should vectorize on both clang gcc 4 6s vs 5 8s and can calculate into the millions without a problem probably it would be even faster on a cpu with avx 512 as it could vectorize more the difference in performance between the simplest easiest r version which took a bad programmer myself minutes to write the first version but takes seconds to evaluate tops out at 143 and this optimized c implementation which took multiple versions hours to write by good programmers feepingcreature with advice from khoth nshepperd but runs in milliseconds tops out at somewhere between millions and however long you care to wait illustrates how much potential for optimization there can be your computer may be faster than you think parallel further parallelization would require threads or processes and has the problem that the overhead of creating communicating is vastly greater than the actual calculations here of some addition division multiplication operations anything involving ipc or synchronization on a modern multi core computer can be safely assumed to cost the equivalent of thousands or hundreds of thousands of arithmetic operations for card counts like 52 i don t think any parallelism above the cpu core level is worthwhile it would only work on far larger problems diagonalization a spinlock is one way to lock for synchronization and for large card counts like l 100 000 there may be enough work when split up to keep cpu cores busy a spinlock for one thread when it hits a value it needs but which hasn t been computed yet will check constantly and as soon as the other thread finishes computing the necessary value will grab it and resume its own computation with as little delay as possible feepingcreature provides a parallelized version of the diagonal code which tries to split the pending diagonal of 100 000 into separate parts...