tag:blogger.com,1999:blog-490963843376202302017-11-13T04:52:53.427-08:00Combinatorial Game TheoryThoughts on games (with probably too much computational complexity) updating <strike>every Tuesday and Friday</strike> some days during the school yearKylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.comBlogger256125tag:blogger.com,1999:blog-49096384337620230.post-486274288304804422017-10-26T05:19:00.001-07:002017-10-26T05:19:20.192-07:00Games and Graphs Workshop, Day 1 TalksThe <a href="https://liris.cnrs.fr/gag/workshop/index.html">Games and Graphs Workshop</a> in Lyon was outstanding! There were so many talks, but I think I understood at least the basics of most of them. The first talks were on Monday.<br /><br /><br />Aviezri Fraenkel: "Problems and Results in Combinatorial Games and Combinatorics"<br /><br />Aviezri presented a talk about games with some elements of (Economic) Game Theory (EGT). For example, he considered playing Geography on a binary tree where all terminal nodes are after Alice's turn, except for a great many on the lowest level. At each level, Alice has one instantly-winning move, but what if there are many other moves and Alice can't differentiate between them? Now she is essentially choosing at random because of some hidden information. With enough of these extra edges, she is not going to be able to win the game, despite having a winning option each turn.<br /><br />Aviezri showed many other connections to EGT and called for future work on infinite games in the partizan, scoring, and misere realms.<br /><br /><br />Craig Tennenhouse: "Three Graph Games"<br /><br />Craig presented three new games: Tumbleweeds, Deletion/Contraction, and Total Conversion. Tumbleweeds is a cool variant of Hackenbush without a static root. Instead, whenever a player chooses an edge that breaks the graph up into multiple connected components, that player chooses either of the components to completely discard!<br /><br />The partizan game Deletion/Contraction is played on a multigraph (but no loops). The Left player moves by deleting an edge on their turn, while the Right player chooses an edge to contract (removing any loops that are created).<br /><br />In Total Conversion, the position is a graph with a non-zero game embedded into each edge and each vertex colored either Red or Blue. To take a turn, the player must make a move on each game where the edge has ends colored in opposing colors. Edges with exactly 0 are then removed and both vertices are subsequently repainted with that player's color.<br /><br />Craig already drew attention with these games and, as always, I suspect he has about three new projects as a result of the conference.<br /><br /><br />Loic Cellier: "The Game of Hex"<br /><br />It always seems like there are new things to learn about Hex. Loic presented just about everything I knew and lots that I didn't. He covered the history---I did not know that Einstein was a supporter of the game!---the connection to Y, and even presented a variant of the Pie Rule, the Swap Rule: Here, instead of swapping the identity of the players (if Player 2 wants), instead just swap the color of the piece on the board. This is, of course, not always equivalent; it prevents the first player from playing in a position that would be too good for their opponent as well.<br /><br />I also (finally) learned why a Y game must end, by the self-reduction of each vertex into a hex on a slightly-smaller board. This is surprisingly elegant and easy to explain, but with that little twist that makes it amazing. It may be more likely to be in The Book than the Hex Theorem (that no Hex game can end in a tie.<br /><br /><br />Milos Stojakovic: "Maker-Breaker Games Played on Random Graphs"<br /><br />Milos talked about Positional Games: maker-breaker games on a finite set of elements, X, where F, the winning set, is a subset of the power set of X. The players alternate turns claiming one element of X. Maker then wins if they claim all the elements in some set in F; Breaker wins otherwise. Milos paid special attention games where X is the set of edges in a complete graph.<br /><br />Unfortunately, for many common sets F (e.g. set of Triangles) it is too easy for Maker to win. To balance things out, he considers adding biases for each player to change the frequency of turns. (E.g. Maker takes 3 turns, then Breaker takes 7.) The idea he took off with was to begin the game by removing a number of random edges. If each edge remains with probability p, how low does p have to be before Breaker can (usually) win? He calls this the Threshold Probability, and looked in to determining this value.<br /><br /><br />Mirjana Mikalacki: "Fast Winning in Positional Games on Graphs"<br /><br />Mirjana is also interested in positional games, but is looking for other ways to give Breaker a chance to win. Instead of removing some edges, she considers a "fast" variant where Maker only gets to make a certain number of moves before the game ends in Breaker's favor. (Breaker still gets to move as normal too.)<br /><br />Mirjana also combined this with the biases mentioned above. These "combination" fast games generalize positional games significantly.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-35971907045245164382017-07-30T06:39:00.001-07:002017-07-30T06:39:20.059-07:00Elwyn's CG VideosElwyn Berlekamp's video-talk at Fundy and Games, "A Program of Introductory Videos on Combinatorial Games", alerted me to something I didn't realize: Elwyn's been creating a bunch of videos to introduce CGT. Since the meta-video presentation, I've been watching the videos.<br /><br />He's using some good philosophy towards introducing concepts:<br /><ul><li>Examples come before the abstractions. It's easier to motivate the abstract notions once you've seen some concrete examples.</li><li>Delay notation as long as possible. The non-standard notation used while still showing the initial concepts works just fine. For example, instead of using N and P (outcome classes), the impartial videos start off with just checkmarks (for N-positions) and circles (P).</li></ul>Here's the <a href="https://youtu.be/ndvoTQE92TQ?list=PLj6WGJe-RmYZ-yHrobuCZVjaKHpXTxZOJ">sequence of videos on impartial games</a>. They use an impartial version of chess where each piece occupies it's own board and each piece can only move towards the southwest corner. The first video describes what happens with one King, and the following videos show what happens as other pieces get added, each time adding a new concept to the theory of games.<br /><br />Here's the <a href="https://youtu.be/CqLcYxIg7ww?list=PLj6WGJe-RmYbQwmwQctxA9hNJk19kkzJ_">sequence on partisan games</a>. I haven't watched as many of these yet. <br /><br />These are a great resource for introducing CGT. I'd really like to know how effective these are in a classroom setting (at any level).Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com1tag:blogger.com,1999:blog-49096384337620230.post-23636555472738609372017-07-28T10:58:00.000-07:002017-07-28T10:58:24.098-07:00Game Description: NoCanDoFor the tournament game at Fundy and Games, we played a variant of Domineering known as NoCanDo. (We spent the first day deciding on the name.) This is a very nice mix of Domineering with a little splash of NoGo: each domino on the board must be adjacent to at least one uncovered square. That's it. You're not allowed to play a domino if it would be completely surrounded or if would cause another domino (already played) to be completely surrounded.<br /><br />This little rules change makes a huge difference! <br /><ul><li>You can place pieces aggressively to force an opponent to leave spots open.</li><li>You need three spaces in a line for a free move, instead of two. (And sometimes you can't play in those three anyways because it blocks other dominoes.) Five in a line can often net you two plays, but I don't think I ever had a group worth three.</li><li>The "liberty" rule is still different from Go and NoGo, because each domino needs the free space, not just each connected group of similarly-oriented dominoes.</li><li>When the game breaks up into subregions, sometimes they're not all independent.</li></ul>We held human and computer tournaments at Fundy and Games. RJN won the human tournament, and my program won the computer tournament. Richard handily beat my computer player to win the overall title.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-69407732233807408332017-07-27T09:09:00.001-07:002017-08-14T11:41:56.161-07:00Game Description: SlimetrailOne of the games <a href="http://ludicum.org/">Ludus</a> has used in their national tournaments is <a href="https://boardgamegeek.com/boardgame/31467/slimetrail">Slimetrail</a>. This game is simple enough that it can be played by a wide age range, but there are many complicated strategies that can be used by more advanced players.<br /><br />Slimetrail is played on a connected graph, with one vertex colored Blue, another colored Red, and a third vertex with a moveable piece or token which will create the trail of slime. The two players alternate turns moving the token one space, then marking the previous space (where the token was) a third color (usually green). The token can never be moved back to one of these "slimed" spaces.<br /><br />A player wins when the token is moved onto the space of their color. Since we want to make sure that one player can still win, it's not allowed to move the token to a space where it can't reach at least one of the two goals.<br /><br />In all the examples I've seen, Slimetrail is played on a grid, with adjacencies in all 8 directions. Apparently, it's also played on hex grids.<br /><br />I wrote a <a href="http://turing.plymouth.edu/~kgb1013/combGames/slimeTrail.html">playable version</a> using Javascript. My auto-AI players are terrible at this game, but you can still try it out. In order to make this strictly-combinatorial (the last player wins) I altered the rules slightly so that you can't move to your opponent's goal space. <br /><br />(Edit: the link to the game didn't auto-clickableify, so I added a clickable link.)Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com4tag:blogger.com,1999:blog-49096384337620230.post-25301298442368983382017-07-25T06:17:00.000-07:002017-07-25T06:17:35.521-07:00Fundy & Games 2017: Quick Highlights<a href="http://www2.unb.ca/~nmckay/fundyandgames/">Fundy and Games</a> was excellent! After driving through Saint John three times, I'm really happy that I got to experience it first-hand. I love the fog!<br /><br />Here are some quick highlights (from my perspective):<br /><ul><li>The talks were great! I'll include another post summarizing these.</li><li>I worked with a group that solved a complexity problem on the first full day of working groups. Both of the undergraduates from Plymouth State made significant contributions towards the result!</li><li>The game Richard proposed, NoCanDo, made for a great conference tournament game. (I'll have a separate post describing the game, but it's a variant of Domineering.) </li><li>My students were interested in participating in a NoCanDo computer tournament, so I wrote some code to model the game, then a display to show the progress in the game. To give them something to play against, I wrote a very basic AI (just case-based, with no end-game wrangling). Amie wrote a player with a very similar strategy. In the computer finals, my code squeaked out a victory against her, winning 507 of 1000 games. Yikes!</li><li>Amie also beat me in the human tournament. I had a slightly better record, then got beaten by RJN in the finals. RJN went on to handily defeat my computer player to be the Overall 2017 NoCanDo World Champion!</li><li>I saw the Reversing Falls go backwards! Sweet! (I saw them go forwards last year when we dropped Neil off.)</li><li>Neil and Rebecca McKay were excellent organizers! I greedily ate many of the snacks they provided. They even made certificates for the tournament winners!</li><li>I'm still not sure what a <a href="https://blogs.unb.ca/unbsjathletics/">Seawolf</a> is. </li><li><br /></li><li>I continue to enjoy traveling to Atlantic Canada for games!</li></ul>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-17192275449008459762017-07-17T03:35:00.002-07:002017-07-17T03:35:44.192-07:00Sprouts 2017 Summaries, Session III<span style="font-size: large;"><span style="font-size: small;">After lunch we had three more talks to wrap up <a href="http://turing.plymouth.edu/~kgb1013/sprouts/sprouts2017/">Sprouts 2017</a>.</span> </span><br /><br /><span style="font-size: large;">Matt Ferland: <i>Applying Heuristics in Combinatorial Games</i></span><br /><br />My own student, Matt, explained some of the tactics used by AI to play Chess and Go. He talked about all the different heuristics used to approximate the values of Chess boards (I had no idea how deep this really was) and then gave a good overview of just how far computer Go players have come.<br /><br />I learned a ton from this! It's been great to have a student really interested in exploring Artificial Intelligence.<br /><br /><span style="font-size: large;">Ethan Wester: <i>Protect the King</i></span><br /><br />Ethan presented a game similar to Crab & Gulls. This game is partisan, with two kings (one per player). The bishops, however, now threaten both kings. A turn consists of first moving your own king (like a King does in Chess) to an unthreatened location, then placing a new bishop that threatens the opposing king.<br /><br />Ethan found a bunch of values for this ruleset: all integers, all switches, *, *2, Up, Down, 1/2 and 1/4. Wow!<br /><br /><span style="font-size: large;">Cameron Hodgdon: <i>Analysis of a New All-Small Game: An Introduction to Kanye</i></span><br /><br />Cameron created the game Kanye (I think he named his before Ashlee named "Also Kanye"). This is very similar to Also Kanye, except that all pieces are the same color, so the game is dicotic (all-small). The is still partisan, though: Right chooses a column and moves that column North. Left chooses a row and moves it West.<br /><br />Cameron evaluated games for a bunch of different patterns of starting configurations. Then he even found the atomic weights for these games!<br /><br /><br />As you can see, it was very easy to get excited about all of the great work these undergrads had done!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-3695661697081823192017-07-16T05:43:00.000-07:002017-07-16T05:43:29.265-07:00Sprouts 2017 Summaries, Session II<span style="font-size: large;"><span style="font-size: small;">Two talks were given in the second session at <a href="http://turing.plymouth.edu/~kgb1013/sprouts/sprouts2017/">Sprouts 2017</a>.</span> </span><br /><br /><span style="font-size: large;">Kristen Falcinelli: <i>Undecidability demonstrated by a tiling game</i></span><br /><br />Kristen showed a new game, Infinitiles, where players each have their own library of <a href="https://en.wikipedia.org/wiki/Wang_tile">Wang Tiles</a>. The starting position is a finite or infinite grid with at least one tile already on the board. Each turn consists of a player choosing one of their tiles, then placing a copy of it onto the board somewhere adjacent to one of the tiles already on the board. The placed tile must match all the other tiles it touches.<br /><br />Kristen was able to find many values in the game: all integers, all switches, *, Up, Down, and 1/2. One issue she found was that on an infinite board, it is <a href="https://en.wikipedia.org/wiki/Undecidable_problem">undecidable</a> to determine whether the game will finish on an infinite board!<br /><br /><span style="font-size: large;">Ashlee Tiberio: <i>Also Kanye: Examining patterns in a strip game variant</i></span><br /><br />Ashlee created a grid game similar to Drag Over, but in two dimensions. On a grid with red and blue pieces, you move by choosing a row or column, then you move all pieces in that space. If it's a column, you move all pieces up ("North"); if it's a row, you move all the pieces left ("West"). If the pieces fall off the board, they are removed. You can only make a move if you have pieces left on the board.<br /><br />Ashlee found number values for all 1-by-n strips where either all spaces had a token (of the same color) or one space had a token. She also found values for 1-by-n strips with two tokens of separate colors.<br /><br />Ashlee also noted that the misere version of this game should be called "Imma Let you Finish".Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-88770017991149311182017-07-15T13:54:00.001-07:002017-07-15T13:54:24.339-07:00Sprouts 2017 Summaries, Session IHere are summaries of the first round of presentations from <a href="http://turing.plymouth.edu/~kgb1013/sprouts/sprouts2017/">Sprouts 2017</a>!<br /><br /><span style="font-size: large;">Destiny Martin: <i>The game of Locking Nim</i></span><br /><br />Destiny presented a really cool version of Nim: Locking Nim. The only difference between this and Nim is that players cannot play on heaps of the same size as another heap in the game. First glance: this should be the same as Nim, right? After all, in Nim, two equal-sized heaps cancel out in the Nim-sum. This isn't the same here, though, because there could be three heaps with the same size, and now they're all irrelevant!<br /><br />Destiny found that with three (non-zero) heaps, games are in P exactly when they nim-sum to zero and the piles have unique sizes. If they are not unique, the position is in P exactly if they're all the same size. For four heaps, the regular nim-sum-to-zero property holds for P, whether or not the four piles are unique.<br /><br /><br /><span style="font-size: large;">Nick Paolini: <i>Node Hackenbush disguised as a Chomp variant</i></span><br /><br />Nick modified Hackenbush to create Polar Bear Plunge, a game played on a grid-graph. On one node of the grid sits the polar bear, acting as the ground from Hackenbush. Players take turns removing other nodes (ice bergs) from the graph. If another node is not reachable from the bear, it disappears too.<br /><i> </i><br />Nick determined formulas for all 1-by-n and 2-by-n boards, no matter where the bear is located. For other n-by-m grids (both greater than 2), all you need to know is the parity: the game is equal to * if n times m is even, and 0 otherwise!<br /><br /><span style="font-size: large;">Emilee Jurkowski: <i>Crab & Gulls</i></span><br /><br />Emilee built a variant of Queens: a game where players alternate turns placing non-threatening Queens onto a chessboard. Crab and Gulls is similar, except that Bishops (Gulls) are placed instead of Queens and they don't need to threaten each other, but instead <i>must</i> threaten a separate Crab piece. A turn consists of two parts: place a threatening Gull, then move crab to any other space (not necessarily adjacent) that isn't threatened. (Both parts of the move need to be completed.) She came up with two further variants: King & Gulls (the Crab moves like a King) and Rock & Gulls (Crab doesn't move, but each new Gull needs to threaten it).<br /><br />Emilee calculated the nimbers for all Crab & Gulls starting positions on a 2-by-{2, ..., 8}, 3-by-{3, 4, 5, 6}, and 4-by-{4, 5}. She also found the King & Gulls nimbers for starting boards for 2-by-{2, .., 11}, 3x{3, ... 7}, and 4-by-{4, 5}. For Rock & Gulls, she realized that this game is just equivalent to Nim with 4 heaps.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-17582896273091043042017-06-15T14:59:00.001-07:002017-06-15T14:59:05.665-07:00Game Description: Cutthroat and Impartial CutthroatA long time back, while going through Lessons in Play, I got hung up on the definition of Impartial Cutthroat in section 2.2. I completely forgot about this until recently, when a student asked me to explain what was going on. Today, I had a look back at Cutthroat and Impartial Cutthroat and confirmed my understanding with Richard Nowakowski. In this post, I'll try to clarify both games.<br /><br />Cutthroat is a partisan game played on a graph where each vertex is colored Blue or Red. In addition, each connected component of the graph must include vertices of both colors. Each turn a player chooses one of the vertices of their color and removes it from the board, including all incident edges. Then, remove any connected component that includes only vertices of one color.<br /><br />Here's a whiteboard sketch of a Cutthroat game tree I made today:<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-UlFxZ-Je5EE/WUL87bgiPJI/AAAAAAAAfPk/WwgqM0sRzAMaat4aKyPmVRwNwW-exyHpACKgBGAs/s1600/20170615_144519.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1434" data-original-width="1600" height="286" src="https://4.bp.blogspot.com/-UlFxZ-Je5EE/WUL87bgiPJI/AAAAAAAAfPk/WwgqM0sRzAMaat4aKyPmVRwNwW-exyHpACKgBGAs/s320/20170615_144519.jpg" width="320" /></a></div><div style="text-align: left;"> </div><div style="text-align: left;">Notice that Red has an immediate move to zero by choosing the lower red vertex. (The remaining two connected components are both mono-colored, so they are immediately removed.)</div><div style="text-align: left;"><br /></div><div style="text-align: left;">I've added this as it's own <a href="http://turing.plymouth.edu/~kgb1013/rulesetTable.php#Cutthroat">entry in the ruleset table</a>.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">Impartial Cutthroat is a bit different. On one hand, it's the same game if you assume that players can choose vertices of any color AND all vertices are given a unique color. </div><div style="text-align: left;"><br /></div><div style="text-align: left;">Another way to explain it is that a position is an uncolored graph where each vertex must have at least one neighbor. On a player's turn, they choose a vertex and remove it and all incident edges. Afterwards, all vertices with no neighbors are also removed.</div><div style="text-align: left;"><br /></div><div style="text-align: left;">Yet another way to explain Impartial Cutthroat is by considering it as a variant of Node Kayles. In Kayles, a player chooses a vertex, then removes that vertex and all of its direct neighbors. Here, there are two differences:</div><div style="text-align: left;"><ul><li>The player must choose a vertex that has at least one neighbor.</li><li>Only the chosen vertex is removed, not any of the neighbors.</li></ul></div><div class="separator" style="clear: both; text-align: left;">Because of this similarity, I've included it in the ruleset table as a <a href="http://turing.plymouth.edu/~kgb1013/rulesetTable.php#Impartial%20Cutthroat">variant of Node Kayles</a>, instead of a standalone game or a variant of Cutthroat.</div>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-17476156555348168932017-05-01T05:28:00.000-07:002017-05-01T05:28:49.564-07:00Sprouts 2017: Overall AwesomenessI spent all Saturday at Sprouts 2017, and it was excellent!<br /><br />Craig Tennenhouse organized an amazing experience. Everyone got a Gamester Pen, a program with a CGT quick-reference-page, a grid-lined notebook decked out with a gamey cover, and a nametag with the logo.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-eX91iROYbGo/WQZv2PCnccI/AAAAAAAAd2c/nQLVRXCq8ow13s5lGgfEc-dtpdFao4NTACKgB/s1600/20170430_190630.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://1.bp.blogspot.com/-eX91iROYbGo/WQZv2PCnccI/AAAAAAAAd2c/nQLVRXCq8ow13s5lGgfEc-dtpdFao4NTACKgB/s320/20170430_190630.jpg" width="180" /></a></div><div style="text-align: center;"> Official Sprouts Notebook</div><br />His students gave amazing talks. Each had created their own game, complete with actual pieces they had 3-D printed or otherwise manufactured! It was clear they had spent lots of time analyzing their games, and had learned CGSuite to help get results. One student had learned about Atomic Weights and applied that theory to their analysis!<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://4.bp.blogspot.com/-8G3GvZqoHyE/WQZwpG1cu8I/AAAAAAAAd2o/0m6KaQ0sXa0slvLnckwdtnrJtymdLmhDwCKgB/s1600/20170429_111607.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="180" src="https://4.bp.blogspot.com/-8G3GvZqoHyE/WQZwpG1cu8I/AAAAAAAAd2o/0m6KaQ0sXa0slvLnckwdtnrJtymdLmhDwCKgB/s320/20170429_111607.jpg" width="320" /></a></div><div style="text-align: center;">Infinitiles</div><br />My student, Matt, also gave an excellent talk. He discussed AI methods to play Chess and Go. After all the talks, we got into working groups and looked at a few games more deeply. I am definitely convinced that undergraduates can contribute to this field!<br /><br />I'll post comments about the individual talks, though that may have to wait until the semester wraps up. In the meantime, I've already started dreaming about Sprouts 2018.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-89684844223065688812017-04-23T17:33:00.001-07:002017-04-23T17:33:18.403-07:00Sprouts 2017: A CGT Conference for UndergradsExciting news for New England Gamesters: Craig Tennenhouse is organizing the first Sprouts, a conference for undergrad CGT research. (I helped by making the website.) <a href="http://turing.plymouth.edu/~kgb1013/sprouts/sprouts2017/">Sprouts 2017</a> will take place at the University of New England (Biddeford, ME) on April 29. The basic plan is to continue hosting Sprouts every year at either UNE or Plymouth State (NH).<br /><br />I know this announcement is a bit late, but things have come together only recently. Inspired by our desire to get our gamester undergrads involved in research, we're harnessing the opportunity presented by Craig's research class.<br /><br />Hopefully in the future, we'll be able to get the word out sooner to attract visitors from the region.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-44753265050319308982017-01-02T10:18:00.003-08:002017-01-02T10:18:47.067-08:00CGT Facebook groupSimon Rubinstein-Salzedo started a Combinatorial Game Theory Facebook group! Join us here: https://www.facebook.com/groups/413534538978745/<br /><br />Happy New Year!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-12336829555357009112016-12-30T05:26:00.005-08:002016-12-30T05:26:48.943-08:00All I want for Christmas is TweetsIn 2016, I joined the technology era of 2006 by getting myself a Wii and now a Twitter account. Hooray!<br /><br />This summer, I promised myself that I would sign up for Twitter after I submitted my tenure portfolio. Well, I turned that all in back in October, so this is overdue. Here's my Twitter-Sphere Presence: <a href="https://twitter.com/CGTKyle">CGTKyle</a><br /><br />I find myself noticing CGT things that don't quite warrant an entire blog post. Then I forget about those things. Now I can quickly say something about them in an attempt to garner attention.<br /><br />I expect that I'll also be tweeting about general board games, teaching, voting systems, CS and math, and more. Yikes.<br /><br />My first tweet announced a little page I made for CGT events: http://turing.plymouth.edu/~kgb1013/CGTMeetings.php I realized that I always needed the links to these previous and coming events. As is common for me, I coded the whole thing up in Javascript (feel free to look at the underlying code) so events like <a href="http://cgtc.eu/2/">CGTC II</a> is currently in the "Future" section, but should move to "Past" after it's happened. We'll see whether I did that right. (Also, you should all be going to CGTC2! I'm very disappointed that I'll be missing it.)<br /><br />I think I'm missing some meetings on there (there was something at Kamloops a few years back, I believe) so help me fill it out. I hope there's something coming up this summer also (I think Games at Dal will have to wait until 2018.)<br /><br />Happy New Year!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com6tag:blogger.com,1999:blog-49096384337620230.post-4413124701055988292016-12-01T07:35:00.001-08:002016-12-01T07:35:20.592-08:00 LaTeXing Lecture NotesI've been working hard the past 2.5 years teaching a bunch of new courses and improving old courses. One of the things that's helped a ton is converting hand-written lecture notes into LaTeX. <br /><br />Many years ago, I started working on a style file to add a bunch of commands for lecture notes. Most important, I created a question command to facilitate Socratic-style lectures. I later modified this so that I could set a flag indicating that the output was for students. Then it would hide the answers to those questions. I started posting these versions online for students.<br /><br />I've been adding stuff to this, but recently really wished I could add exercises that would put all the answers in an appendix, but hide those answers in the student version. I recently discovered the <a href="https://www.ctan.org/tex-archive/macros/latex/contrib/exercise">exercise package</a> (thanks, <a href="http://tex.stackexchange.com/questions/301/how-can-i-produce-exercises-in-one-part-of-a-latex-document-with-selected-answer">Stack Exchange</a>) which can do this automatically. Using that, I updated my style file, and recently posted the code on <a href="https://github.com/paithan/LaTeX-LectureNotes">GitHub</a>. (If you're not familiar with GitHub, I made my own <a href="http://turing.plymouth.edu/~kgb1013/lectureNotesLatexStyle.php">landing page</a>.)<br /><br />I find that it's really convenient to teach from the pdfs on a tablet, and it saves me tons of paper. The only issue is that it's a bit more difficult to make notes on the pdfs than with a regular pen and paper.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-8614482551379223322016-09-30T09:45:00.002-07:002016-09-30T09:45:54.485-07:00Richard Guy is 100<div style="text-align: center;"><span style="font-size: large;">Happy Birthday, Richard Guy!</span> </div><br />Richard Guy turns 100 today. He is one of the authors of the classic text <a href="https://en.wikipedia.org/wiki/Winning_Ways_for_your_Mathematical_Plays">Winning Ways for your Mathematical Plays</a>. At the CGT workshop at BIRS in 2011, he proposed a new subtraction game that I find myself thinking about on and off:<br /><br />Given a pile of n tokens, and a subtraction set, S, each turn, you move to a new position, n (< n'), S', where either:<br /><ul><li>Normal thing: S = S' and n' = n - s, for some s in S or,</li><li>Weird thing: S' = { x } U S and n' = n - x and there are some y and z in S such that x = y + z.</li></ul>...I haven't gotten anywhere with it either.<br /><br />I was alerted to an excellent <a href="https://www.youtube.com/watch?v=2RAalmbDGxM">birthday video</a> for Richard, highlighting his work in Geometry.<br /><br />Richard is one of the nicest people I've ever met, and he continues to be active in research today!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-67116636495522067822016-08-20T07:04:00.003-07:002016-08-20T07:04:26.033-07:00Integers 2016Integers is back!<br /><br />Integers is a conference in combinatorial number theory. Traditionally it's been held every other year on the odd years, but it had to be skipped last year. Integers is a great, low-key conference held at the University of West Georgia. It has an associated electronic journal with no paywalls (so convenient!). It's well run and everyone is very nice. This year, they've moved it up to early October (6th-9th). Here's the official <a href="https://www.westga.edu/academics/cosm/mathematics/assets/docs/intergers-conference-2016.pdf">Integers 2016 announcement</a>.<br /><br />Historically, there's been a contingent of gamesters attending Integers. In 2011, I brought an undergraduate and met many of Richard Nowakowski's students. In 2013, I met Silvia Heubach and Matthieu Dufour.<br /><br />Unfortunately, I don't know of anyone attending Integers this time around. This is partly due to the number of CGT events popping up. Games@Dal has returned, and CGTC2 will be happening in January 2017 in Lisbon.<br /><br />If you're planning to go for Combinatorial Games, please comment below (or email me). At this point, it looks like we might not have any gamester attendees.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-39689567478880607932016-08-17T19:05:00.000-07:002016-08-17T19:05:31.046-07:00Games@Dal 2016: Tanya talks about Cookie Monster GamesGames@Dal 2016 talk: "Cookie Monster Plays Games" - Tanya Khosanova w/Leigh Marie Braswell, Eric Nie, Alok Puranik, Joshua Ziong, and Dhroova Aiylam<br /><br />Tanya Khovanova shared some work with a bunch of <i>high schoolers</i> (whoa!) on patterns in Cookie Monster games. Cookie Monster games are Nim games where k sticks (cookies) can be removed from multiple heaps. Each ruleset has a different restriction on which sets of piles can be removed from.<br /><br />She and her students considered rulesets where you can take from...:<br /><ul><li>No restriction</li><li>One-or-all piles</li><li>One-or-two piles</li><li>Any consecutive piles (assuming the piles are in a list)</li><li>One or two consecutive piles</li><li>Any set of piles including the first jar</li><li>Any odd number of piles. (It turns out that the P positions are the same as in Nim!)</li><li>Any set of piles except all of them.</li><li>... and more!</li></ul><br />In one of these games, she noticed a surprising correlation with an automaton problem! A sequence of the number of P positions is related to the number of new cells born from the Ulam-Warburton automaton. She then looked more closely at other relationships to automaton!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-10010496245502768642016-08-16T13:56:00.000-07:002016-08-16T13:56:25.951-07:00Games@Dal 2016: Urban talks about Drawing TrianglesGames@Dal 2016 talks: "Hopeful Windows in Cellular Automata and Combinatorial Games" - Urban Larsson<br /><br />Urban talked about the Hopeful Window Triangle-Placing Game, a very interesting game based on his work with cellular automata games. In this game, there are multiple steps per turn revolving around drawing a digital 45-45-90 triangle on a grid. The triangle always has one box at the top, and the hypotenuse descends on the left-hand side. There is a single box lower in the grid that is the blocking box: <br /><ul><li>No triangle can be drawn that contains that box, and</li><li>The first player to draw a triangle past that box wins.</li></ul>At the beginning of each turn, there are candidate boxes that the current player can start with are all in a horizontal row. (I'll explain how those are generated as part of the turn below.) The steps to each turn are:<br /><ul><li>The current player chooses one of the candidate boxes for the top of the triangle, then draws it as far down as they want. (If they start out to the left of the blocking box, then they can automatically win by drawing a large-enough triangle. Otherwise, they can't cover up the blocking box.)</li><li>Consider the boxes directly beneath the drawn triangle - the triangle's support, but increase this set by extending to the left and the right by two boxes on each side. (This can be parameterized to be any l and r numbers.)</li><li>Inside of this elongated support, the next player chooses a "hopeful window" of, say, 6 adjacent boxes. (Again, this can be parameterized.)</li><li>The previous player then gets to block, say, 3 of the boxes in that window. (Parameterizeable again.)</li><li>The remaining 3 (in this example) boxes from that window become the candidate top boxes for the next player to choose from on their turn.</li></ul>The game is certainly a bit complex, but Urban found an extremely surprising relationship between this game and automata that generate Sierpinski-Triangle figures. By using the l, r, w (window size), and b (number of block) parameters in the formula for the triangle-creating automata, the resulting pattern of triangles tells you exactly which boxes you should choose to start a new triangle from: choose one of exactly those which remain uncolored in the diagram. Amazing!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-46611572625089922562016-08-15T19:48:00.001-07:002016-08-15T19:48:58.457-07:00Games@Dal 2016: Alda and Carlos talk about Short SumsGames@Dal 2016 talk: "Some notes on Disjunctive Short Sum" - Alda Carvalho & Carlos Santos<br /><br />Alda and Carlos presented their work on Disjunctive Short sums. They started from Paul Ottaway's definition of the difference from a short sum (to a normal long sum): The game ends when a player chooses a component in which they have no legal move. This doesn't make a difference in Normal play (because players don't want to choose one of those games) but it's important for Misere. In misere, this is equivalent to: The game ends when there is a component in which the current player has no legal move.<br /><br />Now, instead of starting from zero as the terminal position, they start with two games that have no options: Infinity (Inf) and negative Infinity (-Inf). Inf is the game with no options for Right, and -Inf has no moves for Left. These are the only games born on day 0. Then the day 1 games are:<br /><ul><li>Inf* = {Inf | Inf}</li><li>+/- Inf = {Inf | -Inf} (like a switch)</li><li>0 = {-Inf | Inf}</li><li>-Inf* = {-Inf | -Inf}</li></ul>They showed a bunch of the birthday lattice for day 2, which is very large, then started talking about Color Nim: a short disjunctive sum of Nim games. Another way to say this is that each pile has a color (not necessarily unique) and the game ends when one of the colors is gone. In the Misere case, this means that each color behaves like Penultimate Nim. (For some reason, Penultimate Nim kept coming up at this meeting!)Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com1tag:blogger.com,1999:blog-49096384337620230.post-82175315466387329802016-08-15T04:53:00.002-07:002016-08-15T05:25:39.218-07:00Games @ Dal 2016 Wrap UpYesterday morning, I put myself and three other Muppets back into my car and departed Games @ Dal. 675 miles, 16 hours (just under 12:45 actually behind the wheel) and three drop-offs later, and I was back at home. <br /><br />There are still more talk summaries to come over the next few days, don't worry. We even had an unexpected bonus talk by Tanya Khovanova on Friday, so there are three more to go! :)<br /><br />Here's a few things I learned:<br /><ul><li>I got a result! It's not about the computational complexity of a game... who am I?</li><li>There are lots of very obvious rulesets that we still need to find the computational complexity for. Even just impartializations or other variations of common rulesets need to be figured out.</li><li>Halifax Citadel's noon gun is loud if you're standing near the citadel entrance. (Good choice, Amie!)</li><li>Hanabi is pronounced differently in Canada.</li><li>CGT is still a really good field to introduce to mathy undergrads. (Also, I should really take a look at Tom Ferguson's book.) </li><li>It would be very nice to have a list of gamesters. I should probably make this.</li><li>It would be very nice to have a list of past and future CGT conferences/events. I should probably make this. </li><li>I should spend more time working on the ruleset table.</li><li>I would really like to go to a workshop where my only job is to update the table. I'd like this to be a CGT event because I'd like to be surrounded by Gamesters while doing it. </li><li>A post on the Gamester Pen would not be worthless.</li><li>I should probably get on Twitter and tweet little things like these.</li></ul>Thanks to Richard Nowkowski, AARMS, and Dalhousie for hosting such a great event!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-9842653409248341722016-08-15T04:53:00.000-07:002016-08-15T04:53:34.674-07:00Games@Dal 2016: Israel talks about PicariaGames@Dal 2016 talk: "Eternal Picaria" - Israel Rocha w/Urban Larsson<br /><br />Israel Rocha presented a new game to me: Picaria. Picaria is a traditional board game of the Zuni tribe from the American southwest, but it also pops up in other parts of the world, including southwest Sweden (known there as a type of Luffarshack). It plays a bit like a Three Mens Morris mixed with Tic-Tac-Toe.<br /><br />Players play on a graph, usually set up in a 3x3 grid like Tic-Tac-Toe, but with diagonal connections as well. In the first six turns, players are playing pieces, trying to make three-in-a-row. After those pieces are played, players instead slide pieces to an adjacent location, still trying to make a line of three.<br /><br />Israel explained that he and Urban Larsson showed that Picaria is a draw, via exhaustive search. (And without a computer!) They then considered some variants, including giving a player more stones and playing on bigger boards.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-53836409507838006322016-08-15T04:49:00.000-07:002016-08-15T04:49:37.116-07:00Games@Dal 2016: Carlos talks about 3-player NimGames@Dal 2016 talk: "3-player Nim with podium rule" - Carlos Santos w/Richard J. Nowakowski and Alexandre M. Silva<br /><br />Carlos's talk entered the somewhat-forbidden world of three-player games. He spoke of different ways of considering these games, but continued using Lee's Podium Rule from 1978: If you can't come in first, you should instead try to come in second. (Try to get as high up the podium as you can.)<br /><br />In impartial games, this leads to a third outcome class: O ("Other") which has no P options, but at least one N option. Playing on Nim heaps, to find P positions, we now have to perform the nim sum, but mod 3 instead of mod 2. Thus, *7 + *17 + *22 + *23 is a P position. Zeroness in the sum only actually tells us about P positions; non-zero values might be O or N, so we need further criteria.<br /><br />Carlos described these further criteria, then continued by describing how to define canonical forms for Nim.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com5tag:blogger.com,1999:blog-49096384337620230.post-64763415288557175162016-08-12T11:11:00.002-07:002016-08-12T11:11:31.530-07:00Games@Dal 2016: Craig talks about PenFib NimGames@Dal 2016 talk: "Penultimate Nim and Conjoined Games" - Craig Tennenhouse, w/ Kelsey Mihachik<br /><br />Craig talked about Conjoined Games, another type of "sum" extending the notion of sequential sums. The sequential sum of G and H works that both players must play as normal on G until the game ends, at which point the next player makes a move on H. Conjoined Games are special in that the second summand (H) is not defined until G ends; H is based on the state terminal position from G. The nicest games to play are those where the state of the terminal position is exactly the state of H. Craig suggested Colobber: Col followed by Clobber.<br /><br />Craig then described Penultimate Nim (AKA Gale's Nim), which is just like Nim except that there are no moves when there's only one heap. Pen(ultimate) Nim is solved for all games with 3 or less heaps. He then showed Fibonacci Nim: a single-heap subtraction game with the following rules:<br /><br />* For the first turn, the first player may take any number of sticks aside from the entire heap.<br />* On any subsequent turn, the current player may take any sticks up to twice the amount the previous player took.<br /><br />Craig then presented PenFib Nim, which is Penultimate Nim followed by Fibonacci Nim. He's working on trying to categorize the P-positions. <br /><br /><br />Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-13236000785919766192016-08-12T11:02:00.002-07:002016-08-12T11:02:49.936-07:00Games@Dal 2016: Neil talks about Transitive GamesGames@Dal 2016 talk: "A unique form for hereditarily transitive games" - Neil McKay <br /><br />Neil McKay spoke about a new term: Transitive Games. A game, G, is left-transitive if all positions that could be reached from a series of left-only moves from G are also (immediate) options of G. Right-transitive is defined analagously, and a position is transitive if it's both left and right-transitive. Games are hereditarily transitive if their subpositions are also transitive.<br /><br />The ruleset MAZE is transitive, because players can move as many spaces in their direction as they want during their turn. (At some point, I should write a Game Description post about MAZE and MAIZE.)<br /><br />Neil defined closures for (hereditary) left-transitivity, by recursively adding, as new Left options, all Left options of Left options. Again, the right closure is analagous. Speaking in terms of rulesets, MAZE is the hereditary transitive closure of MAIZE. It's still not known which rulesets have a transitive version that's equivalent.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-43059711069625017962016-08-11T05:17:00.000-07:002016-08-12T10:54:59.821-07:00Games at Dal 2016I arrived in Halifax for Games at Dal 2016. The trip was extremely fun: I drove from Plymouth, New Hampshire, and picked up Craig Tennenhouse, my student Amelia, and Neil McKay all in separate places. As Craig said, we were like the Muppets, getting the band back together.<br /><br /><br /><iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/MMR5JVo21wQ" width="420"></iframe> <br />We had six talks yesterday; I'll write something about each of them in the coming days. We have some new people, including Israel, a nice Brazilian graph theorist who studied a traditional game with Urban.<br /><br />The working sessions begin today, and I'm hoping I can convince some people to look at some computational complexity problems with me. We'll see about that. ;) Last year, Games@Dal was extremely kind to me. I started a new research project with Svenja, Silvia, and Melissa, and we had the paper submitted just two months later. That's my fastest turn around research-to-submission ever!<br /><br />Either way, Dalhousie and Halifax is a beautiful setting for thinking about games. Huge thanks to Richard, Melissa, and Svenja for organizing and running the conference!<br /><br />I failed to announce this conference beforehand, unfortnately. After this trip, I'll post about upcoming conferences, including Integers 2016 and CGTC2. This next academic year will definitely not be devoid of CGT gathering opportunities!Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0