CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Game complexity - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"c63dd850-572d-4b9f-a75a-0e28ce85600f","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Game_complexity","wgTitle":"Game complexity","wgCurRevisionId":1246673284,"wgRevisionId":1246673284,"wgArticleId":317419,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1: long volume value","CS1 maint: multiple names: authors list","Articles with short description","Short description matches Wikidata","Use mdy dates from May 2023","Combinatorial game theory","Game theory"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Game_complexity","wgRelevantArticleId":317419,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q903738","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.tablesorter.styles":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","jquery.tablesorter","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin", "ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cjquery.tablesorter.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Game complexity - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Game_complexity"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Game_complexity&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Game_complexity"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Game_complexity rootpage-Game_complexity skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Game+complexity" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Game+complexity" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Game+complexity" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Game+complexity" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Measures_of_game_complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Measures_of_game_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Measures of game complexity</span> </div> </a> <button aria-controls="toc-Measures_of_game_complexity-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Measures of game complexity subsection</span> </button> <ul id="toc-Measures_of_game_complexity-sublist" class="vector-toc-list"> <li id="toc-State-space_complexity" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#State-space_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>State-space complexity</span> </div> </a> <ul id="toc-State-space_complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Game_tree_size" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Game_tree_size"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Game tree size</span> </div> </a> <ul id="toc-Game_tree_size-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Decision_trees" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Decision_trees"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Decision trees</span> </div> </a> <ul id="toc-Decision_trees-sublist" class="vector-toc-list"> <li id="toc-Decision_complexity" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Decision_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3.1</span> <span>Decision complexity</span> </div> </a> <ul id="toc-Decision_complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Game-tree_complexity" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Game-tree_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3.2</span> <span>Game-tree complexity</span> </div> </a> <ul id="toc-Game-tree_complexity-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Computational_complexity" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Computational_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.4</span> <span>Computational complexity</span> </div> </a> <ul id="toc-Computational_complexity-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Example:_tic-tac-toe_(noughts_and_crosses)" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Example:_tic-tac-toe_(noughts_and_crosses)"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Example: tic-tac-toe (noughts and crosses)</span> </div> </a> <ul id="toc-Example:_tic-tac-toe_(noughts_and_crosses)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complexities_of_some_well-known_games" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complexities_of_some_well-known_games"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Complexities of some well-known games</span> </div> </a> <ul id="toc-Complexities_of_some_well-known_games-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Game complexity</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 7 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-7" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">7 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Spiel-Komplexit%C3%A4t" title="Spiel-Komplexität – German" lang="de" hreflang="de" data-title="Spiel-Komplexität" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Complejidad_en_los_juegos" title="Complejidad en los juegos – Spanish" lang="es" hreflang="es" data-title="Complejidad en los juegos" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%BE%DB%8C%DA%86%DB%8C%D8%AF%DA%AF%DB%8C_%D8%A8%D8%A7%D8%B2%DB%8C" title="پیچیدگی بازی – Persian" lang="fa" hreflang="fa" data-title="پیچیدگی بازی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B2%8C%EC%9E%84_%EB%B3%B5%EC%9E%A1%EB%8F%84" title="게임 복잡도 – Korean" lang="ko" hreflang="ko" data-title="게임 복잡도" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Complexidade_de_jogos" title="Complexidade de jogos – Portuguese" lang="pt" hreflang="pt" data-title="Complexidade de jogos" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%8D%9A%E5%BC%88%E8%A4%87%E9%9B%9C%E5%BA%A6" title="博弈複雜度 – Cantonese" lang="yue" hreflang="yue" data-title="博弈複雜度" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%8D%9A%E5%BC%88%E5%A4%8D%E6%9D%82%E5%BA%A6" title="博弈复杂度 – Chinese" lang="zh" hreflang="zh" data-title="博弈复杂度" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q903738#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Game_complexity" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Game_complexity" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Game_complexity"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Game_complexity&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Game_complexity&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Game_complexity"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Game_complexity&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Game_complexity&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Game_complexity" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Game_complexity" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Game_complexity&oldid=1246673284" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Game_complexity&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Game_complexity&id=1246673284&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FGame_complexity"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FGame_complexity"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Game_complexity&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Game_complexity&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q903738" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Notion in combinatorial game theory</div> <p class="mw-empty-elt"> </p><p><a href="/wiki/Combinatorial_game_theory" title="Combinatorial game theory">Combinatorial game theory</a> <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">measures</a> <b>game complexity</b> in several ways: </p> <ol><li>State-space complexity (the number of legal game positions from the initial position),</li> <li>Game tree size (total number of possible games),</li> <li>Decision complexity (number of leaf nodes in the smallest decision tree for initial position),</li> <li>Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position),</li> <li>Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).</li></ol> <p>These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Measures_of_game_complexity">Measures of game complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=1" title="Edit section: Measures of game complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="State-space_complexity">State-space complexity</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=2" title="Edit section: State-space complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <b>state-space complexity</b> of a game is the number of legal game positions reachable from the initial position of the game.<sup id="cite_ref-Allis1994_1-0" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>When this is too hard to calculate, an <a href="/wiki/Upper_bound" class="mw-redirect" title="Upper bound">upper bound</a> can often be computed by also counting (some) illegal positions, meaning positions that can never arise in the course of a game. </p> <div class="mw-heading mw-heading3"><h3 id="Game_tree_size">Game tree size</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=3" title="Edit section: Game tree size"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <b>game tree size</b> is the total number of possible games that can be played: the number of leaf nodes in the <a href="/wiki/Game_tree" title="Game tree">game tree</a> rooted at the game's initial position. </p><p>The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a <a href="/wiki/Tic-tac-toe" title="Tic-tac-toe">tic-tac-toe</a> game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable. </p><p>For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite. </p> <div class="mw-heading mw-heading3"><h3 id="Decision_trees">Decision trees</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=4" title="Edit section: Decision trees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The next two measures use the idea of a <i><a href="/wiki/Decision_tree" title="Decision tree">decision tree</a></i>, which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.) </p> <div class="mw-heading mw-heading4"><h4 id="Decision_complexity">Decision complexity</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=5" title="Edit section: Decision complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Decision complexity</b> of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position. </p> <div class="mw-heading mw-heading4"><h4 id="Game-tree_complexity">Game-tree complexity</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=6" title="Edit section: Game-tree complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <b>game-tree complexity</b> of a game is the number of leaf nodes in the smallest <i>full-width</i> decision tree that establishes the value of the initial position.<sup id="cite_ref-Allis1994_1-1" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> A full-width tree includes all nodes at each depth. </p><p>This is an estimate of the number of positions one would have to evaluate in a <a href="/wiki/Minimax" title="Minimax">minimax</a> search to determine the value of the initial position. </p><p>It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by raising the game's average <a href="/wiki/Branching_factor" title="Branching factor">branching factor</a> <i>b</i> to the power of the number of <a href="/wiki/Ply_(chess)" class="mw-redirect" title="Ply (chess)">plies</a> <i>d</i> in an average game, or: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle GTC\geq b^{d}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mi>T</mi> <mi>C</mi> <mo>≥</mo> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle GTC\geq b^{d}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/508901e10b198208ca82966213e9c6b198f2ea0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.417ex; height:2.843ex;" alt="{\displaystyle GTC\geq b^{d}}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Computational_complexity">Computational complexity</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=7" title="Edit section: Computational complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <b><a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity</a></b> of a game describes the <a href="/wiki/Asymptotic_analysis" title="Asymptotic analysis">asymptotic</a> difficulty of a game as it grows arbitrarily large, expressed in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a> or as membership in a <a href="/wiki/Complexity_class" title="Complexity class">complexity class</a>. This concept doesn't apply to particular games, but rather to games that have been <a href="/wiki/Generalized_game" title="Generalized game">generalized</a> so they can be made arbitrarily large, typically by playing them on an <i>n</i>-by-<i>n</i> board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.) </p><p>The asymptotic complexity is defined by the most efficient (in terms of whatever <a href="/wiki/Computational_resource" title="Computational resource">computational resource</a> one is considering) algorithm for solving the game; the most common complexity measure (<a href="/wiki/Computation_time" class="mw-redirect" title="Computation time">computation time</a>) is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of <a href="/wiki/DSPACE" title="DSPACE">space</a> or <a href="/wiki/Computer_memory" title="Computer memory">computer memory</a> used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be <a href="/wiki/PSPACE-hard" class="mw-redirect" title="PSPACE-hard">PSPACE-hard</a>, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear). </p> <ul><li>The <a href="/wiki/Depth-first_search" title="Depth-first search">depth-first</a> <a href="/wiki/Minimax_strategy" class="mw-redirect" title="Minimax strategy">minimax strategy</a> will use <a href="/wiki/Computation_time" class="mw-redirect" title="Computation time">computation time</a> proportional to the game's tree-complexity, since it must explore the whole tree, and an amount of memory polynomial in the logarithm of the tree-complexity, since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is precisely the tree-complexity.</li> <li><a href="/wiki/Backward_induction" title="Backward induction">Backward induction</a> will use both memory and time proportional to the state-space complexity as it must compute and record the correct move for each possible position.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Example:_tic-tac-toe_(noughts_and_crosses)"><span id="Example:_tic-tac-toe_.28noughts_and_crosses.29"></span>Example: tic-tac-toe (noughts and crosses)</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=8" title="Edit section: Example: tic-tac-toe (noughts and crosses)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For <a href="/wiki/Tic-tac-toe" title="Tic-tac-toe">tic-tac-toe</a>, a simple upper bound for the size of the state space is 3<sup>9</sup> = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions. </p><p>To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games. </p><p>The computational complexity of tic-tac-toe depends on how it is <a href="/wiki/Generalized_game" title="Generalized game">generalized</a>. A natural generalization is to <a href="/wiki/M,n,k-game" title="M,n,k-game"><i>m</i>,<i>n</i>,<i>k</i>-games</a>: played on an <i>m</i> by <i>n</i> board with winner being the first player to get <i>k</i> in a row. It is immediately clear that this game can be solved in <a href="/wiki/DSPACE" title="DSPACE">DSPACE</a>(<i>mn</i>) by searching the entire game tree. This places it in the important complexity class <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a>. With some more work it can be shown to be <a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a>.<sup id="cite_ref-Reisch1980b_4-0" class="reference"><a href="#cite_note-Reisch1980b-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Complexities_of_some_well-known_games">Complexities of some well-known games</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=9" title="Edit section: Complexities of some well-known games"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Due to the large size of game complexities, this table gives the ceiling of their <a href="/wiki/Logarithm" title="Logarithm">logarithm</a> to base 10. (In other words, the number of digits). All of the following numbers should be considered with caution: seemingly-minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the numbers shown. </p><p>Note: ordered by game tree size </p> <style data-mw-deduplicate="TemplateStyles:r1253789634">@media screen{.mw-parser-output .sticky-header>thead>tr:first-child,.mw-parser-output .sticky-header>caption+tbody>tr:first-child,.mw-parser-output .sticky-header>tbody:first-child>tr:first-child,.mw-parser-output .sticky-header-multi>thead{position:sticky;top:0;z-index:10}.mw-parser-output .sticky-header:not(.wikitable),.mw-parser-output .sticky-header-multi:not(.wikitable){background-color:white}.mw-parser-output .sticky-header:not(.wikitable)>*,.mw-parser-output .sticky-header:not(.wikitable)>thead>tr:first-child,.mw-parser-output .sticky-header:not(.wikitable)>caption+tbody>tr:first-child,.mw-parser-output .sticky-header:not(.wikitable)>tbody:first-child>tr:first-child,.mw-parser-output .sticky-header-multi:not(.wikitable)>thead,.mw-parser-output .sticky-header-multi>thead{background-color:inherit}.mw-parser-output .sticky-header.wikitable,.mw-parser-output .sticky-header-multi.wikitable{border-collapse:separate;border-spacing:0;border-width:0 1px 1px 0}.mw-parser-output .sticky-header.wikitable td,.mw-parser-output .sticky-header.wikitable th,.mw-parser-output .sticky-header-multi.wikitable td,.mw-parser-output .sticky-header-multi.wikitable th{border-width:1px 0 0 1px}body.skin-timeless .mw-parser-output .sticky-header.wikitable,body.skin-timeless .mw-parser-output .sticky-header-multi.wikitable{border-bottom-width:0.2em;padding:0}.mw-parser-output .sticky-header.static-row-numbers.wikitable tr::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable tr::before{border-left-width:1px}.mw-parser-output .sticky-header.static-row-numbers.wikitable>thead>tr:first-child::before,.mw-parser-output .sticky-header.static-row-numbers.wikitable>caption+tbody>tr:first-child::before,.mw-parser-output .sticky-header.static-row-numbers.wikitable>tbody:first-child>tr:first-child::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable>thead>tr:first-child::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable>caption+tbody>tr:first-child::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable>tbody:first-child>tr:first-child::before,.mw-parser-output .sticky-header.static-row-numbers.wikitable .sortbottom::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable .sortbottom::before{border-top-width:1px}.mw-parser-output .sticky-header.static-row-numbers.wikitable .sortbottom~.sortbottom::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable .sortbottom~.sortbottom::before{border-top-width:0}.mw-parser-output .sticky-header.static-row-numbers.wikitable>tbody>tr:not(.static-row-header)::before,.mw-parser-output .sticky-header-multi.static-row-numbers.wikitable>tbody>tr:not(.static-row-header)::before{border-bottom-width:0!important;border-right-width:0!important}body.skin-timeless .mw-parser-output .content-table-scrollbar,body.skin-timeless .mw-parser-output .overflowed,body.skin-timeless .mw-parser-output .overflowed .content-table{overflow:visible}body.skin-timeless .mw-parser-output .scroll-right.overflowed .content-table-right{box-shadow:none;border-left:none}}@media screen and (min-width:1120px){body.vector-sticky-header-visible .mw-parser-output .sticky-header>thead>tr:first-child,body.vector-sticky-header-visible .mw-parser-output .sticky-header>caption+tbody>tr:first-child,body.vector-sticky-header-visible .mw-parser-output .sticky-header>tbody:first-child>tr:first-child,body.vector-sticky-header-visible .mw-parser-output .sticky-header-multi>thead{top:3.125rem}}@media screen and (min-width:851px){body.skin-timeless .mw-parser-output .sticky-header>thead>tr:first-child,body.skin-timeless .mw-parser-output .sticky-header>caption+tbody>tr:first-child,body.skin-timeless .mw-parser-output .sticky-header>tbody:first-child>tr:first-child,body.skin-timeless .mw-parser-output .sticky-header-multi>thead{top:3.51em}}@media screen and (max-width:639px){body.skin-minerva .mw-parser-output .sticky-header,body.skin-minerva .mw-parser-output .sticky-header-multi,body.skin-monobook .mw-parser-output .sticky-header,body.skin-monobook .mw-parser-output .sticky-header-multi,body.skin-vector-legacy .mw-parser-output .sticky-header,body.skin-vector-legacy .mw-parser-output .sticky-header-multi,body.skin-vector-2022 .mw-parser-output .sticky-header,body.skin-vector-2022 .mw-parser-output .sticky-header-multi{display:table}body.skin-minerva .mw-parser-output .sticky-header>caption,body.skin-minerva .mw-parser-output .sticky-header-multi>caption{display:table-caption}}@media screen{html.skin-theme-clientpref-night body.skin-minerva .mw-parser-output .sticky-header-multi.wikitable{background-color:#101418}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os body.skin-minerva .mw-parser-output .sticky-header-multi.wikitable{background-color:#101418}}</style> <table class="wikitable sortable sticky-header"> <tbody><tr> <th>Game </th> <th>Board size <p>(positions) </p> </th> <th>State-space complexity <p>(as <a href="/wiki/Logarithm" title="Logarithm">log</a> to base 10) </p> </th> <th>Game-tree complexity <p>(as <a href="/wiki/Logarithm" title="Logarithm">log</a> to base 10) </p> </th> <th>Average game length <p>(<a href="/wiki/Ply_(game_theory)" title="Ply (game theory)">plies</a>) </p> </th> <th>Branching factor </th> <th>Ref </th> <th><a href="/wiki/Complexity_class" title="Complexity class">Complexity class</a> of suitable <a href="/wiki/Generalized_game" title="Generalized game">generalized game</a> </th></tr> <tr> <td><a href="/wiki/Tic-tac-toe" title="Tic-tac-toe">Tic-tac-toe</a> </td> <td style="text-align:right;">9 </td> <td style="text-align:right;">3 </td> <td style="text-align:right;">5 </td> <td style="text-align:right;">9 </td> <td style="text-align:right;">4 </td> <td style="text-align:right;"> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-Reisch1980_5-0" class="reference"><a href="#cite_note-Reisch1980-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Sim_(pencil_game)" class="mw-redirect" title="Sim (pencil game)">Sim</a> </td> <td style="text-align:right;">15 </td> <td style="text-align:right;">3 </td> <td style="text-align:right;">8 </td> <td style="text-align:right;">14 </td> <td style="text-align:right;">3.7 </td> <td style="text-align:right;"> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Pentomino" title="Pentomino">Pentominoes</a> </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">12 </td> <td style="text-align:right;">18 </td> <td style="text-align:right;">10 </td> <td style="text-align:right;">75 </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-0" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a> </td></tr> <tr> <td><a href="/wiki/Kalah" title="Kalah">Kalah</a><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;">14 </td> <td style="text-align:right;">13 </td> <td style="text-align:right;">18 </td> <td style="text-align:right;"> </td> <td style="text-align:right;">50 </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-1" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td> <td>Generalization is unclear </td></tr> <tr> <td><a href="/wiki/Connect_Four" title="Connect Four">Connect Four</a> </td> <td style="text-align:right;">42 </td> <td style="text-align:right;">13 </td> <td style="text-align:right;">21 </td> <td style="text-align:right;">36 </td> <td style="text-align:right;">4 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-2" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a> </td></tr> <tr> <td><a href="/wiki/Domineering" title="Domineering">Domineering</a> (8 × 8) </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">15 </td> <td style="text-align:right;">27 </td> <td style="text-align:right;">30 </td> <td style="text-align:right;">8 </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-2" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a>; in <a href="/wiki/P_(complexity_class)" class="mw-redirect" title="P (complexity class)">P</a> for certain dimensions<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Congkak" class="mw-redirect" title="Congkak">Congkak</a> </td> <td style="text-align:right;">14 </td> <td style="text-align:right;">15 </td> <td style="text-align:right;">33 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-3" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td> <td> </td></tr> <tr> <td><a href="/wiki/English_draughts" title="English draughts">English draughts (8x8) (checkers)</a> </td> <td style="text-align:right;">32 </td> <td style="text-align:right;">20 or 18 </td> <td style="text-align:right;">40 </td> <td style="text-align:right;">70 </td> <td style="text-align:right;">2.8 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-3" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a><sup id="cite_ref-robson1984_14-0" class="reference"><a href="#cite_note-robson1984-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Oware" title="Oware">Awari</a><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;">12 </td> <td style="text-align:right;">12 </td> <td style="text-align:right;">32 </td> <td style="text-align:right;">60 </td> <td style="text-align:right;">3.5 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-4" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td>Generalization is unclear </td></tr> <tr> <td><a href="/wiki/Qubic" class="mw-redirect" title="Qubic">Qubic</a> </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">30 </td> <td style="text-align:right;">34 </td> <td style="text-align:right;">20 </td> <td style="text-align:right;">54.2 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-5" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-Reisch1980_5-1" class="reference"><a href="#cite_note-Reisch1980-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Computer_bridge" title="Computer bridge">Double dummy bridge</a><sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>nb 1<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;">(52) </td> <td style="text-align:right;"><17 </td> <td style="text-align:right;"><40 </td> <td style="text-align:right;">52 </td> <td style="text-align:right;">5.6 </td> <td> </td> <td align="left">PSPACE-complete<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Fanorona" title="Fanorona">Fanorona</a> </td> <td style="text-align:right;">45 </td> <td style="text-align:right;">21 </td> <td style="text-align:right;">46 </td> <td style="text-align:right;">44 </td> <td style="text-align:right;">11 </td> <td style="text-align:right;"><sup id="cite_ref-Schadd2008_18-0" class="reference"><a href="#cite_note-Schadd2008-18"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a> </td></tr> <tr> <td><a href="/wiki/Nine_men%27s_morris" title="Nine men's morris">Nine men's morris</a> </td> <td style="text-align:right;">24 </td> <td style="text-align:right;">10 </td> <td style="text-align:right;">50 </td> <td style="text-align:right;">50 </td> <td style="text-align:right;">10 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-6" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a> </td></tr> <tr> <td><a href="/wiki/Tablut" class="mw-redirect" title="Tablut">Tablut</a> </td> <td style="text-align:right;">81 </td> <td style="text-align:right;">27 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"><sup id="cite_ref-Galassi2018_19-0" class="reference"><a href="#cite_note-Galassi2018-19"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </td> <td> </td></tr> <tr> <td><a href="/wiki/International_draughts" title="International draughts">International draughts (10x10)</a> </td> <td style="text-align:right;">50 </td> <td style="text-align:right;">30 </td> <td style="text-align:right;">54 </td> <td style="text-align:right;">90 </td> <td style="text-align:right;">4 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-7" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a><sup id="cite_ref-robson1984_14-1" class="reference"><a href="#cite_note-robson1984-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Chinese_checkers" title="Chinese checkers">Chinese checkers</a> (2 sets) </td> <td style="text-align:right;">121 </td> <td style="text-align:right;">23 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;">180 </td> <td style="text-align:right;"><sup id="cite_ref-Bell_Halma_20-0" class="reference"><a href="#cite_note-Bell_Halma-20"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a>-complete <sup id="cite_ref-pebble_21-0" class="reference"><a href="#cite_note-pebble-21"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Chinese_checkers" title="Chinese checkers">Chinese checkers</a> (6 sets) </td> <td style="text-align:right;">121 </td> <td style="text-align:right;">78 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;">600 </td> <td style="text-align:right;"><sup id="cite_ref-Bell_Halma_20-1" class="reference"><a href="#cite_note-Bell_Halma-20"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a>-complete <sup id="cite_ref-pebble_21-1" class="reference"><a href="#cite_note-pebble-21"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Reversi" title="Reversi">Reversi</a> (Othello) </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">28 </td> <td style="text-align:right;">58 </td> <td style="text-align:right;">58 </td> <td style="text-align:right;">10 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-8" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>OnTop (2p base game) </td> <td style="text-align:right;">72 </td> <td style="text-align:right;">88 </td> <td style="text-align:right;">62 </td> <td style="text-align:right;">31 </td> <td style="text-align:right;">23.77 </td> <td style="text-align:right;"><sup id="cite_ref-OnTopComputer_23-0" class="reference"><a href="#cite_note-OnTopComputer-23"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup> </td> <td> </td></tr> <tr> <td><a href="/wiki/Lines_of_Action" title="Lines of Action">Lines of Action</a> </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">23 </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">44 </td> <td style="text-align:right;">29 </td> <td style="text-align:right;"><sup id="cite_ref-Winands2004_24-0" class="reference"><a href="#cite_note-Winands2004-24"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a> </td></tr> <tr> <td><a href="/wiki/Gomoku" title="Gomoku">Gomoku</a> (15x15, freestyle) </td> <td style="text-align:right;">225 </td> <td style="text-align:right;">105 </td> <td style="text-align:right;">70 </td> <td style="text-align:right;">30 </td> <td style="text-align:right;">210 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-9" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-Reisch1980_5-2" class="reference"><a href="#cite_note-Reisch1980-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Hex_(board_game)" title="Hex (board game)">Hex (11x11)</a> </td> <td style="text-align:right;">121 </td> <td style="text-align:right;">57 </td> <td style="text-align:right;">98 </td> <td style="text-align:right;">50 </td> <td style="text-align:right;">96 </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-4" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-Reisch1980_5-3" class="reference"><a href="#cite_note-Reisch1980-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Chess" title="Chess">Chess</a> </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">44 </td> <td style="text-align:right;">123 </td> <td style="text-align:right;">70 </td> <td style="text-align:right;">35 </td> <td style="text-align:right;"><sup id="cite_ref-Shannon1950_25-0" class="reference"><a href="#cite_note-Shannon1950-25"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a> (without <a href="/wiki/Fifty-move_rule" title="Fifty-move rule">50-move drawing rule</a>)<sup id="cite_ref-Fraenkel1981_26-0" class="reference"><a href="#cite_note-Fraenkel1981-26"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Bejeweled_(video_game)" title="Bejeweled (video game)">Bejeweled</a> and <a href="/wiki/Candy_Crush_Saga" title="Candy Crush Saga">Candy Crush</a> (8x8) </td> <td style="text-align:right;">64 </td> <td style="text-align:right;"><50 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;">70 </td> <td style="text-align:right;"><sup id="cite_ref-Gual14_27-0" class="reference"><a href="#cite_note-Gual14-27"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> </td></tr> <tr> <td><a href="/wiki/GIPF_(game)" title="GIPF (game)">GIPF</a> </td> <td style="text-align:right;">37 </td> <td style="text-align:right;">25 </td> <td style="text-align:right;">132 </td> <td style="text-align:right;">90 </td> <td style="text-align:right;">29.3 </td> <td style="text-align:right;"><sup id="cite_ref-Wentink_thesis_28-0" class="reference"><a href="#cite_note-Wentink_thesis-28"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;"> </td></tr> <tr> <td><a href="/wiki/Connect6" title="Connect6">Connect6</a> </td> <td style="text-align:right;">361 </td> <td style="text-align:right;">172 </td> <td style="text-align:right;">140 </td> <td style="text-align:right;">30 </td> <td style="text-align:right;">46000 </td> <td style="text-align:right;"><sup id="cite_ref-EnhancePNConn6_29-0" class="reference"><a href="#cite_note-EnhancePNConn6-29"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE" title="PSPACE">PSPACE-complete</a><sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Backgammon" title="Backgammon">Backgammon</a> </td> <td style="text-align:right;">28 </td> <td style="text-align:right;">20 </td> <td style="text-align:right;">144 </td> <td style="text-align:right;">55 </td> <td style="text-align:right;">250 </td> <td style="text-align:right;"><sup id="cite_ref-31" class="reference"><a href="#cite_note-31"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup> </td> <td>Generalization is unclear </td></tr> <tr> <td><a href="/wiki/Xiangqi" title="Xiangqi">Xiangqi</a> </td> <td style="text-align:right;">90 </td> <td style="text-align:right;">40 </td> <td style="text-align:right;">150 </td> <td style="text-align:right;">95 </td> <td style="text-align:right;">38 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-10" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Hsu2004_32-0" class="reference"><a href="#cite_note-Hsu2004-32"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Donghwi_33-0" class="reference"><a href="#cite_note-Donghwi-33"><span class="cite-bracket">[</span>32<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, believed to be <a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a> </td></tr> <tr> <td><a href="/wiki/Abalone_(board_game)" title="Abalone (board game)">Abalone</a> </td> <td style="text-align:right;">61 </td> <td style="text-align:right;">25 </td> <td style="text-align:right;">154 </td> <td style="text-align:right;">87 </td> <td style="text-align:right;">60 </td> <td style="text-align:right;"><sup id="cite_ref-PasChor_34-0" class="reference"><a href="#cite_note-PasChor-34"><span class="cite-bracket">[</span>33<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Kopczynski_35-0" class="reference"><a href="#cite_note-Kopczynski-35"><span class="cite-bracket">[</span>34<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-hard" class="mw-redirect" title="PSPACE-hard">PSPACE-hard</a>, and in <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a> </td></tr> <tr> <td><a href="/wiki/Havannah_(board_game)" title="Havannah (board game)">Havannah</a> </td> <td style="text-align:right;">271 </td> <td style="text-align:right;">127 </td> <td style="text-align:right;">157 </td> <td style="text-align:right;">66 </td> <td style="text-align:right;">240 </td> <td style="text-align:right;"><sup id="cite_ref-GamesSolved_7-5" class="reference"><a href="#cite_note-GamesSolved-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-36" class="reference"><a href="#cite_note-36"><span class="cite-bracket">[</span>35<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-37" class="reference"><a href="#cite_note-37"><span class="cite-bracket">[</span>36<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/TwixT" title="TwixT">Twixt</a> </td> <td style="text-align:right;">572 </td> <td style="text-align:right;">140 </td> <td style="text-align:right;">159 </td> <td style="text-align:right;">60 </td> <td style="text-align:right;">452 </td> <td style="text-align:right;"><sup id="cite_ref-Thesis_Moesker_38-0" class="reference"><a href="#cite_note-Thesis_Moesker-38"><span class="cite-bracket">[</span>37<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;"> </td></tr> <tr> <td><a href="/wiki/Janggi" title="Janggi">Janggi</a> </td> <td style="text-align:right;">90 </td> <td style="text-align:right;">44 </td> <td style="text-align:right;">160 </td> <td style="text-align:right;">100 </td> <td style="text-align:right;">40 </td> <td style="text-align:right;"><sup id="cite_ref-Donghwi_33-1" class="reference"><a href="#cite_note-Donghwi-33"><span class="cite-bracket">[</span>32<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, believed to be <a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a> </td></tr> <tr> <td><a href="/wiki/Quoridor" title="Quoridor">Quoridor</a> </td> <td style="text-align:right;">81 </td> <td style="text-align:right;">42 </td> <td style="text-align:right;">162 </td> <td style="text-align:right;">91 </td> <td style="text-align:right;">60 </td> <td style="text-align:right;"><sup id="cite_ref-MasterQuor_39-0" class="reference"><a href="#cite_note-MasterQuor-39"><span class="cite-bracket">[</span>38<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a> </td></tr> <tr> <td><a href="/wiki/Carcassonne_(board_game)" title="Carcassonne (board game)">Carcassonne</a> (2p base game) </td> <td style="text-align:right;">72 </td> <td style="text-align:right;">>40 </td> <td style="text-align:right;">195 </td> <td style="text-align:right;">71 </td> <td style="text-align:right;">55 </td> <td style="text-align:right;"><sup id="cite_ref-CarcassoneComputer_40-0" class="reference"><a href="#cite_note-CarcassoneComputer-40"><span class="cite-bracket">[</span>39<span class="cite-bracket">]</span></a></sup> </td> <td>Generalization is unclear </td></tr> <tr> <td><a href="/wiki/Game_of_the_Amazons" title="Game of the Amazons">Amazons (10x10)</a> </td> <td style="text-align:right;">100 </td> <td style="text-align:right;">40 </td> <td style="text-align:right;">212 </td> <td style="text-align:right;">84 </td> <td style="text-align:right;">374 or 299<sup id="cite_ref-41" class="reference"><a href="#cite_note-41"><span class="cite-bracket">[</span>40<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;"><sup id="cite_ref-Kloetzer_themonte-carlo_42-0" class="reference"><a href="#cite_note-Kloetzer_themonte-carlo-42"><span class="cite-bracket">[</span>41<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Hengens_thesis_43-0" class="reference"><a href="#cite_note-Hengens_thesis-43"><span class="cite-bracket">[</span>42<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a><sup id="cite_ref-44" class="reference"><a href="#cite_note-44"><span class="cite-bracket">[</span>43<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Shogi" title="Shogi">Shogi</a> </td> <td style="text-align:right;">81 </td> <td style="text-align:right;">71 </td> <td style="text-align:right;">226 </td> <td style="text-align:right;">115 </td> <td style="text-align:right;">92 </td> <td style="text-align:right;"><sup id="cite_ref-Hsu2004_32-1" class="reference"><a href="#cite_note-Hsu2004-32"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-45" class="reference"><a href="#cite_note-45"><span class="cite-bracket">[</span>44<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a><sup id="cite_ref-46" class="reference"><a href="#cite_note-46"><span class="cite-bracket">[</span>45<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Thurn_and_Taxis_(board_game)" title="Thurn and Taxis (board game)">Thurn and Taxis</a> (2 player) </td> <td style="text-align:right;">33 </td> <td style="text-align:right;">66 </td> <td style="text-align:right;">240 </td> <td style="text-align:right;">56 </td> <td style="text-align:right;">879 </td> <td style="text-align:right;"><sup id="cite_ref-Schadd2010_47-0" class="reference"><a href="#cite_note-Schadd2010-47"><span class="cite-bracket">[</span>46<span class="cite-bracket">]</span></a></sup> </td> <td> </td></tr> <tr> <td><a href="/wiki/Go_(game)" title="Go (game)">Go (19x19)</a> </td> <td style="text-align:right;">361 </td> <td style="text-align:right;">170 </td> <td style="text-align:right;">360 </td> <td style="text-align:right;">150 </td> <td style="text-align:right;">250 </td> <td style="text-align:right;"><sup id="cite_ref-Allis1994_1-11" class="reference"><a href="#cite_note-Allis1994-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-cwi_48-0" class="reference"><a href="#cite_note-cwi-48"><span class="cite-bracket">[</span>47<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Tromp2016_49-0" class="reference"><a href="#cite_note-Tromp2016-49"><span class="cite-bracket">[</span>48<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/EXPTIME-complete" class="mw-redirect" title="EXPTIME-complete">EXPTIME-complete</a> (without the <a href="/wiki/Superko_rule" class="mw-redirect" title="Superko rule">superko rule</a>)<sup id="cite_ref-Robson1983_50-0" class="reference"><a href="#cite_note-Robson1983-50"><span class="cite-bracket">[</span>49<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Arimaa" title="Arimaa">Arimaa</a> </td> <td style="text-align:right;">64 </td> <td style="text-align:right;">43 </td> <td style="text-align:right;">402 </td> <td style="text-align:right;">92 </td> <td style="text-align:right;">17281 </td> <td style="text-align:right;"><sup id="cite_ref-Cox2006_51-0" class="reference"><a href="#cite_note-Cox2006-51"><span class="cite-bracket">[</span>50<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Wu2011_52-0" class="reference"><a href="#cite_note-Wu2011-52"><span class="cite-bracket">[</span>51<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Haskin2006_53-0" class="reference"><a href="#cite_note-Haskin2006-53"><span class="cite-bracket">[</span>52<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">?, but in <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a> </td></tr> <tr> <td><a href="/wiki/Stratego" title="Stratego">Stratego</a> </td> <td style="text-align:right;">92 </td> <td style="text-align:right;">115 </td> <td style="text-align:right;">535 </td> <td style="text-align:right;">381 </td> <td style="text-align:right;">21.739 </td> <td style="text-align:right;"><sup id="cite_ref-ArtsStratego_54-0" class="reference"><a href="#cite_note-ArtsStratego-54"><span class="cite-bracket">[</span>53<span class="cite-bracket">]</span></a></sup> </td> <td style="text-align:right;"> </td></tr> <tr> <td><a href="/wiki/Infinite_chess" title="Infinite chess">Infinite chess</a> </td> <td style="text-align:right;">infinite </td> <td style="text-align:right;">infinite </td> <td style="text-align:right;">infinite </td> <td style="text-align:right;">infinite </td> <td style="text-align:right;">infinite </td> <td style="text-align:right;"><sup id="cite_ref-55" class="reference"><a href="#cite_note-55"><span class="cite-bracket">[</span>54<span class="cite-bracket">]</span></a></sup> </td> <td style="background: var(--background-color-interactive, #EEE); color: var(--color-base, black); vertical-align: middle; white-space: nowrap; text-align: center;" class="table-Unknown">Unknown, but mate-in-n is decidable<sup id="cite_ref-Brumleve2012_56-0" class="reference"><a href="#cite_note-Brumleve2012-56"><span class="cite-bracket">[</span>55<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Magic:_The_Gathering" title="Magic: The Gathering">Magic: The Gathering</a> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"> </td> <td style="text-align:right;"><sup id="cite_ref-Churchill2020_57-0" class="reference"><a href="#cite_note-Churchill2020-57"><span class="cite-bracket">[</span>56<span class="cite-bracket">]</span></a></sup> </td> <td>AH-hard<sup id="cite_ref-Biderman_58-0" class="reference"><a href="#cite_note-Biderman-58"><span class="cite-bracket">[</span>57<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td><a href="/wiki/Wordle" title="Wordle">Wordle</a> </td> <td style="text-align:right;">5 </td> <td style="text-align:right;">12,972 </td> <td style="text-align:right;"> </td> <td style="text-align:right;">6 </td> <td style="text-align:right;"> </td> <td style="text-align:right;"><sup id="cite_ref-59" class="reference"><a href="#cite_note-59"><span class="cite-bracket">[</span>58<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/NP-hardness" title="NP-hardness">NP-hard</a>, unknown if <a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a> with parametization. </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=10" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text">Double dummy bridge (i.e., double dummy problems in the context of <a href="/wiki/Contract_bridge" title="Contract bridge">contract bridge</a>) is not a proper board game but has a similar game tree, and is studied in <a href="/wiki/Computer_bridge" title="Computer bridge">computer bridge</a>. The bridge table can be regarded as having one slot for each player and trick to play a card in, which corresponds to board size 52. Game-tree complexity is a very weak upper bound: 13! to the power of 4 players regardless of legality. State-space complexity is for one given deal; likewise regardless of legality but with many transpositions eliminated. The last 4 plies are always forced moves with branching factor 1.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=11" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-Allis1994-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Allis1994_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Allis1994_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Allis1994_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Allis1994_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Allis1994_1-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-Allis1994_1-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-Allis1994_1-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-Allis1994_1-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-Allis1994_1-8"><sup><i><b>i</b></i></sup></a> <a href="#cite_ref-Allis1994_1-9"><sup><i><b>j</b></i></sup></a> <a href="#cite_ref-Allis1994_1-10"><sup><i><b>k</b></i></sup></a> <a href="#cite_ref-Allis1994_1-11"><sup><i><b>l</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFVictor_Allis1994" class="citation thesis cs1"><a href="/wiki/Victor_Allis" title="Victor Allis">Victor Allis</a> (1994). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf"><i>Searching for Solutions in Games and Artificial Intelligence</i></a> <span class="cs1-format">(PDF)</span> (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/90-900748-8-0" title="Special:BookSources/90-900748-8-0"><bdi>90-900748-8-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Searching+for+Solutions+in+Games+and+Artificial+Intelligence&rft.degree=Ph.D.&rft.inst=University+of+Limburg%2C+Maastricht%2C+The+Netherlands&rft.date=1994&rft.isbn=90-900748-8-0&rft.au=Victor+Allis&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fphd%2FSearchingForSolutions.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://math.stackexchange.com/questions/485752/tictactoe-state-space-choose-calculation">"combinatorics - TicTacToe State Space Choose Calculation"</a>. <i>Mathematics Stack Exchange</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-04-08</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Mathematics+Stack+Exchange&rft.atitle=combinatorics+-+TicTacToe+State+Space+Choose+Calculation&rft_id=https%3A%2F%2Fmath.stackexchange.com%2Fquestions%2F485752%2Ftictactoe-state-space-choose-calculation&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFT2018" class="citation web cs1">T, Brian (October 20, 2018). <a rel="nofollow" class="external text" href="https://github.com/Btsan/generate_tictactoe">"Btsan/generate_tictactoe"</a>. <i><a href="/wiki/GitHub" title="GitHub">GitHub</a></i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-04-08</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=GitHub&rft.atitle=Btsan%2Fgenerate_tictactoe&rft.date=2018-10-20&rft.aulast=T&rft.aufirst=Brian&rft_id=https%3A%2F%2Fgithub.com%2FBtsan%2Fgenerate_tictactoe&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Reisch1980b-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Reisch1980b_4-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStefan_Reisch1980" class="citation journal cs1">Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)". <i>Acta Informatica</i>. <b>13</b> (1): 59–66. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf00288536">10.1007/bf00288536</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21455572">21455572</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Gobang+ist+PSPACE-vollst%C3%A4ndig+%28Gobang+is+PSPACE-complete%29&rft.volume=13&rft.issue=1&rft.pages=59-66&rft.date=1980&rft_id=info%3Adoi%2F10.1007%2Fbf00288536&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A21455572%23id-name%3DS2CID&rft.au=Stefan+Reisch&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Reisch1980-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-Reisch1980_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Reisch1980_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Reisch1980_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Reisch1980_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStefan_Reisch1981" class="citation journal cs1">Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". <i>Acta Inform</i> (15): 167–191.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Inform&rft.atitle=Hex+ist+PSPACE-vollst%C3%A4ndig+%28Hex+is+PSPACE-complete%29&rft.issue=15&rft.pages=167-191&rft.date=1981&rft.au=Stefan+Reisch&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSlany2000" class="citation conference cs1">Slany, Wolfgang (2000). "The complexity of graph Ramsey games". In Marsland, T. Anthony; Frank, Ian (eds.). <i>Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers</i>. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45579-5_12">10.1007/3-540-45579-5_12</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=The+complexity+of+graph+Ramsey+games&rft.btitle=Computers+and+Games%2C+Second+International+Conference%2C+CG+2000%2C+Hamamatsu%2C+Japan%2C+October+26-28%2C+2000%2C+Revised+Papers&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=186-203&rft.pub=Springer&rft.date=2000&rft_id=info%3Adoi%2F10.1007%2F3-540-45579-5_12&rft.aulast=Slany&rft.aufirst=Wolfgang&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-GamesSolved-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-GamesSolved_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-GamesSolved_7-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-GamesSolved_7-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-GamesSolved_7-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-GamesSolved_7-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-GamesSolved_7-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFH._J._van_den_HerikJ._W._H._M._UiterwijkJ._van_Rijswijck2002" class="citation journal cs1">H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0004-3702%2801%2900152-7">"Games solved: Now and in the future"</a>. <i>Artificial Intelligence</i>. <b>134</b> (1–2): 277–311. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0004-3702%2801%2900152-7">10.1016/S0004-3702(01)00152-7</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Artificial+Intelligence&rft.atitle=Games+solved%3A+Now+and+in+the+future&rft.volume=134&rft.issue=1%E2%80%932&rft.pages=277-311&rft.date=2002&rft_id=info%3Adoi%2F10.1016%2FS0004-3702%2801%2900152-7&rft.au=H.+J.+van+den+Herik&rft.au=J.+W.+H.+M.+Uiterwijk&rft.au=J.+van+Rijswijck&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252FS0004-3702%252801%252900152-7&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOrman1996" class="citation conference cs1">Orman, Hilarie K. (1996). <a rel="nofollow" class="external text" href="https://www.msri.org/publications/books/Book29/files/orman.pdf">"Pentominoes: a first player win"</a> <span class="cs1-format">(PDF)</span>. In Nowakowski, Richard J. (ed.). <i>Games of No Chance: Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994</i>. Mathematical Sciences Research Institute Publications. Vol. 29. Cambridge University Press. pp. 339–344. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-57411-0" title="Special:BookSources/0-521-57411-0"><bdi>0-521-57411-0</bdi></a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1427975">1427975</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Pentominoes%3A+a+first+player+win&rft.btitle=Games+of+No+Chance%3A+Papers+from+the+Combinatorial+Games+Workshop+held+in+Berkeley%2C+CA%2C+July+11%E2%80%9321%2C+1994&rft.series=Mathematical+Sciences+Research+Institute+Publications&rft.pages=339-344&rft.pub=Cambridge+University+Press&rft.date=1996&rft.isbn=0-521-57411-0&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1427975%23id-name%3DMR&rft.aulast=Orman&rft.aufirst=Hilarie+K.&rft_id=https%3A%2F%2Fwww.msri.org%2Fpublications%2Fbooks%2FBook29%2Ffiles%2Forman.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">See van den Herik et al for rules.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJohn_Tromp2010" class="citation web cs1">John Tromp (2010). <a rel="nofollow" class="external text" href="https://tromp.github.io/c4/c4.html">"John's Connect Four Playground"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=John%27s+Connect+Four+Playground&rft.date=2010&rft.au=John+Tromp&rft_id=https%3A%2F%2Ftromp.github.io%2Fc4%2Fc4.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLachmannMooreRapaport2002" class="citation conference cs1">Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "Who wins Domineering on rectangular boards?". In Nowakowski, Richard (ed.). <i>More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000</i>. Mathematical Sciences Research Institute Publications. Vol. 42. Cambridge University Press. pp. 307–315. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-80832-4" title="Special:BookSources/0-521-80832-4"><bdi>0-521-80832-4</bdi></a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1973019">1973019</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Who+wins+Domineering+on+rectangular+boards%3F&rft.btitle=More+Games+of+No+Chance%3A+Proceedings+of+the+2nd+Combinatorial+Games+Theory+Workshop+held+in+Berkeley%2C+CA%2C+July+24%E2%80%9328%2C+2000&rft.series=Mathematical+Sciences+Research+Institute+Publications&rft.pages=307-315&rft.pub=Cambridge+University+Press&rft.date=2002&rft.isbn=0-521-80832-4&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1973019%23id-name%3DMR&rft.aulast=Lachmann&rft.aufirst=Michael&rft.au=Moore%2C+Cristopher&rft.au=Rapaport%2C+Ivan&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJonathan_Schaeffer2007" class="citation journal cs1">Jonathan Schaeffer; et al. (July 6, 2007). <a rel="nofollow" class="external text" href="https://doi.org/10.1126%2Fscience.1144079">"Checkers is Solved"</a>. <i>Science</i>. <b>317</b> (5844): 1518–1522. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2007Sci...317.1518S">2007Sci...317.1518S</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1126%2Fscience.1144079">10.1126/science.1144079</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17641166">17641166</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10274228">10274228</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Science&rft.atitle=Checkers+is+Solved&rft.volume=317&rft.issue=5844&rft.pages=1518-1522&rft.date=2007-07-06&rft_id=info%3Adoi%2F10.1126%2Fscience.1144079&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10274228%23id-name%3DS2CID&rft_id=info%3Apmid%2F17641166&rft_id=info%3Abibcode%2F2007Sci...317.1518S&rft.au=Jonathan+Schaeffer&rft_id=https%3A%2F%2Fdoi.org%2F10.1126%252Fscience.1144079&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSchaeffer2007" class="citation journal cs1">Schaeffer, Jonathan (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160403093928/https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf">"Game over: Black to play and draw in checkers"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/ICGA_Journal" title="ICGA Journal">ICGA Journal</a></i>. <b>30</b> (4): 187–197. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3233%2FICG-2007-30402">10.3233/ICG-2007-30402</a>. Archived from <a rel="nofollow" class="external text" href="https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2016-04-03.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ICGA+Journal&rft.atitle=Game+over%3A+Black+to+play+and+draw+in+checkers&rft.volume=30&rft.issue=4&rft.pages=187-197&rft.date=2007&rft_id=info%3Adoi%2F10.3233%2FICG-2007-30402&rft.aulast=Schaeffer&rft.aufirst=Jonathan&rft_id=https%3A%2F%2Fticc.uvt.nl%2Ficga%2Fjournal%2Fcontents%2FSchaeffer07-01-08.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-robson1984-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-robson1984_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-robson1984_14-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._M._Robson1984" class="citation journal cs1">J. M. Robson (1984). "N by N checkers is Exptime complete". <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>. <b>13</b> (2): 252–267. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0213018">10.1137/0213018</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=N+by+N+checkers+is+Exptime+complete&rft.volume=13&rft.issue=2&rft.pages=252-267&rft.date=1984&rft_id=info%3Adoi%2F10.1137%2F0213018&rft.au=J.+M.+Robson&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">See Allis 1994 for rules</span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBonnetJamainSaffidine2013" class="citation conference cs1">Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013). <a rel="nofollow" class="external text" href="https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6920">"On the complexity of trick-taking card games"</a>. In Rossi, Francesca (ed.). <i>IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013</i>. IJCAI/AAAI. pp. 482–488.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=On+the+complexity+of+trick-taking+card+games&rft.btitle=IJCAI+2013%2C+Proceedings+of+the+23rd+International+Joint+Conference+on+Artificial+Intelligence%2C+Beijing%2C+China%2C+August+3-9%2C+2013&rft.pages=482-488&rft.pub=IJCAI%2FAAAI&rft.date=2013&rft.aulast=Bonnet&rft.aufirst=Edouard&rft.au=Jamain%2C+Florian&rft.au=Saffidine%2C+Abdallah&rft_id=https%3A%2F%2Fwww.aaai.org%2Focs%2Findex.php%2FIJCAI%2FIJCAI13%2Fpaper%2Fview%2F6920&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Schadd2008-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-Schadd2008_18-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFM.P.D._SchaddM.H.M._WinandsJ.W.H.M._UiterwijkH.J._van_den_Herik2008" class="citation journal cs1">M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008). <a rel="nofollow" class="external text" href="https://dke.maastrichtuniversity.nl/m.winands/documents/Fanorona.pdf">"Best Play in Fanorona leads to Draw"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/New_Mathematics_and_Natural_Computation" title="New Mathematics and Natural Computation">New Mathematics and Natural Computation</a></i>. <b>4</b> (3): 369–387. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS1793005708001124">10.1142/S1793005708001124</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=New+Mathematics+and+Natural+Computation&rft.atitle=Best+Play+in+Fanorona+leads+to+Draw&rft.volume=4&rft.issue=3&rft.pages=369-387&rft.date=2008&rft_id=info%3Adoi%2F10.1142%2FS1793005708001124&rft.au=M.P.D.+Schadd&rft.au=M.H.M.+Winands&rft.au=J.W.H.M.+Uiterwijk&rft.au=H.J.+van+den+Herik&rft.au=M.H.J.+Bergsma&rft_id=https%3A%2F%2Fdke.maastrichtuniversity.nl%2Fm.winands%2Fdocuments%2FFanorona.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Galassi2018-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-Galassi2018_19-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAndrea_Galassi2018" class="citation web cs1">Andrea Galassi (2018). <a rel="nofollow" class="external text" href="http://ai.unibo.it/biblio/galassiTablutComplexity">"An Upper Bound on the Complexity of Tablut"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=An+Upper+Bound+on+the+Complexity+of+Tablut&rft.date=2018&rft.au=Andrea+Galassi&rft_id=http%3A%2F%2Fai.unibo.it%2Fbiblio%2FgalassiTablutComplexity&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Bell_Halma-20"><span class="mw-cite-backlink">^ <a href="#cite_ref-Bell_Halma_20-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Bell_Halma_20-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFG.I._Bell2009" class="citation journal cs1">G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". <i>Integers</i>. <b>9</b>. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0803.1245">0803.1245</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2008arXiv0803.1245B">2008arXiv0803.1245B</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1515%2FINTEG.2009.003">10.1515/INTEG.2009.003</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17141575">17141575</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Integers&rft.atitle=The+Shortest+Game+of+Chinese+Checkers+and+Related+Problems&rft.volume=9&rft.date=2009&rft_id=info%3Aarxiv%2F0803.1245&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A17141575%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1515%2FINTEG.2009.003&rft_id=info%3Abibcode%2F2008arXiv0803.1245B&rft.au=G.I.+Bell&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-pebble-21"><span class="mw-cite-backlink">^ <a href="#cite_ref-pebble_21-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-pebble_21-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKasaiAdachiIwata1979" class="citation journal cs1">Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Classes of pebble games and complete problems". <i>SIAM Journal on Computing</i>. <b>8</b> (4): 574–586. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0208046">10.1137/0208046</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0573848">0573848</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Classes+of+pebble+games+and+complete+problems&rft.volume=8&rft.issue=4&rft.pages=574-586&rft.date=1979&rft_id=info%3Adoi%2F10.1137%2F0208046&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D573848%23id-name%3DMR&rft.aulast=Kasai&rft.aufirst=Takumi&rft.au=Adachi%2C+Akeo&rft.au=Iwata%2C+Shigeki&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span> Proves completeness of the generalization to arbitrary graphs.</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFIwataKasai1994" class="citation journal cs1">Iwata, Shigeki; Kasai, Takumi (1994). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2894%2990131-7">"The Othello game on an <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}"></span> board is PSPACE-complete"</a>. <i>Theoretical Computer Science</i>. <b>123</b> (2): 329–340. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2894%2990131-7">10.1016/0304-3975(94)90131-7</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1256205">1256205</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=The+Othello+game+on+an+MATH+RENDER+ERROR+board+is+PSPACE-complete&rft.volume=123&rft.issue=2&rft.pages=329-340&rft.date=1994&rft_id=info%3Adoi%2F10.1016%2F0304-3975%2894%2990131-7&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1256205%23id-name%3DMR&rft.aulast=Iwata&rft.aufirst=Shigeki&rft.au=Kasai%2C+Takumi&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252F0304-3975%252894%252990131-7&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-OnTopComputer-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-OnTopComputer_23-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRobert_Briesemeister2009" class="citation thesis cs1">Robert Briesemeister (2009). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Briesemeister_Thesis.pdf"><i>Analysis and Implementation of the Game OnTop</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Maastricht University, Dept of Knowledge Engineering.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Analysis+and+Implementation+of+the+Game+OnTop&rft.inst=Maastricht+University%2C+Dept+of+Knowledge+Engineering&rft.date=2009&rft.au=Robert+Briesemeister&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FBriesemeister_Thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Winands2004-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-Winands2004_24-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMark_H.M._Winands2004" class="citation thesis cs1">Mark H.M. Winands (2004). <a rel="nofollow" class="external text" href="https://dke.maastrichtuniversity.nl/m.winands/documents/informed_search.pdf"><i>Informed Search in Complex Games</i></a> <span class="cs1-format">(PDF)</span> (Ph.D. thesis). Maastricht University, Maastricht, The Netherlands. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/90-5278-429-9" title="Special:BookSources/90-5278-429-9"><bdi>90-5278-429-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Informed+Search+in+Complex+Games&rft.degree=Ph.D.&rft.inst=Maastricht+University%2C+Maastricht%2C+The+Netherlands&rft.date=2004&rft.isbn=90-5278-429-9&rft.au=Mark+H.M.+Winands&rft_id=https%3A%2F%2Fdke.maastrichtuniversity.nl%2Fm.winands%2Fdocuments%2Finformed_search.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Shannon1950-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-Shannon1950_25-0">^</a></b></span> <span class="reference-text">The size of the state space and game tree for chess were first estimated in <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFClaude_Shannon1950" class="citation journal cs1"><a href="/wiki/Claude_Shannon" title="Claude Shannon">Claude Shannon</a> (1950). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf">"Programming a Computer for Playing Chess"</a> <span class="cs1-format">(PDF)</span>. <i>Philosophical Magazine</i>. <b>41</b> (314). Archived from <a rel="nofollow" class="external text" href="http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2010-07-06.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Philosophical+Magazine&rft.atitle=Programming+a+Computer+for+Playing+Chess&rft.volume=41&rft.issue=314&rft.date=1950&rft.au=Claude+Shannon&rft_id=http%3A%2F%2Farchive.computerhistory.org%2Fprojects%2Fchess%2Frelated_materials%2Ftext%2F2-0%2520and%25202-1.Programming_a_computer_for_playing_chess.shannon%2F2-0%2520and%25202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span> Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the upper bound in the table, which is detailed in <a href="/wiki/Shannon_number" title="Shannon number">Shannon number</a>.</span> </li> <li id="cite_note-Fraenkel1981-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-Fraenkel1981_26-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFraenkelLichtenstein1981" class="citation journal cs1"><a href="/wiki/Aviezri_Fraenkel" title="Aviezri Fraenkel">Fraenkel, Aviezri S.</a>; Lichtenstein, David (1981). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2881%2990016-9">"Computing a perfect strategy for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>×</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59d2b4cb72e304526cf5b5887147729ea259da78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}"></span> chess requires time exponential in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>"</a>. <i><a href="/wiki/Journal_of_Combinatorial_Theory,_Series_A" class="mw-redirect" title="Journal of Combinatorial Theory, Series A">Journal of Combinatorial Theory, Series A</a></i>. <b>31</b> (2): 199–214. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2881%2990016-9">10.1016/0097-3165(81)90016-9</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0629595">0629595</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Combinatorial+Theory%2C+Series+A&rft.atitle=Computing+a+perfect+strategy+for+MATH+RENDER+ERROR+chess+requires+time+exponential+in+MATH+RENDER+ERROR&rft.volume=31&rft.issue=2&rft.pages=199-214&rft.date=1981&rft_id=info%3Adoi%2F10.1016%2F0097-3165%2881%2990016-9&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D629595%23id-name%3DMR&rft.aulast=Fraenkel&rft.aufirst=Aviezri+S.&rft.au=Lichtenstein%2C+David&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252F0097-3165%252881%252990016-9&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Gual14-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-Gual14_27-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGualàLeucciNatale2014" class="citation conference cs1">Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled, Candy Crush and other match-three games are (NP-)hard". <i>2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014</i>. IEEE. pp. 1–8. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1403.5830">1403.5830</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCIG.2014.6932866">10.1109/CIG.2014.6932866</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Bejeweled%2C+Candy+Crush+and+other+match-three+games+are+%28NP-%29hard&rft.btitle=2014+IEEE+Conference+on+Computational+Intelligence+and+Games%2C+CIG+2014%2C+Dortmund%2C+Germany%2C+August+26-29%2C+2014&rft.pages=1-8&rft.pub=IEEE&rft.date=2014&rft_id=info%3Aarxiv%2F1403.5830&rft_id=info%3Adoi%2F10.1109%2FCIG.2014.6932866&rft.aulast=Gual%C3%A0&rft.aufirst=Luciano&rft.au=Leucci%2C+Stefano&rft.au=Natale%2C+Emanuele&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Wentink_thesis-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-Wentink_thesis_28-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDiederik_Wentink2001" class="citation thesis cs1">Diederik Wentink (2001). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Wentink_thesis.pdf"><i>Analysis and Implementation of the game Gipf</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Maastricht University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Analysis+and+Implementation+of+the+game+Gipf&rft.inst=Maastricht+University&rft.date=2001&rft.au=Diederik+Wentink&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FWentink_thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-EnhancePNConn6-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-EnhancePNConn6_29-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChang-Ming_XuMaJun-Jie_TaoXin-He_Xu2009" class="citation book cs1">Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu (2009). "Enhancements of proof number search in connect6". <i>2009 Chinese Control and Decision Conference</i>. p. 4525. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCCDC.2009.5191963">10.1109/CCDC.2009.5191963</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4244-2722-2" title="Special:BookSources/978-1-4244-2722-2"><bdi>978-1-4244-2722-2</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:20960281">20960281</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Enhancements+of+proof+number+search+in+connect6&rft.btitle=2009+Chinese+Control+and+Decision+Conference&rft.pages=4525&rft.date=2009&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A20960281%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FCCDC.2009.5191963&rft.isbn=978-1-4244-2722-2&rft.au=Chang-Ming+Xu&rft.au=Ma%2C+Z.M.&rft.au=Jun-Jie+Tao&rft.au=Xin-He+Xu&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHsiehTsai2007" class="citation journal cs1">Hsieh, Ming Yu; Tsai, Shi-Chun (October 1, 2007). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=1290195.1290250">"On the fairness and complexity of generalized k -in-a-row games"</a>. <i>Theoretical Computer Science</i>. <b>385</b> (1–3): 88–100. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2007.05.031">10.1016/j.tcs.2007.05.031</a></span><span class="reference-accessdate">. Retrieved <span class="nowrap">2018-04-12</span></span> – via dl.acm.org.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=On+the+fairness+and+complexity+of+generalized+k+-in-a-row+games&rft.volume=385&rft.issue=1%E2%80%933&rft.pages=88-100&rft.date=2007-10-01&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2007.05.031&rft.aulast=Hsieh&rft.aufirst=Ming+Yu&rft.au=Tsai%2C+Shi-Chun&rft_id=http%3A%2F%2Fdl.acm.org%2Fcitation.cfm%3Fid%3D1290195.1290250&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-31">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTesauro1992" class="citation journal cs1">Tesauro, Gerald (May 1, 1992). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00992697">"Practical issues in temporal difference learning"</a>. <i>Machine Learning</i>. <b>8</b> (3–4): 257–277. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00992697">10.1007/BF00992697</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Machine+Learning&rft.atitle=Practical+issues+in+temporal+difference+learning&rft.volume=8&rft.issue=3%E2%80%934&rft.pages=257-277&rft.date=1992-05-01&rft_id=info%3Adoi%2F10.1007%2FBF00992697&rft.aulast=Tesauro&rft.aufirst=Gerald&rft_id=https%3A%2F%2Fdoi.org%2F10.1007%252FBF00992697&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Hsu2004-32"><span class="mw-cite-backlink">^ <a href="#cite_ref-Hsu2004_32-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Hsu2004_32-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShi-Jim_Yen,_Jr-Chang_ChenTai-Ning_YangShun-Chin_Hsu2004" class="citation journal cs1">Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (March 2004). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf">"Computer Chinese Chess"</a> <span class="cs1-format">(PDF)</span>. <i>International Computer Games Association Journal</i>. <b>27</b> (1): 3–18. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3233%2FICG-2004-27102">10.3233/ICG-2004-27102</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10336286">10336286</a>. Archived from <a rel="nofollow" class="external text" href="http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2007-06-14.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=International+Computer+Games+Association+Journal&rft.atitle=Computer+Chinese+Chess&rft.volume=27&rft.issue=1&rft.pages=3-18&rft.date=2004-03&rft_id=info%3Adoi%2F10.3233%2FICG-2004-27102&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10336286%23id-name%3DS2CID&rft.au=Shi-Jim+Yen%2C+Jr-Chang+Chen&rft.au=Tai-Ning+Yang&rft.au=Shun-Chin+Hsu&rft_id=http%3A%2F%2Fwww.csie.ndhu.edu.tw%2F~sjyen%2FPapers%2F2004CCC.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Donghwi-33"><span class="mw-cite-backlink">^ <a href="#cite_ref-Donghwi_33-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Donghwi_33-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDonghwi_Park2015" class="citation arxiv cs1">Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1507.06401">1507.06401</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.GM">math.GM</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Space-state+complexity+of+Korean+chess+and+Chinese+chess&rft.date=2015&rft_id=info%3Aarxiv%2F1507.06401&rft.au=Donghwi+Park&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-PasChor-34"><span class="mw-cite-backlink"><b><a href="#cite_ref-PasChor_34-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChorus" class="citation web cs1">Chorus, Pascal. <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/pcreport.pdf">"Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search"</a> <span class="cs1-format">(PDF)</span>. Dept of Knowledge Engineering, Maastricht University<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-03-29</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Implementing+a+Computer+Player+for+Abalone+Using+Alpha-Beta+and+Monte-Carlo+Search&rft.pub=Dept+of+Knowledge+Engineering%2C+Maastricht+University&rft.aulast=Chorus&rft.aufirst=Pascal&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2Fpcreport.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Kopczynski-35"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kopczynski_35-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKopczynski2014" class="citation thesis cs1">Kopczynski, Jacob S (2014). <i>Pushy Computing: Complexity Theory and the Game Abalone</i> (Thesis). Reed College.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Pushy+Computing%3A+Complexity+Theory+and+the+Game+Abalone&rft.inst=Reed+College&rft.date=2014&rft.aulast=Kopczynski&rft.aufirst=Jacob+S&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-36"><span class="mw-cite-backlink"><b><a href="#cite_ref-36">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJoosten" class="citation web cs1">Joosten, B. <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/bsc/bscHavannah.pdf">"Creating a Havannah Playing Agent"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">2012-03-29</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Creating+a+Havannah+Playing+Agent&rft.aulast=Joosten&rft.aufirst=B&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fbsc%2FbscHavannah.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-37"><span class="mw-cite-backlink"><b><a href="#cite_ref-37">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFE._BonnetF._JamainA._Saffidine2014" class="citation arxiv cs1">E. Bonnet; F. Jamain; A. Saffidine (March 25, 2014). "Havannah and TwixT are PSPACE-complete". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1403.6518">1403.6518</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CC">cs.CC</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Havannah+and+TwixT+are+PSPACE-complete&rft.date=2014-03-25&rft_id=info%3Aarxiv%2F1403.6518&rft.au=E.+Bonnet&rft.au=F.+Jamain&rft.au=A.+Saffidine&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Thesis_Moesker-38"><span class="mw-cite-backlink"><b><a href="#cite_ref-Thesis_Moesker_38-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKevin_Moesker2009" class="citation thesis cs1">Kevin Moesker (2009). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf"><i>Txixt: Theory, Analysis, and Implementation</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Faculty of Humanities and Sciences of Maastricht University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Txixt%3A+Theory%2C+Analysis%2C+and+Implementation&rft.inst=Faculty+of+Humanities+and+Sciences+of+Maastricht+University&rft.date=2009&rft.au=Kevin+Moesker&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FThesis_Moesker.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-MasterQuor-39"><span class="mw-cite-backlink"><b><a href="#cite_ref-MasterQuor_39-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLisa_Glendenning2005" class="citation thesis cs1">Lisa Glendenning (May 2005). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf"><i>Mastering Quoridor</i></a> <span class="cs1-format">(PDF)</span>. Computer Science (B.Sc. thesis). <a href="/wiki/University_of_New_Mexico" title="University of New Mexico">University of New Mexico</a>. Archived from <a rel="nofollow" class="external text" href="http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2012-03-15.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Mastering+Quoridor&rft.degree=B.Sc.&rft.inst=University+of+New+Mexico&rft.date=2005-05&rft.au=Lisa+Glendenning&rft_id=http%3A%2F%2Fhyperion.cs.washington.edu%2Fattachments%2F15%2Fglendenning_ugrad_thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-CarcassoneComputer-40"><span class="mw-cite-backlink"><b><a href="#cite_ref-CarcassoneComputer_40-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCathleen_Heyden2009" class="citation thesis cs1">Cathleen Heyden (2009). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/MasterThesisCarcassonne.pdf"><i>Implementing a Computer Player for Carcassonne</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Maastricht University, Dept of Knowledge Engineering.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Implementing+a+Computer+Player+for+Carcassonne&rft.inst=Maastricht+University%2C+Dept+of+Knowledge+Engineering&rft.date=2009&rft.au=Cathleen+Heyden&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FMasterThesisCarcassonne.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-41"><span class="mw-cite-backlink"><b><a href="#cite_ref-41">^</a></b></span> <span class="reference-text">The lower branching factor is for the second player.</span> </li> <li id="cite_note-Kloetzer_themonte-carlo-42"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kloetzer_themonte-carlo_42-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKloetzerIidaBouzy2007" class="citation conference cs1">Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007). <a rel="nofollow" class="external text" href="https://helios2.mi.parisdescartes.fr/~Bouzy/publications/KIB-MCAmazons-CGW07.pdf">"The Monte-Carlo approach in Amazons"</a> <span class="cs1-format">(PDF)</span>. <i>Computer Games Workshop, Amsterdam, the Netherlands, 15-17 June 2007</i>. pp. 185–192.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=The+Monte-Carlo+approach+in+Amazons&rft.btitle=Computer+Games+Workshop%2C+Amsterdam%2C+the+Netherlands%2C+15-17+June+2007&rft.pages=185-192&rft.date=2007&rft.aulast=Kloetzer&rft.aufirst=Julien&rft.au=Iida%2C+Hiroyuki&rft.au=Bouzy%2C+Bruno&rft_id=https%3A%2F%2Fhelios2.mi.parisdescartes.fr%2F~Bouzy%2Fpublications%2FKIB-MCAmazons-CGW07.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Hengens_thesis-43"><span class="mw-cite-backlink"><b><a href="#cite_ref-Hengens_thesis_43-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFP._P._L._M._Hensgens2001" class="citation web cs1">P. P. L. M. Hensgens (2001). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Hensgens_thesis.pdf">"A Knowledge-Based Approach of the Game of Amazons"</a> <span class="cs1-format">(PDF)</span>. Universiteit Maastricht, Institute for Knowledge and Agent Technology.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=A+Knowledge-Based+Approach+of+the+Game+of+Amazons&rft.pub=Universiteit+Maastricht%2C+Institute+for+Knowledge+and+Agent+Technology&rft.date=2001&rft.au=P.+P.+L.+M.+Hensgens&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FHensgens_thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-44"><span class="mw-cite-backlink"><b><a href="#cite_ref-44">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFR._A._Hearn2005" class="citation arxiv cs1"><a href="/wiki/Bob_Hearn" title="Bob Hearn">R. A. Hearn</a> (February 2, 2005). "Amazons is PSPACE-complete". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs.CC/0502013">cs.CC/0502013</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Amazons+is+PSPACE-complete&rft.date=2005-02-02&rft_id=info%3Aarxiv%2Fcs.CC%2F0502013&rft.au=R.+A.+Hearn&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-45"><span class="mw-cite-backlink"><b><a href="#cite_ref-45">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHiroyuki_IidaMakoto_SakutaJeff_Rollason2002" class="citation journal cs1">Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (January 2002). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0004-3702%2801%2900157-6">"Computer shogi"</a>. <i>Artificial Intelligence</i>. <b>134</b> (1–2): 121–144. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0004-3702%2801%2900157-6">10.1016/S0004-3702(01)00157-6</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Artificial+Intelligence&rft.atitle=Computer+shogi&rft.volume=134&rft.issue=1%E2%80%932&rft.pages=121-144&rft.date=2002-01&rft_id=info%3Adoi%2F10.1016%2FS0004-3702%2801%2900157-6&rft.au=Hiroyuki+Iida&rft.au=Makoto+Sakuta&rft.au=Jeff+Rollason&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252FS0004-3702%252801%252900157-6&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-46"><span class="mw-cite-backlink"><b><a href="#cite_ref-46">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFH._AdachiH._KamekawaS._Iwata1987" class="citation journal cs1 cs1-prop-long-vol">H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi on n × n board is complete in exponential time". <i>Trans. IEICE</i>. J70-D: 1843–1852.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Trans.+IEICE&rft.atitle=Shogi+on+n+%C3%97+n+board+is+complete+in+exponential+time&rft.volume=J70-D&rft.pages=1843-1852&rft.date=1987&rft.au=H.+Adachi&rft.au=H.+Kamekawa&rft.au=S.+Iwata&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Schadd2010-47"><span class="mw-cite-backlink"><b><a href="#cite_ref-Schadd2010_47-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFF.C._Schadd2009" class="citation thesis cs1">F.C. Schadd (2009). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210114164554/https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf"><i>Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Maastricht University. Archived from <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2021-01-14.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Monte-Carlo+Search+Techniques+in+the+Modern+Board+Game+Thurn+and+Taxis&rft.inst=Maastricht+University&rft.date=2009&rft.au=F.C.+Schadd&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FFschadd_thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-cwi-48"><span class="mw-cite-backlink"><b><a href="#cite_ref-cwi_48-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJohn_TrompGunnar_Farnebäck2007" class="citation web cs1">John Tromp; Gunnar Farnebäck (2007). <a rel="nofollow" class="external text" href="https://tromp.github.io/go/gostate.ps">"Combinatorics of Go"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Combinatorics+of+Go&rft.date=2007&rft.au=John+Tromp&rft.au=Gunnar+Farneb%C3%A4ck&rft_id=https%3A%2F%2Ftromp.github.io%2Fgo%2Fgostate.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span> This paper derives the bounds 48<log(log(<i>N</i>))<171 on the number of possible games <i>N</i>.</span> </li> <li id="cite_note-Tromp2016-49"><span class="mw-cite-backlink"><b><a href="#cite_ref-Tromp2016_49-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJohn_Tromp2016" class="citation web cs1">John Tromp (2016). <a rel="nofollow" class="external text" href="https://tromp.github.io/go/legal.html">"Number of legal Go positions"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Number+of+legal+Go+positions&rft.date=2016&rft.au=John+Tromp&rft_id=https%3A%2F%2Ftromp.github.io%2Fgo%2Flegal.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Robson1983-50"><span class="mw-cite-backlink"><b><a href="#cite_ref-Robson1983_50-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._M._Robson1983" class="citation book cs1">J. M. Robson (1983). "The complexity of Go". <i>Information Processing; Proceedings of IFIP Congress</i>. pp. 413–417.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+complexity+of+Go&rft.btitle=Information+Processing%3B+Proceedings+of+IFIP+Congress&rft.pages=413-417&rft.date=1983&rft.au=J.+M.+Robson&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Cox2006-51"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cox2006_51-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChrist-Jan_Cox2006" class="citation web cs1">Christ-Jan Cox (2006). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Cox_thesis1.pdf">"Analysis and Implementation of the Game Arimaa"</a> <span class="cs1-format">(PDF)</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Analysis+and+Implementation+of+the+Game+Arimaa&rft.date=2006&rft.au=Christ-Jan+Cox&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FCox_thesis1.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Wu2011-52"><span class="mw-cite-backlink"><b><a href="#cite_ref-Wu2011_52-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDavid_Jian_Wu2011" class="citation web cs1">David Jian Wu (2011). <a rel="nofollow" class="external text" href="http://icosahedral.net/downloads/djwuthesis.pdf">"Move Ranking and Evaluation in the Game of Arimaa"</a> <span class="cs1-format">(PDF)</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Move+Ranking+and+Evaluation+in+the+Game+of+Arimaa&rft.date=2011&rft.au=David+Jian+Wu&rft_id=http%3A%2F%2Ficosahedral.net%2Fdownloads%2Fdjwuthesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Haskin2006-53"><span class="mw-cite-backlink"><b><a href="#cite_ref-Haskin2006_53-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrian_Haskin2006" class="citation web cs1">Brian Haskin (2006). <a rel="nofollow" class="external text" href="http://arimaa.janzert.com/bf_study/">"A Look at the Arimaa Branching Factor"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=A+Look+at+the+Arimaa+Branching+Factor&rft.date=2006&rft.au=Brian+Haskin&rft_id=http%3A%2F%2Farimaa.janzert.com%2Fbf_study%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-ArtsStratego-54"><span class="mw-cite-backlink"><b><a href="#cite_ref-ArtsStratego_54-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFA.F.C._Arts2010" class="citation thesis cs1">A.F.C. Arts (2010). <a rel="nofollow" class="external text" href="https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf"><i>Competitive Play in Stratego</i></a> <span class="cs1-format">(PDF)</span> (Thesis). Maastricht.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Competitive+Play+in+Stratego&rft.inst=Maastricht&rft.date=2010&rft.au=A.F.C.+Arts&rft_id=https%3A%2F%2Fproject.dke.maastrichtuniversity.nl%2Fgames%2Ffiles%2Fmsc%2FArts_thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-55"><span class="mw-cite-backlink"><b><a href="#cite_ref-55">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCDA_Evans_and_Joel_David_Hamkins2014" class="citation arxiv cs1">CDA Evans and Joel David Hamkins (2014). "Transfinite game values in infinite chess". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1302.4377">1302.4377</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.LO">math.LO</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Transfinite+game+values+in+infinite+chess&rft.date=2014&rft_id=info%3Aarxiv%2F1302.4377&rft.au=CDA+Evans+and+Joel+David+Hamkins&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-Brumleve2012-56"><span class="mw-cite-backlink"><b><a href="#cite_ref-Brumleve2012_56-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStefan_Reisch,_Joel_David_Hamkins,_and_Phillipp_Schlicht2012" class="citation journal cs1">Stefan Reisch, Joel David Hamkins, and Phillipp Schlicht (2012). "The mate-in-n problem of infinite chess is decidable". <i>Conference on Computability in Europe</i>: 78–88. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1201.5597">1201.5597</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Conference+on+Computability+in+Europe&rft.atitle=The+mate-in-n+problem+of+infinite+chess+is+decidable&rft.pages=78-88&rft.date=2012&rft_id=info%3Aarxiv%2F1201.5597&rft.au=Stefan+Reisch%2C+Joel+David+Hamkins%2C+and+Phillipp+Schlicht&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_journal" title="Template:Cite journal">cite journal</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span> </li> <li id="cite_note-Churchill2020-57"><span class="mw-cite-backlink"><b><a href="#cite_ref-Churchill2020_57-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlex_Churchill,_Stella_Biderman,_and_Austin_Herrick2020" class="citation arxiv cs1">Alex Churchill, Stella Biderman, and Austin Herrick (2020). "Magic: the Gathering is Turing Complete". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1904.09828">1904.09828</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.AI">cs.AI</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Magic%3A+the+Gathering+is+Turing+Complete&rft.date=2020&rft_id=info%3Aarxiv%2F1904.09828&rft.au=Alex+Churchill%2C+Stella+Biderman%2C+and+Austin+Herrick&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_arXiv" title="Template:Cite arXiv">cite arXiv</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span> </li> <li id="cite_note-Biderman-58"><span class="mw-cite-backlink"><b><a href="#cite_ref-Biderman_58-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStella_Biderman2020" class="citation arxiv cs1">Stella Biderman (2020). "Magic: the Gathering is as Hard as Arithmetic". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2003.05119">2003.05119</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.AI">cs.AI</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Magic%3A+the+Gathering+is+as+Hard+as+Arithmetic&rft.date=2020&rft_id=info%3Aarxiv%2F2003.05119&rft.au=Stella+Biderman&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> <li id="cite_note-59"><span class="mw-cite-backlink"><b><a href="#cite_ref-59">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLokshtanovSubercaseaux2022" class="citation arxiv cs1">Lokshtanov, Daniel; Subercaseaux, Bernardo (May 14, 2022). "Wordle is NP-hard". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2203.16713">2203.16713</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CC">cs.CC</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Wordle+is+NP-hard&rft.date=2022-05-14&rft_id=info%3Aarxiv%2F2203.16713&rft.aulast=Lokshtanov&rft.aufirst=Daniel&rft.au=Subercaseaux%2C+Bernardo&rfr_id=info%3Asid%2Fen.wikipedia.org%3AGame+complexity" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Go_and_mathematics" title="Go and mathematics">Go and mathematics</a></li> <li><a href="/wiki/Solved_game" title="Solved game">Solved game</a></li> <li><a href="/wiki/Solving_chess" title="Solving chess">Solving chess</a></li> <li><a href="/wiki/Shannon_number" title="Shannon number">Shannon number</a></li> <li><a href="/wiki/List_of_NP-complete_problems#Games_and_puzzles" title="List of NP-complete problems">list of NP-complete games and puzzles</a></li> <li><a href="/wiki/List_of_PSPACE-complete_problems#Games_and_puzzles" title="List of PSPACE-complete problems">list of PSPACE-complete games and puzzles</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Game_complexity&action=edit&section=13" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/David_Eppstein" title="David Eppstein">David Eppstein</a>'s <a rel="nofollow" class="external text" href="http://www.ics.uci.edu/~eppstein/cgt/hard.html">Computational Complexity of Games and Puzzles</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Topics_of_game_theory" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Game_theory" title="Template:Game theory"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Game_theory" title="Template talk:Game theory"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Game_theory" title="Special:EditPage/Template:Game theory"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Topics_of_game_theory" style="font-size:114%;margin:0 4em">Topics of <a href="/wiki/Game_theory" title="Game theory">game theory</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Definitions</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Congestion_game" title="Congestion game">Congestion game</a></li> <li><a href="/wiki/Cooperative_game_theory" title="Cooperative game theory">Cooperative game</a></li> <li><a href="/wiki/Determinacy" title="Determinacy">Determinacy</a></li> <li><a href="/wiki/Escalation_of_commitment" title="Escalation of commitment">Escalation of commitment</a></li> <li><a href="/wiki/Extensive-form_game" title="Extensive-form game">Extensive-form game</a></li> <li><a href="/wiki/First-player_and_second-player_win" title="First-player and second-player win">First-player and second-player win</a></li> <li><a class="mw-selflink selflink">Game complexity</a></li> <li><a href="/wiki/Graphical_game_theory" title="Graphical game theory">Graphical game</a></li> <li><a href="/wiki/Hierarchy_of_beliefs" title="Hierarchy of beliefs">Hierarchy of beliefs</a></li> <li><a href="/wiki/Information_set_(game_theory)" title="Information set (game theory)">Information set</a></li> <li><a href="/wiki/Normal-form_game" title="Normal-form game">Normal-form game</a></li> <li><a href="/wiki/Preference_(economics)" title="Preference (economics)">Preference</a></li> <li><a href="/wiki/Sequential_game" title="Sequential game">Sequential game</a></li> <li><a href="/wiki/Simultaneous_game" title="Simultaneous game">Simultaneous game</a></li> <li><a href="/wiki/Simultaneous_action_selection" title="Simultaneous action selection">Simultaneous action selection</a></li> <li><a href="/wiki/Solved_game" title="Solved game">Solved game</a></li> <li><a href="/wiki/Succinct_game" title="Succinct game">Succinct game</a></li> <li><a href="/wiki/Mechanism_design" title="Mechanism design">Mechanism design</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Economic_equilibrium" title="Economic equilibrium">Equilibrium</a><br /><a href="/wiki/Solution_concept" title="Solution concept">concepts</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bayes_correlated_equilibrium" title="Bayes correlated equilibrium">Bayes correlated equilibrium</a></li> <li><a href="/wiki/Bayesian_Nash_equilibrium" class="mw-redirect" title="Bayesian Nash equilibrium">Bayesian Nash equilibrium</a></li> <li><a href="/wiki/Berge_equilibrium" title="Berge equilibrium">Berge equilibrium</a></li> <li><a href="/wiki/Core_(game_theory)" title="Core (game theory)"> Core</a></li> <li><a href="/wiki/Correlated_equilibrium" title="Correlated equilibrium">Correlated equilibrium</a></li> <li><a href="/wiki/Coalition-proof_Nash_equilibrium" title="Coalition-proof Nash equilibrium">Coalition-proof Nash equilibrium</a></li> <li><a href="/wiki/Epsilon-equilibrium" title="Epsilon-equilibrium">Epsilon-equilibrium</a></li> <li><a href="/wiki/Evolutionarily_stable_strategy" title="Evolutionarily stable strategy">Evolutionarily stable strategy</a></li> <li><a href="/wiki/Gibbs_measure" title="Gibbs measure">Gibbs equilibrium</a></li> <li><a href="/wiki/Mertens-stable_equilibrium" title="Mertens-stable equilibrium">Mertens-stable equilibrium</a></li> <li><a href="/wiki/Markov_perfect_equilibrium" title="Markov perfect equilibrium">Markov perfect equilibrium</a></li> <li><a href="/wiki/Nash_equilibrium" title="Nash equilibrium">Nash equilibrium</a></li> <li><a href="/wiki/Pareto_efficiency" title="Pareto efficiency">Pareto efficiency</a></li> <li><a href="/wiki/Perfect_Bayesian_equilibrium" title="Perfect Bayesian equilibrium">Perfect Bayesian equilibrium</a></li> <li><a href="/wiki/Proper_equilibrium" title="Proper equilibrium">Proper equilibrium</a></li> <li><a href="/wiki/Quantal_response_equilibrium" title="Quantal response equilibrium">Quantal response equilibrium</a></li> <li><a href="/wiki/Quasi-perfect_equilibrium" title="Quasi-perfect equilibrium">Quasi-perfect equilibrium</a></li> <li><a href="/wiki/Risk_dominance" title="Risk dominance">Risk dominance</a></li> <li><a href="/wiki/Satisfaction_equilibrium" title="Satisfaction equilibrium">Satisfaction equilibrium</a></li> <li><a href="/wiki/Self-confirming_equilibrium" title="Self-confirming equilibrium">Self-confirming equilibrium</a></li> <li><a href="/wiki/Sequential_equilibrium" title="Sequential equilibrium">Sequential equilibrium</a></li> <li><a href="/wiki/Shapley_value" title="Shapley value">Shapley value</a></li> <li><a href="/wiki/Strong_Nash_equilibrium" title="Strong Nash equilibrium">Strong Nash equilibrium</a></li> <li><a href="/wiki/Subgame_perfect_equilibrium" title="Subgame perfect equilibrium">Subgame perfection</a></li> <li><a href="/wiki/Trembling_hand_perfect_equilibrium" title="Trembling hand perfect equilibrium">Trembling hand equilibrium</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Strategy_(game_theory)" title="Strategy (game theory)">Strategies</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Appeasement" title="Appeasement">Appeasement</a></li> <li><a href="/wiki/Backward_induction" title="Backward induction">Backward induction</a></li> <li><a href="/wiki/Bid_shading" title="Bid shading">Bid shading</a></li> <li><a href="/wiki/Collusion" title="Collusion">Collusion</a></li> <li><a href="/wiki/Cheap_talk" title="Cheap talk">Cheap talk</a></li> <li><a href="/wiki/De-escalation" title="De-escalation">De-escalation</a></li> <li><a href="/wiki/Deterrence_theory" title="Deterrence theory">Deterrence</a></li> <li><a href="/wiki/Conflict_escalation" title="Conflict escalation">Escalation</a></li> <li><a href="/wiki/Forward_induction" class="mw-redirect" title="Forward induction">Forward induction</a></li> <li><a href="/wiki/Grim_trigger" title="Grim trigger">Grim trigger</a></li> <li><a href="/wiki/Markov_strategy" title="Markov strategy">Markov strategy</a></li> <li><a href="/wiki/Pairing_strategy" title="Pairing strategy">Pairing strategy</a></li> <li><a href="/wiki/Strategic_dominance" title="Strategic dominance">Dominant strategies</a></li> <li><a href="/wiki/Strategy_(game_theory)" title="Strategy (game theory)">Pure strategy</a></li> <li><a href="/wiki/Strategy_(game_theory)#Mixed_strategy" title="Strategy (game theory)">Mixed strategy</a></li> <li><a href="/wiki/Strategy-stealing_argument" title="Strategy-stealing argument">Strategy-stealing argument</a></li> <li><a href="/wiki/Tit_for_tat" title="Tit for tat">Tit for tat</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Category:Game_theory_game_classes" title="Category:Game theory game classes">Classes<br />of games</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Auction" title="Auction">Auction</a></li> <li><a href="/wiki/Bargaining_problem" class="mw-redirect" title="Bargaining problem">Bargaining problem</a></li> <li><a href="/wiki/Global_game" title="Global game">Global game</a></li> <li><a href="/wiki/Intransitive_game" title="Intransitive game">Intransitive game</a></li> <li><a href="/wiki/Mean-field_game_theory" title="Mean-field game theory">Mean-field game</a></li> <li><a href="/wiki/N-player_game" title="N-player game"><i>n</i>-player game</a></li> <li><a href="/wiki/Perfect_information" title="Perfect information">Perfect information</a></li> <li><a href="/wiki/Poisson_games" class="mw-redirect" title="Poisson games">Large Poisson game</a></li> <li><a href="/wiki/Potential_game" title="Potential game">Potential game</a></li> <li><a href="/wiki/Repeated_game" title="Repeated game">Repeated game</a></li> <li><a href="/wiki/Screening_game" title="Screening game">Screening game</a></li> <li><a href="/wiki/Signaling_game" title="Signaling game">Signaling game</a></li> <li><a href="/wiki/Strictly_determined_game" title="Strictly determined game">Strictly determined game</a></li> <li><a href="/wiki/Stochastic_game" title="Stochastic game">Stochastic game</a></li> <li><a href="/wiki/Symmetric_game" title="Symmetric game">Symmetric game</a></li> <li><a href="/wiki/Zero-sum_game" title="Zero-sum game">Zero-sum game</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/List_of_games_in_game_theory" title="List of games in game theory">Games</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Go_(game)" title="Go (game)">Go</a></li> <li><a href="/wiki/Chess" title="Chess">Chess</a></li> <li><a href="/wiki/Infinite_chess" title="Infinite chess">Infinite chess</a></li> <li><a href="/wiki/Draughts" class="mw-redirect" title="Draughts">Checkers</a></li> <li><a href="/wiki/All-pay_auction" title="All-pay auction">All-pay auction</a></li> <li><a href="/wiki/Prisoner%27s_dilemma" title="Prisoner's dilemma">Prisoner's dilemma</a></li> <li><a href="/wiki/Gift-exchange_game" title="Gift-exchange game">Gift-exchange game</a></li> <li><a href="/wiki/Optional_prisoner%27s_dilemma" title="Optional prisoner's dilemma">Optional prisoner's dilemma</a></li> <li><a href="/wiki/Traveler%27s_dilemma" title="Traveler's dilemma">Traveler's dilemma</a></li> <li><a href="/wiki/Coordination_game" title="Coordination game">Coordination game</a></li> <li><a href="/wiki/Chicken_(game)" title="Chicken (game)">Chicken</a></li> <li><a href="/wiki/Centipede_game" title="Centipede game">Centipede game</a></li> <li><a href="/wiki/Lewis_signaling_game" title="Lewis signaling game">Lewis signaling game</a></li> <li><a href="/wiki/Volunteer%27s_dilemma" title="Volunteer's dilemma">Volunteer's dilemma</a></li> <li><a href="/wiki/Dollar_auction" title="Dollar auction">Dollar auction</a></li> <li><a href="/wiki/Battle_of_the_sexes_(game_theory)" title="Battle of the sexes (game theory)">Battle of the sexes</a></li> <li><a href="/wiki/Stag_hunt" title="Stag hunt">Stag hunt</a></li> <li><a href="/wiki/Matching_pennies" title="Matching pennies">Matching pennies</a></li> <li><a href="/wiki/Ultimatum_game" title="Ultimatum game">Ultimatum game</a></li> <li><a href="/wiki/Electronic_mail_game" title="Electronic mail game">Electronic mail game</a></li> <li><a href="/wiki/Rock_paper_scissors" title="Rock paper scissors">Rock paper scissors</a></li> <li><a href="/wiki/Pirate_game" title="Pirate game">Pirate game</a></li> <li><a href="/wiki/Dictator_game" title="Dictator game">Dictator game</a></li> <li><a href="/wiki/Public_goods_game" title="Public goods game">Public goods game</a></li> <li><a href="/wiki/Blotto_game" title="Blotto game">Blotto game</a></li> <li><a href="/wiki/War_of_attrition_(game)" title="War of attrition (game)">War of attrition</a></li> <li><a href="/wiki/El_Farol_Bar_problem" title="El Farol Bar problem">El Farol Bar problem</a></li> <li><a href="/wiki/Fair_division" title="Fair division">Fair division</a></li> <li><a href="/wiki/Fair_cake-cutting" title="Fair cake-cutting">Fair cake-cutting</a></li> <li><a href="/wiki/Bertrand_competition" title="Bertrand competition">Bertrand competition</a></li> <li><a href="/wiki/Cournot_competition" title="Cournot competition">Cournot competition</a></li> <li><a href="/wiki/Stackelberg_competition" title="Stackelberg competition">Stackelberg competition</a></li> <li><a href="/wiki/Deadlock_(game_theory)" title="Deadlock (game theory)">Deadlock</a></li> <li><a href="/wiki/Unscrupulous_diner%27s_dilemma" title="Unscrupulous diner's dilemma">Diner's dilemma</a></li> <li><a href="/wiki/Guess_2/3_of_the_average" title="Guess 2/3 of the average">Guess 2/3 of the average</a></li> <li><a href="/wiki/Kuhn_poker" title="Kuhn poker">Kuhn poker</a></li> <li><a href="/wiki/Bargaining_problem" class="mw-redirect" title="Bargaining problem">Nash bargaining game</a></li> <li><a href="/wiki/Induction_puzzles" title="Induction puzzles">Induction puzzles</a></li> <li><a href="/wiki/Dictator_game#Trust_game" title="Dictator game">Trust game</a></li> <li><a href="/wiki/Princess_and_monster_game" title="Princess and monster game">Princess and monster game</a></li> <li><a href="/wiki/Rendezvous_problem" title="Rendezvous problem">Rendezvous problem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aumann%27s_agreement_theorem" title="Aumann's agreement theorem">Aumann's agreement theorem</a></li> <li><a href="/wiki/Folk_theorem_(game_theory)" title="Folk theorem (game theory)">Folk theorem</a></li> <li><a href="/wiki/Minimax" title="Minimax">Minimax theorem</a></li> <li><a href="/wiki/Nash_equilibrium" title="Nash equilibrium">Nash's theorem</a></li> <li><a href="/wiki/Negamax" title="Negamax">Negamax theorem</a></li> <li><a href="/wiki/Purification_theorem" title="Purification theorem">Purification theorem</a></li> <li><a href="/wiki/Revelation_principle" title="Revelation principle">Revelation principle</a></li> <li><a href="/wiki/Sprague%E2%80%93Grundy_theorem" title="Sprague–Grundy theorem">Sprague–Grundy theorem</a></li> <li><a href="/wiki/Zermelo%27s_theorem_(game_theory)" title="Zermelo's theorem (game theory)">Zermelo's theorem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key<br />figures</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Albert_W._Tucker" title="Albert W. Tucker">Albert W. Tucker</a></li> <li><a href="/wiki/Amos_Tversky" title="Amos Tversky">Amos Tversky</a></li> <li><a href="/wiki/Antoine_Augustin_Cournot" title="Antoine Augustin Cournot">Antoine Augustin Cournot</a></li> <li><a href="/wiki/Ariel_Rubinstein" title="Ariel Rubinstein">Ariel Rubinstein</a></li> <li><a href="/wiki/Claude_Shannon" title="Claude Shannon">Claude Shannon</a></li> <li><a href="/wiki/Daniel_Kahneman" title="Daniel Kahneman">Daniel Kahneman</a></li> <li><a href="/wiki/David_K._Levine" title="David K. Levine">David K. Levine</a></li> <li><a href="/wiki/David_M._Kreps" title="David M. Kreps">David M. Kreps</a></li> <li><a href="/wiki/Donald_B._Gillies" title="Donald B. Gillies">Donald B. Gillies</a></li> <li><a href="/wiki/Drew_Fudenberg" title="Drew Fudenberg">Drew Fudenberg</a></li> <li><a href="/wiki/Eric_Maskin" title="Eric Maskin">Eric Maskin</a></li> <li><a href="/wiki/Harold_W._Kuhn" title="Harold W. Kuhn">Harold W. Kuhn</a></li> <li><a href="/wiki/Herbert_A._Simon" title="Herbert A. Simon">Herbert Simon</a></li> <li><a href="/wiki/Herv%C3%A9_Moulin" title="Hervé Moulin">Hervé Moulin</a></li> <li><a href="/wiki/John_Conway" class="mw-redirect" title="John Conway">John Conway</a></li> <li><a href="/wiki/Jean_Tirole" title="Jean Tirole">Jean Tirole</a></li> <li><a href="/wiki/Jean-Fran%C3%A7ois_Mertens" title="Jean-François Mertens">Jean-François Mertens</a></li> <li><a href="/wiki/Jennifer_Tour_Chayes" title="Jennifer Tour Chayes">Jennifer Tour Chayes</a></li> <li><a href="/wiki/John_Harsanyi" title="John Harsanyi">John Harsanyi</a></li> <li><a href="/wiki/John_Maynard_Smith" title="John Maynard Smith">John Maynard Smith</a></li> <li><a href="/wiki/John_Forbes_Nash_Jr." title="John Forbes Nash Jr.">John Nash</a></li> <li><a href="/wiki/John_von_Neumann" title="John von Neumann">John von Neumann</a></li> <li><a href="/wiki/Kenneth_Arrow" title="Kenneth Arrow">Kenneth Arrow</a></li> <li><a href="/wiki/Kenneth_Binmore" title="Kenneth Binmore">Kenneth Binmore</a></li> <li><a href="/wiki/Leonid_Hurwicz" title="Leonid Hurwicz">Leonid Hurwicz</a></li> <li><a href="/wiki/Lloyd_Shapley" title="Lloyd Shapley">Lloyd Shapley</a></li> <li><a href="/wiki/Melvin_Dresher" title="Melvin Dresher">Melvin Dresher</a></li> <li><a href="/wiki/Merrill_M._Flood" title="Merrill M. Flood">Merrill M. Flood</a></li> <li><a href="/wiki/Olga_Bondareva" title="Olga Bondareva">Olga Bondareva</a></li> <li><a href="/wiki/Oskar_Morgenstern" title="Oskar Morgenstern">Oskar Morgenstern</a></li> <li><a href="/wiki/Paul_Milgrom" title="Paul Milgrom">Paul Milgrom</a></li> <li><a href="/wiki/Peyton_Young" title="Peyton Young">Peyton Young</a></li> <li><a href="/wiki/Reinhard_Selten" title="Reinhard Selten">Reinhard Selten</a></li> <li><a href="/wiki/Robert_Axelrod_(political_scientist)" title="Robert Axelrod (political scientist)">Robert Axelrod</a></li> <li><a href="/wiki/Robert_Aumann" title="Robert Aumann">Robert Aumann</a></li> <li><a href="/wiki/Robert_B._Wilson" title="Robert B. Wilson">Robert B. Wilson</a></li> <li><a href="/wiki/Roger_Myerson" title="Roger Myerson">Roger Myerson</a></li> <li><a href="/wiki/Samuel_Bowles_(economist)" title="Samuel Bowles (economist)"> Samuel Bowles</a></li> <li><a href="/wiki/Suzanne_Scotchmer" title="Suzanne Scotchmer">Suzanne Scotchmer</a></li> <li><a href="/wiki/Thomas_Schelling" title="Thomas Schelling">Thomas Schelling</a></li> <li><a href="/wiki/William_Vickrey" title="William Vickrey">William Vickrey</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Search optimizations</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">Alpha–beta pruning</a></li> <li><a href="/wiki/Aspiration_window" title="Aspiration window">Aspiration window</a></li> <li><a href="/wiki/Principal_variation_search" title="Principal variation search">Principal variation search</a></li> <li><a href="/wiki/Max%5En_algorithm" title="Max^n algorithm">max^n algorithm</a></li> <li><a href="/wiki/Paranoid_algorithm" title="Paranoid algorithm">Paranoid algorithm</a></li> <li><a href="/wiki/Lazy_SMP" title="Lazy SMP">Lazy SMP</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Miscellaneous</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bounded_rationality" title="Bounded rationality">Bounded rationality</a></li> <li><a href="/wiki/Combinatorial_game_theory" title="Combinatorial game theory">Combinatorial game theory</a></li> <li><a href="/wiki/Confrontation_analysis" title="Confrontation analysis">Confrontation analysis</a></li> <li><a href="/wiki/Coopetition" title="Coopetition">Coopetition</a></li> <li><a href="/wiki/Evolutionary_game_theory" title="Evolutionary game theory">Evolutionary game theory</a></li> <li><a href="/wiki/Glossary_of_game_theory" title="Glossary of game theory">Glossary of game theory</a></li> <li><a href="/wiki/List_of_game_theorists" title="List of game theorists">List of game theorists</a></li> <li><a href="/wiki/List_of_games_in_game_theory" title="List of games in game theory">List of games in game theory</a></li> <li><a href="/wiki/No-win_situation" title="No-win situation">No-win situation</a></li> <li><a href="/wiki/Topological_game" title="Topological game">Topological game</a></li> <li><a href="/wiki/Tragedy_of_the_commons" title="Tragedy of the commons">Tragedy of the commons</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Game_complexity&oldid=1246673284">https://en.wikipedia.org/w/index.php?title=Game_complexity&oldid=1246673284</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Combinatorial_game_theory" title="Category:Combinatorial game theory">Combinatorial game theory</a></li><li><a href="/wiki/Category:Game_theory" title="Category:Game theory">Game theory</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Use_mdy_dates_from_May_2023" title="Category:Use mdy dates from May 2023">Use mdy dates from May 2023</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 20 September 2024, at 11:17<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Game_complexity&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.canary-84779d6bf6-wmcb5","wgBackendResponseTime":112,"wgPageParseReport":{"limitreport":{"cputime":"0.681","walltime":"0.860","ppvisitednodes":{"value":3410,"limit":1000000},"postexpandincludesize":{"value":133204,"limit":2097152},"templateargumentsize":{"value":1766,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":218229,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 676.042 1 -total"," 54.89% 371.080 2 Template:Reflist"," 16.20% 109.515 10 Template:Cite_thesis"," 15.48% 104.671 1 Template:Game_theory"," 15.12% 102.238 1 Template:Navbox"," 11.68% 78.929 18 Template:Cite_journal"," 10.68% 72.230 1 Template:Short_description"," 10.45% 70.650 1 Template:Sticky_header"," 7.25% 49.042 12 Template:Cite_web"," 6.55% 44.252 2 Template:Pagetype"]},"scribunto":{"limitreport-timeusage":{"value":"0.367","limit":"10.000"},"limitreport-memusage":{"value":5432304,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-gcdjm","timestamp":"20241122140743","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Game complexity","url":"https:\/\/en.wikipedia.org\/wiki\/Game_complexity","sameAs":"http:\/\/www.wikidata.org\/entity\/Q903738","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q903738","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-09-13T10:39:40Z","dateModified":"2024-09-20T11:17:20Z","headline":"notion in combinatorial game theory"}</script> </body> </html>