![\"tic-tac-toe.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_321.png?resize=292%2C198\")
<\/p>\n<\/p>\n
Moving on from simple zero-sum games, there are a bunch of directions in which
\nwe can go. So far, the games we’ve looked at are very restrictive. Beyond the
\nzero-sum property, they’re built on a set of fundamental properties which ultimately
\nreduce to the idea that no player ever has an information advantage over any other
\nplayer: the complete payoff matrix is known by all players; no player gets
\nto see the other players strategy before selecting their own; and so on.<\/p>\n
Moving on to more interesting games, we can relax those assumptions, and allow information to be hidden. Perhaps each player can see a different part of the
\npayoff matrix. Perhaps they take turns, so that one player gets to see the others
\nstrategy before selecting his own. Perhaps the game isn’t zero-sum. <\/p>\n
Non-zero sum games turn out to be disappointing from a game theory point of
\nview. Given a suitable set of restrictions, you can convert a non-zero-sum game to a
\nzero-sum game with an additional player. In the cases where you can’t do that,
\nyou’re pretty much stuck – the mathematical tools that work well for analyzing
\nzero-sum games often simply don’t work once you relax the zero-sum requirement.<\/p>\n
The more interesting ways of exploring different realms of games comes when you This makes things much more interesting. The easiest way to think of it is <\/p>\n As usual, it’s easiest to see this with an example. At the top of this post is the game tree for tic-tac-toe, assuming that “X” goes first.<\/p>\n There are really three moves that X can make initially – she can play a corner, How can you solve a game like this?<\/p>\n Ultimately, it comes down to utility functions. You can build up a utility Computing the utilities in tic-tac-toe is easy: the utility of any move is the The problem with this approach is that game trees grow incredibly quickly. Even with all symmetries eliminated, the game tree for tic-tac-toe has approximately 25,000 nodes! That means that for a human, the complete game tree isn’t really understandable, even for a trivial game like tic-tac-toe. When Obviously, we can’t compute the whole game tree for games like that. And without the full tree, we can’t calculate precise utility for every possible move. So we Heuristics is the use of what you could call intelligent guesses. There Prunings can be thought of as a sort of heuristic. The idea is that Board valuations are ways of looking at a given game situation, and assigning Board valuations are particularly important when combined with partial trees. The idea of a partial tree is that the full game tree is impossibly large. So you only consider a small part of it. This is very common in chess-playing programs. The So where do we go from here in our exploration of game theory? There’s more Moving on from simple zero-sum games, there are a bunch of directions in which we can go. So far, the games we’ve looked at are very restrictive. Beyond the zero-sum property, they’re built on a set of fundamental properties which ultimately reduce to the idea that no player ever has an information advantage over any […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[88],"tags":[],"class_list":["post-663","post","type-post","status-publish","format-standard","hentry","category-game-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aH","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=663"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/663\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nallow things to get more complex. This comes about when you allow a players strategy
\nselection to alter the game<\/em>. This general takes place in a turn-taking
\ngame, where each players strategy selection alters the game for the other player. A
\nsimple example of this is the game of tic-tac-toe. The set of strategies of the game
\nfor a given player at any point in time is the set of open squares on the board.
\nEach time a player makes a move, the game is altered for the other player.<\/p>\n
\nthat now, instead of a simple matrix for the game, we end up with a tree. Each move
\nthat a player can make creates a new game for the other player. By making each game position a tree node, and adding children nodes for each position that can follow it, you can build a tree describing the complete set of possible game positions, and thus the complete set of ways that the game could play out.<\/p>\n
\na center-edge, or the center. Which corner or edge she chooses is irrelevant – on an empty tic-tac-toe game-board, due to symmetries, the corners\/edges are equivalent. If X plays the center, then the other player can choose either an edge or a corner. If X plays an edge, the O player can play a corner adjacent to X’s move; a corner not adjacent; an adjacent edge; the opposite edge; or the center. And so on.<\/p>\n
\nfunction describing the values of each possible move. This requires some of what I
\ntalked about in my last post with lotteries: most moves produce not a specific
\nresult (win or lose), but a new game. So to compute the utility value of a
\nparticular strategy, you need to combine the utility values of the potential
\nsubsequent strategies resulting from that move.<\/p>\n
\nprobability of your winning the game if you make that move. You determine that by
\nanalyzing the possible moves available to you. First, you can prune the tree: any
\nstrategy that doesn’t include a potential path for you to win, you can just
\neliminate from consideration: it has a utility of 0. For other moves, you look at
\nthe potential paths: if move A leads into a subtree where 72% of the paths lead to a
\nleaf in which you win, then the utility of A is 0.72. Each turn, the best
\nstrategy is the one with the highest utility; moves with equal utility are
\nequivalent.<\/p>\n
\nyou start looking at more interesting games, you get some really astonishingly large game trees. Checkers has a game tree with around 5×1020<\/sup> nodes, after eliminating all symmetries. For Go, the exact size of the tree is unknown – but it’s greater than 10100<\/sup>!<\/p>\n
\nto compute approximate<\/em> utilities. We can compute approximate utility
\nvalues using a variety of techniques, including heuristics, prunings, board valuations, and partial trees.<\/p>\n
\nare moves or positions on most games that are usually sensible. In a game of checkers, if you have an opportunity to either jump and capture one opponents
\npiece, or double-jump and capture two, it’s generally smarter to capture two. Not
\nalways – there are cases where the single jump (and subsequent sacrifice of one of your pieces) is the best move. But most of the time<\/em>, the double-capture is
\npreferable. In the absence of any other information, you’d assign a higher
\nestimated utility to the double-jump. Heuristics also covers some things
\nbased on your knowledge of the other player. People who’ve played chess with me know that I tend to over-use my queen and under-use my knights; if you use that
\nknowledge, you can make intelligent guesses that certain paths in the tree
\nare more likely than others, and use that to weight the likely paths higher
\nin your utility computation.<\/p>\n
\nif you look at the game tree, there are some parts of the tree that lead
\ninto undesirable situations – that is, situations where your probability of
\nwinning is reduced. If it appears that a particular subtree of the game
\nisn’t likely to work out well for you, you just eliminate that entire
\nsubtree. It’s possible that if you searched that subtree, that you might find
\na path that would let you win. But the odds of finding a great winning strategy
\nare small enough that you just cut the subtree away, and don’t search it.<\/p>\n
\nit a value. In chess, a board where your opponent has his king in an unguarded position, you’ve got your queen out on the board where it’s not vulnerable and it’s available to move, and your king is in a castled defensive position is better
\nthan the same position where you’re queen was captured, or where your king is undefended. You don’t need to look further into the game tree to make a strong guess which of those positions is preferable. This comes down to assigning a valuation
\nto a board position without looking further into the tree to compute that
\nvaluation. It’s based solely on immediate, observable properties of the state
\nof the game when you make the valuation.<\/p>\n
\nprogram computes a partial game tree: for example, it may compute 9 levels of the game tree from the current position, which covers the next 9 moves. The states at the leafs of that partial tree are computed by board valuations; the states at internal nodes are computed by combining the values of their children.<\/p>\n
\nto be said about game trees. For example, for most two-player alternative move games, there’s a very particular structure that can efficiently represent the game tree, and provide opportunities for analysis and pruning, called an and-or tree. There are also a set of optimizations based on the fact that in a typical game tree, there are multiple ways that a given board position can be reached. We can compact the game tree into a graph by taking advantage of that.<\/p>\n","protected":false},"excerpt":{"rendered":"