tag:blogger.com,1999:blog-490963843376202302024-07-14T11:04:46.503-07:00Combinatorial Game TheoryMy CGT musings, with an emphasis on the computational complexity of games.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.comBlogger284125tag:blogger.com,1999:blog-49096384337620230.post-5550305988470935962024-04-23T13:29:00.000-07:002024-04-23T13:29:06.182-07:00Sprouts 2024 Talks<p><a href="http://kyleburke.info/sprouts/sprouts2024/">Sprouts 2024</a> was on Saturday, and it was excellent! Here are my summaries of the talks:</p><p><br /></p><p><b>Pritika Raj, "Red-Blue Hackenbush and the Construction of Real Numbers"</b></p><p>Pritika covered the basics of Hackenbush and showed how to create integers from mono-colored stalks: path graphs with one end on the ground. Then she got to dyadic rationals, and showed that they can also all be created from finite stalks. After that, Pritika explained how to use infinite stalks to create non-dyadic-rational real numbers. For example, she showed that 2/3 is equal to an alternating Blue/Red/Blue/Red/... infinite path from the ground. </p><p><br /></p><p><b>Vivaan Daga, "Nim and Base 2"</b></p><p>Vivaan explained the rules of Nim and gave a good example of a playthrough. He showed how to use the binary XOR to figure out the outcome class of a position. Then he got into the details of the proof that XOR works. Vivaan explained that binary is the important operation because, due to the mex rule, Grundy values are as small as they can be.</p><p><br /></p><p><b>Keynote: Mike Fisher, "Octal Games: Old and New"<br /></b></p><p>Mike introduced impartial games and the basis of Sprague-Grundy theory. Then he explained the rules of Kayles and showed the table of the first 84 Kayles values. He showed the same with Dawson's Chess, explaining the rules and giving a table of values that showed the periodicity. Then he covered Treblecross in the same way, but showed a graph of the Grundy values, since it's unknown whether the Grundy values are periodic.</p><p>Mike then explained the coding of octal games. Each game is represented as d0.d1d2d3d4... with d0 = 0 or 4, and all other di being between 0 and 7 (inclusive). Each digit di is the sum of up to three components:</p><ul style="text-align: left;"><li>1 if you can remove i when the pile has exactly i,<br /></li><li>2 if you can remove i when the pile has more than i, and</li><li>4 if you can remove i and split the remaining items into two piles, when the pile has more than i+1</li></ul><p>Mike showed that Kayles is 0.77, Dawson's Chess is 0.137, Treblecross is 0.007, and Nim is 0.3333... He then showed off Achim Flammenkamp page of <a href="http://wwwhomes.uni-bielefeld.de/achim/octal.html">known octal game properties</a>. </p><p>He continued by describing Wythoff's Nim, Beatty Sequences, and the Golden Mean, then explained what the Silver and Bronze means are. He used that to lead into the three octal games he created from sequences based on each of these means. The Olympic Games, as they are known: The Golden Game, the Silver Game, and the Bronze Game. Mike ended with a new result to me: the Plastic Game, based on the plastic sequence, which is generated by Van der Laan numbers.<br /></p><p> </p><p><b>Ethan Saunders, "Misère Cricket Pitch"</b></p><p>Ethan explained Cricket Pitch, themed around a bumpy field that must be leveled out by a huge roller. The game is described by a list of non-negative integers with the roller inserted somewhere. A move consists of moving the roller in your direction (left/right) over as many piles as you want, but you can't cross a zero-sized pile. Every pile you roll over in your turn gets decremented. Ethan showed how to calculate some basic games, then used this to discuss group representations. </p><p><br /></p><p><b>Sean Pye, "Fighting Fires on Infinite Grids"</b><br /></p><p>Sean researched the fire-fighting problem on graphs: where fires break out on vertices then fire fighters are sent to defend them. The fire fighters prevent the vertices they visit from burning as the fire spreads out from its initial location each round. Sean studied solutions on hexagonal grids and strong grids. He showed the known strategies for hexgrids that use only 2 firefighters to contain a fire and that strong grids need only 4 firefighters.</p><p><br /></p><p><b>Devan Burke, "Reinforcement Learning with Super Mario Bros."</b></p><p>Devan talked about how he<b> </b>worked towards training an AI player to beat level 1-1 of Super Mario Bros. He talked about the formulas he used to reward the AI player using reinforcement learning. He explained that the player can see four snapshots of the screen to use as input. In order to keep the size reasonable, they used grayscale images. Devan described the design of the neural networks used by his player. His algorithm included a double-deep Q network. </p><p><br /></p><p><b>Raymond Riddell, "Monte Carlo Tree Search"</b></p><p>Raymond talked about the MCTS algorithm he wrote for my HTML-(and JS-)based combinatorial games. He explained the difference between heuristic and aheuristic algorithms. He showed a demo of the algorithm applied to Connect Four. He described a bunch of details of his code, including how the tree is structured and all of the UCB1 values of the nodes based on their win records. These values are used to determine which node to traverse when exploring more of the tree.<br /></p><p><br /></p><p><b>Max Fierro, "Computational Methods Uniformly Pushing the Solving Horizon"</b></p><p>Max talked about exhaustive searches for solving deterministic games. In order to do this, he employs the notion of histories, sets of states that include a utility function. His team created a 4-tuple to represent vertices in a graph that works for any sort of deterministic game. Max described a minimax implementation to search and make decisions. His group uses multiple threads and a custom database system to speed up his code.<br /></p><p><br /></p><p><b>Tomasz Maciosowski, "The Temperature of a Snort Position can be Infinitely Larger Than its Degree"</b></p><p>Tomasz explained the game of Snort and described a game simplification that removes unplayable vertices and tints vertices that can only be played by one player. He described the notion of temperature and showed how it applies to star graphs. He then talked about using a genetic algorithm to search for positions with higher temperature than the max degree of the graph. This led to the discovery of caterpillar graphs that led to unbounded differences between the temperature and degree.<br /></p><p></p><p><br /></p><p>One of our scheduled presenters got sick and couldn't present, but otherwise this was an immensely successful edition of Sprouts! Thank you to everyone who came and especially thank you to everyone who presented! See you next year!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-84234933224406739002024-01-25T04:44:00.000-08:002024-01-25T04:44:55.003-08:00Games at Mumbai: Not the Talks<p><a href="https://www.ieor.iitb.ac.in/Combinatorial_Games">Games at Mumbai</a> just ended. In a few hours, I will arrive at the airport and fly home. My first time in India has been wonderful! I loved it! Here are some quick notes about my time here that I think are interesting:<br /></p><ul style="text-align: left;"><li>The traffic outside the IIT Bombay campus is the wildest I have ever experienced.</li><li>Learning to look right first when I try to walk across a road is harder than I thought it would be. <br /></li><li>All of the food was awesome! I discovered so much!</li><li>Many bathrooms have a bidet spray nozzle instead of toilet paper. I attempted to learn to use bidets without using toilet paper, but failed. I had to rely on stalls that were equipped with rolls of toilet paper.</li><li>The venue at IIT Bombay, the Victor Menezes Convention Center, was excellent. There is a great indoor room for presentations and a nice shaded outdoor space for eating and collaborating. (We also had access to some classrooms.)</li><li>I got addicted to chai, both with and without masala.</li></ul><p>Notes specific to CGT:</p><ul style="text-align: left;"><li>I talked about what (I think) a ruleset is and this sparked some conversations.</li><li>Lots of people wanted to talk with me about my research! That was a (dangerous) ego boost, for sure.</li><li>I was lucky about the topics I put in my second talk; it addressed many of the questions I got in the two days after the first one. I barely changed anything from the slides I had before I arrived!</li><li>Four days of talks about CGT is not too much for me, even being sleep-deprived for three of them.</li><li>I learned a TON about the pre-history of CGT from Carlos. <br /></li></ul><p>Long, sappy note: <br /></p><p>I was very nervous about this trip, because air travel is tough for me. Mumbai is the furthest east I have ever traveled. I got quite sick a few weeks ago, and then the day before I left I still had to visit the doctor. My flights here got cancelled on the morning they were set to depart. </p><p>Nevertheless, I still made it here and I am extremely glad I did. I learned so much. Thank you to everyone I met! Thank you to everyone on the organizing committee! I feel like I could have jumped into 5 or more new research projects! (I'm not a research professor, so there's no way I'll be able to do that, sadly.) </p><p>I have been very lucky in my career. Many times I have not been able to follow through on all the things I wanted to do, and I've had the fortune to continue on anyways. I received a lot of appreciation here, and it means a ton. I hope that it is deserved; I did spend a lot of time preparing my talks. <br /></p><p>Just like the <a href="https://projet.liris.cnrs.fr/gag/workshop/index.html">Games and Graphs Workshop</a> six-and-a-half years ago and the <a href="https://www.birs.ca/events/2011/5-day-workshops/11w5073">BIRS meeting in 2011</a>, I really feel like a valuable part of the CGT community. Thank you to everyone. There may not be any chance in our rulesets, but I've still been very lucky. <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-91453495642320629152024-01-25T03:41:00.000-08:002024-01-25T03:41:56.976-08:00Games at Mumbai, Day 4 (Final) of Talks<p>The talks on the final day of Games At Mumbai continued the excellence of the week! Here are my summaries:</p><p><b>Dhruv Basin, "On ergodicity of a 1-dimensional PCA with parity dependent updation rules" </b> <br /></p><p>Dhruv talked about the site percolation problem--whether there are open clusters on randomly-generated graphs. In a game version of this, vertices (integer coordinates of the Cartesian plane, so the board is infinite) are randomly either a trap, a target, or open. Players alternate moving a token along edges that are the same respectively for each vertex. If you land on a trap, you lose. If you land on a target, you win. If both players can force play to continue infinitely, then the game is a draw. Dhruv showed that, on some loop-free transition choices, how to recursively define the outcome classes. Then he talked about how this is all related to Probabilistic Cellular Automata. Dhruv found some range of target/trap probabilities that make the probability of draws become zero.</p><p><br /></p><p><b>Anirban Mitra, "A Steckelberg game for cross-channel free-riding"</b><br /></p><p>Anirban discussed multi-channel retailing: the approach of selling goods via multiple platforms. He described showrooming: looking for products in person, then buying them online as well as the converse: looking for products online, then buying them in person. Anirban created a Steckelberg model to create an economic game for these phenomena. He talked about using SPNE (Subgame Perfect Nash Equilibria) to solve the value of Steckelberg games. He applied SPNE to his showrooming and webrooming model and got meaningful results.</p><p><br /></p><p><b>Saraswati Girish Nanati, "Eternal Vertex Cover Game"</b><br /></p><p>Saraswati introduced the Eternal Vertex Cover Game, based on the eternal vertex cover problem. This is a loopy maker-breaker game. A position consists of an undirected graph with guards on a subset of the vertices. Each turn, the attacker selects any edge. If there are no guards on the vertices incident to that edge, then the attacker wins instantly. Otherwise, on the defender's turn, they move each guard along up to one edge, one of which must include the edge chosen by the attacker. (Two guards can cross paths and swap.) Saraswati related this to the EVC number of a graph. She showed that finding the smallest necessary set of guards for the defender to win forever is NP-hard by reducing from Red-Blue Dominating Set. On elementary bipartite graphs, if all guards are in one half of the vertex set, the winning strategy for the defender is to move all guards along the perfect matching. If not perfect matching exists, then the attacker has a winning strategy. Saraswati then discussed some variants and open problems she has results for.</p><p><br /></p><p><b>Santanu Acharjee, "Scopes of games in bitopological dynamical systems"</b><br /></p><p>Santanu talked about potential applications of CGT to his field: bitopological dynamical systems. This is concerned with quasi-pseudo-metric spaces when two metrics form a partition on the topology. (I'm glad I remembered a bit of my college topology class, but I definitely needed to remember more!) Santanu talked about when many pairwise properties existed across the two metrics. He then related this to infinite games on topological spaces. The point of these game, he said, is not to play, but to describe novel infinite strategies. He talked about Menger, compact, and Alster games (and even more categories beyond these) on bitopological spaces, and many conditions he found for when winning strategies exist.</p><p><br /></p><p><b>Matthieu Dufour, "A family of slow exact k-Nim games"</b><br /></p><p>Slow exact k-Nim (SN(n, k)) is a game played on n stacks of tokens. A move consists of removing exactly 1 token from exactly k different stacks. Prior results are known for the P-positions on SN(n, 1) (P-positions: when n is even), SN(n,n), SN(3,2), and SN(4,2). Matthieu has extended this by adding results for many other individual categories. He started by showing how to identify unplayable tokens to shrink some positions to equivalent smaller stacks. He called this the NIRB (No stack Is Really Big) condition. He then listed some other values commonly important to categorize positions. Matthieu showed his evaluation strategies, explaining when he needed reductions to complete the characterization proofs.</p><p>After his talk, Matthieu showed a hilarious "mathematical magic trick" called "Bring the Cat" to close the conference. He pulled a numerical rabbit from a hat!</p><p><br /></p><p>Games At Mumbai (Extra Spicy) has been an excellent experience! I felt really honored to be included, and especially lucky to get to give so many talks. All of the talks I listened to were awesome and I hope to see many of the new people I met again! Thank you so much to Urban, Mallik, Prem, Anjali, Ankita, and everyone else who made this happen!<br /></p><p> </p><p> </p><p> <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-87449232455663077122024-01-24T05:20:00.000-08:002024-01-24T05:20:35.252-08:00Games at Mumbai, Day 3 Talks<p>Day 3 of Games at Mumbai had more excellent talks! (I hope you like Wythoff's Nim! :-P)<br /></p><p> </p><p><b>Indrajit Saha, "Subtraction Games in more than one dimension"</b> <br /></p><p>Indrajit described a two-pile subtraction game in terms of animals taking from different piles of nuts: either 3 walnuts and 1 peanut or 1 walnut and 2 peanuts. This generalizes to multi-dimensional subtraction games on tuples. Indrajit has proven many excellent properties in two dimensions when there are two elements in the subtraction set. For example, if S = {s1, s2}, then a tuple t is a P-position exactly when t + s1 + s2 is also a P-position! This is the two move theorem. When plotting the P-positions, some of the images look like overlapped checkerboards. Indrajit has also found many results when extending to any dimension.</p><p> </p><p><b>Carlos Pereira dos Santos, "Some open problems in CGT: Not much background required!"</b> <br /></p><p>Carlos went directly into impartial games. He started by talking about Luca Pacioli, who, 500 years ago, wrote a treatise that contained a combinatorial game: a backwards subtraction game (you add instead of subtract and are trying to get up to 30) as well as the solution to the game. Carlos then talked about basic subtraction games and Grundy sequences. He did a long example ({1, 3, 6}) and then showed a table of known results from Winning Ways. Then he gave a first 40-year-old unproven conjecture by Richard Guy about the bounds on period lengths of subtraction games. Then he listed another open problem directly related to Indrajit's talk: the periodicity of bidimensional finite subtraction games. Next he talked about pile splitting, starting with Kayles.</p><p>Carlos then moved into partizan-land, using Blue-Red Hackenbush. He explained how to represent dyadic rationals in binary. He showed the utility of using negatives in the representations to build numbers with no zeroes. From this, he showed that these are really just Hackenbush strings with that numeric value.</p><p><br /></p><p><b>Gandhar Joshi, "Games, puzzles, and automatic proofs"</b><br /></p><p>Gandhar talked about finite state automata and the sequences they generate: automatic sequences. Gandhar then showed the relationship to games using Wythoff's Nim (he put an Indian spin on the normal names, using Leela and Rajesh). He showed that Zeckendorf representations can be used with the automata to find Wythoff's Nim P-positions. Gandhar then talked about using the Walnut theorem solver to find new integer sequences from Upper and Lower Wythoff sets.</p><p><br /></p><p><b>Shun-ichi Kimura, "Enforce operation of the disjunctive sum and the continued conjunctive sum"</b><br /></p><p>Kimura talked about two-pile subtraction games as well. He started by showing plots of his P-positions first, which looked a lot like Indrajik's images, then promised they were the results of easy rules. In his games he used the continued conjunctive sum, which means players have to make a move on each summand game on their turn, except they can ignore components without moves (unless none of them have moves; then you lose). Then Kimura explained the enforce operator across sums: the opponent decides which kind of sum the next player will use on their turn. "Something phenomenal happens", especially because Tweedledee-Tweedledum strategies are much more difficult to implement. There is also a good theorem by Odawara that shows that some sum rules dominate others. Combinations of sums create the figures he showed initially, all of which used the same subtraction set {1, 2, 3}.</p><p> </p><p><b>Takahiro Yamashita, "Yama Nim, Triangular Nim, and their Wythoff variations"</b> <br /></p><p>Yamashita also talked about two-heap Nim games. Yama Nim is a variant where you must take at least two from one pile and you also return 1 to the other heap. The P-positions turn out to be along the diagonal and the two diagonal bands adjacent. Triangular Nim is a generalization of Yama Nim where you can return more than one token so long as the total number removed is still positive. Amazingly, the P-positions are exactly the same! The Grundy values, however, are different and more complicated. Yamashita then added the "c-Wythoff" twist to triangular nim, allowing players to remove from both piles as long as the difference between the removed amounts is less than or equal to c. The 0-Wythoff twist changes the P-positons into a list of triangular number pairs! The 1-Wythoff twist gives square numbers! Yamashita proved the theorem that the c-Wythoff twist delivers (c+3)-gonal number pairs as P-positions!</p><p> </p><p><b>Hirotaka Ono, "Computational Complexity of Turning Tiles"</b> <br /></p><p>Ono described Turning Tiles, which I'd seen Koki, one of his coauthors, present before. The game is played on a grid of Blue/Red/Black colored tiles and with a token on one of the non-black tiles. A turn consists of moving the token as a rook so long as all spaces entered are that player's color. After moving, all tiles that were left get turned to black (never to be used again). Ono showed that this game is PSPACE-complete, and also showed that the disjoint version is DP-hard. The hardness reduction is from (Generalized) Geography, restricted to the still-hard max-degree of 3 bipartite graphs. With those restrictions, Ono was able to create gadgets embedded in the grid. He then stated that the monochrome disjoint version with one token on each section is DP-hard via a reduction from SAT-UNSAT. Very cool! Ono finished by showing an exponential-time dynamic programming algorithm to solve the general version of the game.</p><p> </p><p><b>Hridank Garodia, "Pixel Pummel"</b> <br /></p><p>Pixel Pummel is played on an m x n grid, with players placing their own colored dominoes on the grid. The dominoes are placed standing up, but oriented either vertically or horizontally all in one square. When a domino's placed with it's long side (from above) directly facing an adjacent opponent's domino's short side, the opponent's domino is replaced by one from the current player (in the same orientation). These captures cascade recursively. There are other play configurations that are not allowed. Hridank, who is a local high school student, has already shown the outcome classes of 1xn boards. <br /></p><p> </p><p><b>Geremias Polanco, "On the theme of Wythoff's Game"</b> <br /></p><p>Geremias warned us that his talk was likely to have a "number theory flavor". He started off by describing Beatty sequences, then went to Sturmian sequences (new to me) and showed the bijection between them. He stated that Wythoff introduced the mex function, which I did not know. He then covered many of the generalizations to Wythoff, including the removal of the monotonicity requirement on the sequences. Geremias found a Unifying Theorem that states that one of the four properties must be true. He was also able to find a relaxed version of Wythoff that includes all Beatty solutions.<br /></p><p> </p><p><b>Nikhil Gehlot, "Enabling learning by playing"</b> </p><p>Nikhil comes from the side of reality: his company creates educational games to help students learn math and science skills. He described multiple games that reinforce trigonometric functions. They also have games for chemical formulas and coordinate systems. <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-69773297567641442092024-01-23T04:51:00.000-08:002024-01-23T04:51:21.226-08:00Games at Mumbai, Day 2 Talks<p><b>Anjali Bhagat, "Fork positions and 2-dimensional Toppling Dominoes"</b> <br /></p><p>Anjali described Toppling Domines, giving some good examples of positions, options, and values. Her definition included green dominoes, which is not something I'd look at before. The best part is that she brought in actual dominoes to demonstrate along the edge of the podium. She then introduced a 2-dimensional variant where one domino is lined up directly next to two dominoes on the same side. These "fork dominoes" are interesting because they root domino can knock over both other two, but neither of those can topple the other. She found a bunch of results about what happens when you duplicate one domino in the middle of a string She proved that when a green stone is added, in many cases the value of the new position is comparable with the old. Anjali also looked at many other combinations and is interested in solving triangular-number-type structures of all green dominoes. <br /></p><p> </p><p><b>Ankita Dargad, "The temperatures of Robin Hood game"</b> <br /></p><p>Ankita explained Robin Hood, a 1-heap game of Wealth Nim with some additional rules: players cannot remove more tokens from the heap than their wealth, and when they take t tokens, it also deducts that same amount from the opponent's wealth. She also formulated the game in an equivalent way named Ancient Village Story. She then discovered values (hidden in Sherwood Forest, no doubt) including all integers and all integer switches and switch-like values. "It's a hot game," she explained. Ankita then went deeper and looked at the Left and Right stops. She named the optimal move the "Little John" move, which can be determined easily. I learned that in India, the Fibonacci sequence is known as a Pingala sequence, which contains all such sequences using different starting pairs. She showed that the wealth values follow one of these. She continued by analyzing the temperatures of these positions, which depend on how the Golden Ratio relates to the ratio of wealths.</p><p> </p><p><b>Prem Kant, "Bidding Combinatorial Games"</b> <br /></p><p>Prem, who I met last year in the Azores, talked about how to generalize the alternating play part of CGT to create rulesets where players bid to see who plays next. To handle the bidding process, he uses Discrete Richman Auctions: the players secretly choose their bids, then simultaneously reveal them. The winner hands over what they bid and (must) take(s) the next turn. The players each have starting money and bid must be a non-negative integer. There is additionally one tie-breaker token that one player starts with. The token can be included in that player's bid, and adds a value of 1/2. It gets transferred with winning as normal, however if the bids are tied, then it is considered automatically added to that player's bid, so they win and it is transferred to the other player. There's a lot of space for results here and Prem has covered quite a lot. In particular, he talked about the different outcome classes based on the budgets each player has compared with the overall total. For each total budget in the non-negative integers, he found a way to set up the positions so that each one of the possible outcomes in that range is reached.<br /></p><p><br /></p><p><b>Johan Wästlund, "Games and optimization on random structures" </b><br /></p><p>On rare occasions, I go to talks at these meetings and then I think "Oh, this one isn't actually about games," and then all of a sudden it is. This was one of those talks!</p><p>Johan started by talking about the geometry of randomly-generated trees and how to determine their independence number--the size of their maximum independent set. He then showed how that probability distribution comes out. This was then all used in a simple dice game where players alternate rolling a single n-sided die until the number of throws + the number of distinct values rolled is greater than or equal to n, with the last person winning. The probability of the game ending after k rolls is exactly equal to the probabilities of the independent set having size k. Wow!</p><p>He used that result to tie into the game Slither, which is equivalent to (directed) Geography on a game tree. To generate the trees, he uses the same random process as before, but then also randomly chooses the root. From this he generates a Slither code by writing down the labels of the leaves, from lowest to highest. Each time he appends these to the ends of the string and works his way in, with P and N-positions going on different sides. His scheme also includes writing the label of each parent above each digit. The resulting 2-row code is enough information to completely recreate the tree. Since the P-positions always consist of a maximum independent set (whoa!) you can also determine the independence number from the string! He used this to find the Omega constant, though his construction is different from the prior method found in the 1970s.</p><p>Johan then switched to talk about putting random edge weights in [0,1] on the complete graph, K_n. If you consider the minimum matching total weight, that cost tends towards (pi^2)/2 as n goes to infinity. He talked about a relaxation of the problem that allows you to pay a bailout price instead of paying for the matching for expensive edges. This is related to a graph game where the players traverse a weighted undirected graph and pay the edge's weight at each move. (Or pass and pay the bail out price.) Optimal play can be analyzed by relating back to the matching problem and using that solution.</p><p>He also mentioned comply-constraint games, where the opponent picks two options for the current player to select to move to (instead of all available options). He then surprised me once more by relating this to the Traveling Salesman Problem! "You never know when Game Theory will come in handy!" </p><p>This was such a cool talk because of how the different results related back to games in amazingly unexpected ways!</p><p><br /></p><p><b>Satvik Sharma, "Symmetry in Combinatorial Games"</b><br /></p><p>Satvik, an undergrad student, talked about many cases of symmetry in games. First he talked about strategy stealing arguments. He described the 2-move Chess game where each player makes two standard Chess moves in a row instead of one. There is a very simple strategy stealing argument showing that the second player cannot have a winning strategy (though they may be able to force a Draw): if they did have a winning strategy, then the first player could just move a knight out and back and then use that second player's strategy. He also talked about the Hex Theorem and the result that the first player has a winning strategy. Satvik then talked about how to employ Tweedledee-Tweedledum arguments whenever they are available. Finally he talked about the Game of Queens, a partizan placement game where you alternate placing a queen of your color, but only in a space no other of your queens can attack. Satvik showed that a symmetry strategy works very well here for any even x even or odd x even size boards.</p><p><br /></p><p>Today was another great day of talks! These are excellent!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-34785489606215454452024-01-22T06:15:00.000-08:002024-01-22T06:15:31.341-08:00Games at Mumbai, Day 1 Talks<p>Today we kicked off a big day of talks at the first "official" day of <a href="https://www.ieor.iitb.ac.in/Combinatorial_Games">Games at Mumbai</a>. Urban taught a CGT course (for grad students) last semester, and I believe that many of the presenters created new combinatorial games in his course, which they spoke about. There were many very creative games!<br /></p><p><br /></p><p><b>Carlos Pereira dos Santos, "A quick journey into Combinatorial Game Theory"</b></p><p>Carlos gave us an intro to all of CGT. (These talks are very interesting to me because I have heard many different versions and I'm always looking to improve the "Crash Course" talk I give every year at Sprouts.) </p><p>Carlos began with impartial games, using Nim, Cram and Wythoff's Queens to explain Sprague-Grundy theory. (Carlos was very historically-minded in his talk and started with Bouton.) He gave lots of good examples to motivate his talking points. He had a great quote about the omnipresence of nimbers: "This is no longer just a recreational result." In the end he phrased Sprague-Grundy theory as four facts (this is my simplification):</p><ul style="text-align: left;"><li>Every impartial game has a nimber value. (The aforementioned "omnipresence of nimbers")</li><li>The nimber value can be computed by the mex rule.</li><li>Sum values use the XOR rule, and </li><li>The outcome class is determined by whether the nimber value is zero.</li></ul><p>Carlos did not have much time left for the partizan half of his talk. Nevertheless, he got to integers and 1/2 using Hackenbush positions. Overall this was a great talk! I don't think I would be able to fit al the historical context into my talks like he did. </p><p> </p><p><b>Moumanti Podder, "Graph nim games on graphs with four edges"</b> <br /></p><p>Moumanti talked about a Nim variant on graphs with weighted edges. Each move consists of selecting a vertex and removes tokens from the incident edges in any way that removes at least one token overall. She showed that a "rectangle graph" is a zero position by explaining a Tweedledee-Tweedledum strategy. She also showed that star graphs act like single nim heaps, so a galaxy acts like a multi-heap nim position. Moumanti is looking at trying to characterize the outcome classes of graphs with four edges. She's found some results on the nim values on triangles, which she got by adding with to a disjoint single edge. <br /></p><p> </p><p><b>Aaron Siegel, "How to lose at combinatorial games (or at least draw)"</b></p><p>Aaron talked about "standard" CGT and all the different ways the conventions can be broken. (Transfinite games was a new concept to me!) He covered breaking normal play (to be mis<span>è</span>re) and finite game lengths. </p><p>In mis<span>è</span>re play, Aaron explained that Bouton also found the winning strategy for nim (as well as in normal play). He went over the Sprague-Grundy basics, and applied it to Kayles, showing off how nice periodicity falls into normal play. He contrasted this with mis<span>è</span>re results, which continue to highlight just how elusive these nice patterns are. "We need an extra condition for outcome classes," he explained--the base case for the set which is an exception to the natural terminal condition. He gave the Mis<span>è</span>re Mex Rule, which "becomes almost useless in mis<span>è</span>re theory." (As with outcomes, there is an additional condition from the normal play version.) He explained the "combinatorial explosion" that happens and that the number of possible values born on day five skyrockets to 4,171,780. </p><p>Aaron then talked about tame games: mis<span>è</span>re impartial games that do reduce to nim. He also talked about using other algebraic structures to solve different rulesets, including Kayles. </p><p>Shifting to loopy games (under normal play, still impartial), Aaron showed that we no longer have game trees. He explained the new outcome class: D - draws. He provided some basic game graphs to show the cases where Draws can occur. Aaron then dove into values, giving the definition of the loopy mex-rule. This was very helpful; I think I understood values of impartial loopy games for the first time!</p><p><br /></p><p><b>Aditya D. Bhat, "Slamming Toads and Frogs"</b></p><p>Aditya explained how his game differs from traditional Toads & Frogs: no jumping moves are allowed; instead amphibians "slam" other pieces over them. More concretely: an amphibian with an open space behind it and with an opposing amphibian right in front of them can move that opposing piece to that open space behind, as though that opposing piece had just performed the T&F jump move. Aditya used CGSuite to find many different game values. In general, it seems that the values are at least as hot as the same position in Toads and Frogs. So far he hasn't found a single *-valued position.</p><p> </p><p><b>Deepankar Sehra, "Impartial Game Ruleset: Space Quest"</b> <br /></p><p>Deepankar's game, Space Quest, involves an avatar moving around on a grid, one space horizontally or vertically each turn, to a cell that has not yet been visited. In addition to that movement, however, the player must also pick another cell anywhere on the board to destroy. There is a lot of similarity to Undirected Vertex Geography. Deepankar has done some work on the outcome classes and nimbers of nxn grids up to n=5. Amazingly, they so far all satisfy: nxn = *(n-1). (The starting position of the avatar is in the top left cell.)</p><p> </p><p><b>Tanmay Joshi, "3-Annihiliation"</b> <br /></p><p>Tanmay showed off his ruleset, which is played on a string of Ls and Rs, but never three or more of the same letter in a row. A turn consists of removing one of your own letters, which shrinks and collapses the string. If this creates any string of 3 or 4 of the same letter in a row, those are removed. This process is continued until no more 3+ of the same letter remain. Tanmay has found the integers -2, -1, 0, 1, and 2, switches, but no stars nor fractions. It seems very reasonable that no other integers exist! Additionally, the hottest temperature he's found so far is 2, which also makes sense.</p><p> </p><p><b>Vedang Gupta, "Nuclear Battleship and Surround"</b> <br /></p><p>Vedang showed off his two new rulesets: Nuclear Battleship and Surround. The former is played on a grid with each player having a single ship piece on separate spaces. Some of the spaces may be destroyed (due to nuclear fallout in the area) and ships cannot move there. Each turn the current player either leaves their ship alone or moves it, then fires a nuclear missile at another space. (They can target any undestroyed square, including one that contains an opponent's ship.) At the end of their opponent's next turn, that space becomes destroyed. Thus, opposing ships want to move out of a targeted square if they're in one. Vedang found integers, unbounded switches, and *, and showed thermographs for some positions with multiple ships of one color.</p><p>Vedang then talked about his second ruleset: Surround. In this game, also played on a grid, spaces can contain white or black tokens. A turn consists of placing tokens of your color in any of the cells that surround the other player's pieces, including the diagonal connections. If no such cells exist, you're allowed to play one piece along the board's edge. This creates an all-small ruleset. Vedang found a lot of infintesimal values, including *, *2, and up.</p><p><br /></p><p><b>Harhsvardan Agarwal, "Tokens Partizan"</b> <br /></p><p>Tokens Partizan is another game played on a grid. One way to think of this game is that one player is making Col moves while the other is making Cram moves. White plays single white stones, but cannot play adjacent to their prior plays. Black places two adjacent black stones on the board either vertically adjacent or horizontally. Harhsvardan talked about strategies for the players that involve thinking of the boards colored in a checkerboard style. With this reasoning, he found general results for all empty grid boards, many of which were proven using induction and reasoning about tiling.</p><p><br /></p><p>These talks were really good today! I am really looking forward to see what tomorrow brings.<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-90335898821109049322024-01-21T20:02:00.000-08:002024-01-21T20:02:40.257-08:00Games at Mumbai, Day 0 Talks<p>On the "unofficial" first day of <a href="https://www.ieor.iitb.ac.in/Combinatorial_Games">Games at Mumbai</a>, we had two talks and two tournaments! This has been a great conference already, but you are here to hear about the talks, so here we go.</p><p><b>Karan Rawat, "All about Go!"</b></p><p>Karan, a member of the Maharashtra Go Association, gave us an overview of Go. He talked about the history and origins. He compared it to Chess, which is apparently far more popular in India. Karan talked about six of the top international Go federations and some of the top tournaments. He explained many cultural aspects, especially high level tournaments and the pieces used. (Super fancy Go stones made of shells can cost as much as $150 apiece!) Karan explained the rules and discussed a bunch of patterns for beginners to look out for.</p><p> </p><p><b>Carlos Pereira dos Santos, "Presentation of Atari Go"</b> <br /></p><p>Carlos gave a quick talk to explain Atari Go, which is the same as Go except that the first capture move wins. (Self-capture moves and passes are not allowed.) He did give a quick dip into breaking down a complex position into separate independent pieces and use a disjunctive sum to put them back together. "All components matter" he advised, and then we were off to play an Atari Go tournament. <br /></p><p> <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-29832882362987570012023-04-01T19:21:00.000-07:002023-04-01T19:21:11.049-07:00Sprouts 2023 Talks<p>Sprouts 2023 went great today! Here are my summaries of the talks.</p><p><br /></p><p><b>Shikhar Sehgal, "Playing with Money: Using Symmetry and Combinatorial Game Theory to Solve Simplified Versions of Poker"</b></p><p>Shikhar started by explaining the basics of poker, including the betting and bluffing and versions like Five-Card Stud and Texas Hold 'Em. He then covered the notion of expected values. Shikhar broke down all steps of poker into different turns, using expecting values in a scoring-game-outcome fashion. When the tree is collapsed, the result seems to be very similar to a partizan game.</p><p><br /></p><p><b>Isaac Attoh: "Positions of High Temperature in Domineering"</b></p><p>Isaac reminded us about the basics of Domineering. He showed how some positions are cold (integers) and others are hot (switches). He covered the basics of temperature including cooling. Isaac showed the Drummond-Cole temperature 2 position and Berlekamp's conjecture that there isn't anything higher in Domineering. Isaac was able to find new positions of temperature 3/2 and 7/4. He used Sage Math and CGSuite in tandem to find those positions. (During the questions, Isaac revealed that he believes the conjecture.)</p><p> </p><p><b>Melissa Huggan: "The Cheating Robot" (Keynote) </b> <br /></p><p>Melissa talked about her simultaneous CGT model where one player has the advantage of being the Cheating Robot: they can see what move the other player is going to make and choose their best possible counter. This is still different from alternating play for two reasons:</p><ul style="text-align: left;"><li>The game appears to any observer to be being played simultaneously, so draws can occur.</li><li>The ruleset changes from standard normal play due to moves that interfere with each other.</li></ul><p>Melissa then applied her model to Toppling Dominoes. Although single-color rows of dominoes still maintain their integer "values", rows of two single-color components are already complex: the cheating robot's best strategy isn't necessarily to push back on the same row as the other player, even if that position is traditionally the highest-temperature switch!</p><p>Melissa then talked about the Cheating Robot outcome classes (L, R, and D for Draw) and notation: {G^L | G^S | G^R} where G^S are the same round options: what can happen when both players play on that same position. She also covered CR-game trees and conjugates (instead of negatives) and explained that there are still some fundamental terms getting sorted out.</p><p>Melissa finished up by applying the Cheating Robot to Cops and Robbers. For example, she showed that on a strong grid, four cops are needed to capture a robot-robber.</p><p><br /></p><p><b>Harpreet Brar: "Sequences of Grundy Values in Node Kayles"</b><br /></p><p>Harpreet talked about the history of Kayles and Node Kayles (AKA the Domination Game) and covered Grundy values and the mex rule with examples with excellent figures. She explained very clearly how to apply mex to a list of options by going through each of them. She then showed her calculations for the Grundy values of paths of length up to 21.</p><p><br /></p><p><b>Nadia Bautista-Perez: "Sensing an Invisible Robber"</b><br /></p><p>Nadia described the Localization Game, similar to Cops and Robbers, except that the cop (here the "sensor") doesn't know exactly where the robber is. The sensor does have more power in that they can move to any vertex on their turn. After they and the robber move, the sensor then learns how far they are from the robber. Nadia looked specifically at the case of Broom graphs and she showed that the sensor can capture in moves equal to the number of bristles in the broom.</p><p><br /></p><p><b>Andrea Morris: "Exploring AI Techniques on Game of Thrones: Hand of the King"</b><br /></p><p>Andrea explained how the board game Hand of the King works. This is a kind of impartial scoring game, where both players have the same options each turn, but they keep their own scores. Andrea employed a minimax algorithm which was useful in the last third of the turns. To help their early moves, she used a Monte Carlo Tree Search. The best algorithm they found was a hybrid of the MCTS and Minimax approaches.<br /></p><p><br /></p><p><b>Will DeFroscia: "Plinko Nim"</b><br /></p><p>Will described Plinko Nim, which is a Nim game played on (Binary) trees. Each move has to be on the heap on a leaf of the tree. If a leaf's heap is reduced to zero, the piles above it cascade down all the way to the root, which is removed. The path cases are the same as Tower Nim, but the tree case is not yet solved. Will looked at cases with a simple 3-node tree, and even then the formulas are elusive!</p><p><br /></p><p>I am so glad we had all these great talks! Thank you to all of these great speakers!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-75117464708738057452023-01-25T15:28:00.004-08:002023-01-26T00:02:20.368-08:00CGTC IV Talks, Day 3<p>The last round of talks just happened! They were great again! Here are my summaries.</p><p><br /></p><p><b>Dana Ernst: "Impartial Geodetic Convexity Achievement and Avoidance Games on Graphs"</b></p><p>Joint work with: B. Benesh, M. Meyer, S. Salmon, and N. Sieben. Dana, who also spent time teaching at Plymouth State University, talked about impartial games on graph subsets that contain all shortest paths between vertices in the subset. The games deal with alternating adding vertices to a set and either avoiding a set that "generates" the entire graph if you include all shortest paths between those vertices, or try to create such a set. Dana talked about some instances where the initial positions are 0 or *, including both games played on trees, cycles, and hypergraphs. His team did find initial positions with values up through *7. In addition, they looked at the opposite games, where you remove vertices and avoid/seek the termination of the generating set.</p><p><b> </b><br /></p><p><b>Colin Wright: "MathsJam and Mastodon"</b></p><p>Colin advertised both for MathsJam, which is a meeting series I've never been to, and the Mastodon server Mathstodon.xyz, which is where I joined a few months ago. (You can follow me there: <a href="https://mathstodon.xyz/@CGTKyle">https://mathstodon.xyz/@CGTKyle</a>) </p><p><b> </b><br /></p><p><b>Mark Mitton: "Random Thoughts: Nim is a Hustle"</b></p><p>Mark delivered his perspectives on academia and CGT as a magician. (E.g. he learned Nim as a swindling tactic.) He reminded us it's important to listen to the non-logical parts of our brains because truth is not equal to reason. I took this to mean that we need to not only research our games, but also actually play them as a part of our craft.</p><p><b> </b><br /></p><p><b>Antoine Dailly: "Subtraction Games on Graphs"</b></p><p>(Updated the list!) This presentation covers a bunch of projects with: Laurent Beaudou, K. Burke, Pierre Coupechoux, Éric Duchêne, Sylvain Gravier, Julien Moncel, Nacim Oijid, Aline Parreau, and Éric Sopena. Antoine was interested in how to change subtraction games into graph games. They translated removing counters into removing specific connected subgraphs of that many vertices. Then Antoine's team looked specifically at the case where you're not allowed to disconnect the graph during your turn, naming this the Connected Subtraction Game. They wanted to have nice sequences of nimbers, so they considered graphs where you connect a path of k vertices to a specific vertex in the graph. They showed that you still get periodic sequences. They then showed lots of results for CSG({1,2}) but their techniques don't work for general trees.</p><p><br /></p><p><b>Craig Tennenhouse: "Vexing Vexillological Logic"</b></p><p>Joint work with me. Craig talked about Flag Coloring, which is the game we're using at <a href="http://kyleburke.info/sprouts/sprouts2023/">Sprouts this year</a>. (If you attend, you can play in our <a href="http://kyleburke.info/DB/combGames/flagColoring.html">human tournament</a> or submit a (Javascript) player for our <a href="http://kyleburke.info/sprouts/sprouts2023/flagColoringComputerTournament.php">computer tournament</a>!) In Flag Coloring, you play on an image (or graph) and change a colored region (connected component of one color) by flood-filling it with the color of an adjacent region a la MS paint. Craig analyzed the outcome classes of various flags, then showed some other results we got on 2-color graphs, including showing that it's PSPACE-complete in general. </p><p> </p><p><b>Urban Larsson: "Feasible Outcomes of Bidding Combinatorial Games"</b></p><p>Joint work with: Prem Kant, Ravi Rai, Akshay Upasany. Urban talked about the idea of bidding play in games: before each turn, players blind bid money to decide who takes the next turn. (Using a Richman auction.) Ties are broken with an extra marker, which, if used, is passed to the other player. The winning bid transfers that much money to the bid loser, so there is a static total pool of cash. Urban's team looked at two different scenarios: when players can choose to include the marker in their bid or not. They proved (when you can bid with the marker) that there's a perfect strategy for one player under the second model.<b> </b>Moreover, they get the standard CGT outcome classes as well as extra ones for who has the marker. They looked specifically at the game with integer bids and a total pool of $0, $1, and $2.</p><p><b> </b><br /></p><p><b>Nándor Sieben: "Impartial Hypergraph Games"</b></p><p>Nándor talked about four new impartial games on hypergraphs where players mark vertices on their turn and the end of the game is triggered by the marking of an entire edge. To divide this into two games, we first use the avoid/seek dichotomy. (I heard "achieve" used a lot instead of "seek".) To divide it again to get four, instead of marking, we use "creation" and "deletion" of vertices on each turn. This gives us four games similar to what was seen in Dana's talk: "Achieve", "Avoid", "Destroy", and "Preserve". Nándor notes that for any H, the game DAG for some pairs are complements! He also showed that PRV(H) = AVD(Transversal(H)) and ACH(H) = DES(Transversal(H)), as well as vice-versa, since the transversal is it's own inverse. Nándor proved that if two sets are structurally equivalent and their sizes have the same parity, then the positions will have the same nimber. He also found that there games have an infinite Nim-dimension!</p><p><br /></p><p><b>Svenja Huntemann: "Temperature of Partizan ArcKayles Trees"</b></p><p>Joint work with Neil McKay. Svenja talked about some of the advances she and Neil have been making towards finding the temperatures of Domineering, which is the grid case of Partizan (Red/Blue) ArcKayles (PArcK). She reminded us about temperature and that Berlekamp conjectured that the max temperature of Domineering is 2. She explained that the regular sentiment has been that the grid structure was responsible for this apparent bound, but her team has not found anything of higher temperature "off the grid". Based on their work so far, they boldly conjecture that the temperature of PArcK trees is at most 3/2 and even bolder, that the overall max tempreature is 2.</p><p> </p><p><b>Florian Galliot: "The Maker-Breaker Game on Hypergraphs of Rank 3"</b></p><p>Joint work with Sylvain Gravier and Isabelle Sivignon. In this game, Florian has players claiming vertices and the condition that triggers the end of the game is the creation of an edge. Florian's team looked at the case with small edges and which player has a winning strategy. The rank cases for 1 and 2 have relatively simple polynomial time strategies, so they looked at case 3. This led to a good notation for the positions, including the notion of a "danger" subgraph, which means a region where the Maker can win if the Breaker doesn't immediately move there. They showed that this is solvable in polynomial time, by recognizing a set of complex, but recognizable, situations. The cool thing is that this solves another problem that's been open for a few years! The computational complexity is still open for ranks 4 and 5. (6 and up is PSPACE-complete.)</p><p><br /></p><p><b>Prem Kant: "Bidding Combinatorial Games"</b></p><p>Joint Work: Urban Larsson, Ravi K Rai, Akshay Upasany. Prem continued the topic from Urban's talk earlier in the day, building off of the idea of bidding for who takes the next turn in each game. Outcomes of only the game positions can be described as lists of standard outcome classes, with both different quantities of money for Left as well as with and without Left having the tiebreaking token. Similar to Misere play, Prem's team defines conjugation instead of negatives. They showed that there's no such game, G, where G + * = 0. Without the negatives, they still went to see if there could be numbers and found them! Prim then worked out when numbers are comparable with zero and how to test this property using only 0-bid strategies.</p><p><br /></p><p><b>Nacim Oijid: "Bipartite Instances of Influence"</b></p><p>Joint work with Eric Duchene and Aline Parreau. In the game of Influence, players take vertices from a bipartite graph, scoring points for the size of the immediate neighborhood, all of which get removed. However, players can only play on their side of the bipartiteness, so it plays a bit like bipartite Snort, except with the scoring in addition. Nacim's team decided to use Milnor's rules (universe) for scoring, which doesn't worry as much about which player went last. They are looking for graph families where the analysis is easy, but the simple solutions are elusive. Nacim is very interested in complexity and showed that determining the winnability is PSPACE-complete. Moreover, they showed that detecting draw situations is Graph-Isomorphism-Hard! He talked about computing temperatures in scoring games, including some advances his team has made. (I really want to learn more about Scoring Play!) Nacim's team was able to apply these things to help evaluate paths in Influence.</p><p><b> </b><br /></p><p>This was a great conference! (CGTC is "The Conference" for the field, as Richard put it.) All the talks were great and it was wonderful to see everyone in person for the first time in so long! Thank you again to the conference organizers and hosts!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-89187640018565112602023-01-25T10:18:00.001-08:002023-01-25T10:18:08.129-08:00CGTC IV Talks, Day 2<p> There were great talks again on Day 2! </p><p><br /></p><p><b>Miloš Stojaković: "Strong Avoiding Positional Games"</b></p><p>Joint work with Jelena Stratijev. Positional games are played on a finite set X where the Winning Sets are given subsets. Players take turns claiming elements until all are taken. Then the winner is determined based on different classes of the positional games (e.g. the Strong Maker-Maker condition for Tic-Tac-Toe). Miloš talked about Strong Avoider-Avoider: the first player who claims an entire Winning Set (now the "losing set") loses. If no one does, then the game is a draw.</p><p>Sim, for example, is played on K_c with triangles as the Winning Sets. (Ramsey Theory tells us that a draw is not possible.) It turns out there is a winning strategy for the first player on 3^3 Tic-Tac-Toe! (The potential name Tic-Tac-No was mentioned.) No draws are possible here either.</p><p>Miloš's team found winning strategies for the second player for different Winning Sets of complete graphs. The proofs use a lot of cool techniques including strategy stealing!</p><p><br /></p><p><b>Daniella Popović: "A New Approach to Equivalence of Games"</b></p><p>Joint work with Nikola Milosavljević and Bojan Bašić. Daniella began by reminding us of the equivalence of games. She then presented a new idea: partitioning game DAGs into classes where two positions share a class if they all have options to the same other classes. This is called "Emulational Equivalence" and is flexible because it does not require knowledge of the play convention (Normal/Misere). Her team defined Hackenforb: players alternate deleting edges from a graph. If any component matches a forbidden set of subgraphs, it is also deleted. </p><p>Daniella then showed that Hackenforb and Nim are emulationally equivalent. They were also able to show equivalence from Hackenforb to Chomp! More importantly, they showed there are games that cannot be related to Hackenforb in this way!</p><p><br /></p><p><b>Michael Fisher: "Olympic Games: Three Impartial Games with Octal Codes"</b></p><p>Joint work with Keith Hazen and Craig Tennenhouse. Mike reminded us about Wythoff's Nim and Beatty sequences: using irrationals to define partitions on the natural numbers. He then reminded us about Octal Games, Kayles, Dawson's Chess, and Nim. Then Mike tied this in to Number Theory and Metallic Means: the Golden Ratio and Silver mean based on Pell Numbers. Bronze numbers exist as well, so Mike's team made an octal game based on each. E.g. the Golden Game uses the infinite octal code .1211212112112... (non-repeating!). The P-positions are at 0 = F1, F3, F5, F7, ... (the odd elements of the Fibonacci sequence). The Silver game does the same thing: each index is 1 or 2 depending on which side of the Silver-based Beatty sequences the index lands on. Mike showed graphs of Grundy values, but these did not reveal any obvious formulas.</p><p><b> </b><br /></p><p><b>Richard J Nowakowski: "The Game of Flipping Coins"</b></p><p>Joint work with Anthony Bonato and Melissa Huggan. This talk came about from teaching CGT to a non-CGT faculty member. They tried using Turning Turtles, but then wanted something to include partizan games as well. To do that they created Flipping Coins. This game is played on a string of 1s and 0s: Left can change two 1s into 0s (no matter what is between them) and Right can change a 0...1 to 1..0 (yes, the order matters). Thus, for example, the strings 11 = integer value 1 and 01 = -1. His group found integers and fractions. They discovered that Left has a serious advantage, but that all values are numbers. (That last bit uses the conditions from Alda's talk the previous day!)</p><p>It turns out that both players want to play usually at the right-end of the string, meaning it looks like the analysis could be related to ordinal sums. Richard's team found a complete way to evaluate positions!</p><p><br /></p><p><b>Tomoaki Abuku: "A Multiple Hook Removing Game Whose Starting Position is a Rectangular Young Diagram with Unimodal Numbering"</b></p><p>This is Joint Work with Masata Tada. In this new impartial game, the players play on a Young Diagram and remove one box and the corresponding hook: the boxes directly below and to the right. Then the remaining boxes are shifted up and to the left. This is a very interesting Chomp variant! Tomoaki then described a variant with a unimodal numbering on the boxes. After a move that removes a hook, the player <i>has to</i> go again if they can remove a book with the same multiset. This continues until no such matching multiset move exists. Tomoaki's team found a diagonal expression to classify positions, which they used to calculate many of the nimbers. Tomoaki described an equivalence to a version with shifted Young Diagrams that helped reduce game sizes.</p><p><br /></p><p><b>Kanae Yoshiwatari: "Complexity of Colored Arc Kayles"</b></p><p>Joint work with Tesshu Hanaka, Hironori Kiya, and Hirotaka Ono. Colored Arc Kayles is the partizan version of Arc Kayles where edges are colored by the player (or green/gray for either) who can play on that edge. Kanae reminded us about the relationship between Arc Kayles and Cram and Domineering. Kanae's team showed that Colored Arc Kayles is NP-hard, as well as some parameterized algorithms (still exponential) to solve it that improved on multiple previous results. Some of the parameters they use include the vertex cover and neighborhood diversity.</p><p><b> </b><br /></p><p><b>Eric Duchêne: "Partizan Subtraction Games"</b></p><p>Joint work with Marc Heinrich, Richard J Nowakowski, and Aline Parreau. Eric next presented his result on Partizan Subtraction games, which is just like impartial subtraction, but with separate subtraction sets. Eric's team showed that this game is NP-hard via a clever reduction from Generalized Knapsack. Then they showed the game is quite easy from some small sets and talked about the different styles of sequences of outcome classes. They showed that computing the length of the preperiod of the sequence is NP-hard using the Frobenius problem! Then they looked at the effects of set sizes between the players.</p><p><b> </b><br /></p><p><b>Aline Parreau: "Maker-Breaker Domination Game"</b></p><p>Joint work with: Guillaume Bagan, Eric Duchêne, Valentin Gledel, Tuomo Lehtilä, and Gabriel Renault. In this game, one player (the Maker) is trying to build a dominating set on the vertices of a graph while the other player tries to prevent that. Aline pointed out that you can swap the roles by thinking of the Breaker as trying to created closed neighborhoods. Aline's team showed that the game is PSPACE-complete, even for bipartite and split graphs. They also showed a property that implies a Maker win, then showed that the property is NP-hard to detect, but not in trees! Trees are one of few graph families Aline found to be solvable in Polynomial time. The hardness remains open for interval graphs. There are really interesting relationships between matchings.</p><p><b> </b></p><p><b>Hikaru Manabe: "Four-Dimensional Chocolate Games and Chocolate Games with a Pass Move"</b></p><p>Joint work with Aditi Singh, Yuki Tokuni, and Ryohei Miyadera. Hikaru is a high-school student in Japan! He spoke about Chomp games (on chocolate) but also using only horizontal and vertical cuts. His team looked at staircase functions that result in different board shapes and the nimbers you can get. Then Hikaru generalized to 3-d and then to 4-d! His team continued to use stair-shaped functions to grow boards out from the bitter (poison) square. Then they looked at the relationship with adding a pass move and how that could be modeled by shifting dimensions.<b> </b></p><p><br /></p><p>Amazing talks! Then we had a great conference dinner until way too late. (That's why these weren't out last night.) One more day to go!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-43185365047416468802023-01-23T16:03:00.004-08:002023-01-30T07:52:24.487-08:00CGTC IV Talks, Day 1<p>Woohoo! We're back in Portugal for CGTC! This is my first time at an in-person Combinatorial Games conference since COVID started, and also my first time on the Azores. It is great to see so many colleagues and friends and I've learned a lot already on the first day! </p><p>Let's get down to the summaries!</p><p><b>Opening Ceremony</b></p><p>We had a wonderful intro from Expolab (the facility we're at), the Science Director of the Azores, the University of the Azores, the Lagoa Mayor's office, and Ludus (of course).<b> </b></p><p><b>Aaron Siegel: "Horizons in Combinatorial Game Theory"</b></p><p>Aaron gave a high-level survey of three different topics: Temperature Theory, Misere Partizan games, and Computational Octal games. For the first, he explained that we know how to evaluate single Ko situations in Go, but the theory remains incomplete for more complicated situations. </p><p>For the second, he mentioned that the oldest unsolved problem in Misere Play is probably Dawson's Chess from 1935. For partizan positions, Aaron rephrased G >= H in a way that extends to Misere (and beyond) with the language of absolute universes. There are a lot of questions coming from that point. </p><p>With Octal games, Aaron noted that the longest known period for values used to increase about every 10 years, until 2002, and it hasn't increased yet. Aaron wrote some code to search for periods in octal games and recommended a distributed search among the community to find a new record. Bonus: we would simultaneously be exploring the an open question from the 50s: Do all finite-length octal code games have a finite period?</p><p><b> </b><br /></p><p><b>Alda Carvalho: "<<All is number?>> Not so fast, Mr. Pythagoreas..."</b></p><p>Joint work with: Melissa Huggan, Richard J. Nowakowski, Carlos Pereira dos Santos</p><p>Alda gave a Konane example showing numbers as part of a sum. Then she proved some requirements sufficient to showing ruleset that contains only numbers. These are properties of pairs of positions known as "F-loss" and "descending". Then she showed how to apply this to Partizan (Blue-Red) Chomp to show that all grid positions are numbers. Then she did the same for Push, Shove, Blue-Red Hackenbush, and Cutcake. Furthermore, she proved that if only the descending property is used in the proof, the values are not just numbers but integers! </p><p>I'm excited to see what rulesets this can be applied to in the future. As Alda pointed out, this is also an extremely useful pedagogical tool!</p><p><br /></p><p><b>Paul Ellis: "The Arithmetic-Periodicity of CUT for C= {1, 2c}"</b></p><p>Joint work with: Thotsaporn Thanatipanonda (Edit note: fixed name misspelling. I'm sorry!)<br /></p><p>CUT is a class of rulesets parameterized by a cut set C. A turn consists of splitting a pile of n tokens into d+1 piles, where d is in C. Paul found arithmetic periodicities for all sets of the form {1,2c}. This is a very fast update on earlier results, as the game was initially defined in 2020. Paul's group found some correspondences between sequences in shifted values of C (e.g. {1,6} and {1,8}). Using this they were able to expand {1,6} to any {1,2c}. Despite this, there are still many unsolved families of CUT sets out there!</p><p><br /></p><p><b>Koki Suetsusu: "Some New Universal Partisan Rulesets"</b></p><p>Universal rulesets are those which contain positions for any short game value, as was previously shown for Generalized Konane. Koki found three new rulesets with this property! In Turning Tiles, there is a grid of tiles: Red, Blue, and Black with a token on one of the black tiles. A turn consists of moving the token across neighboring tiles in one (cardinal) direction of your color and flipping all those tiles to black. Koki showed his construction to get all the values. </p><p>Beyond the Door is his second-such ruleset, also played on a grid with a token, where the token can move as many spaces as desired in one direction. Here, the edges connecting spaces are modeled as doors which are colored on each side (the sides can be different colors). Players can only move the token through doors that are their color on the side the token moves from. As with the prior game, vertices cannot be revisited. To show this is all universal, Koki showed a reduction from Turning Tiles.</p><p>Finally, Koki presented Go on Lattice, which is another grid graph game with a token and vertices that cannot be revisited. In this one, the edges are only a single color or dotted. Dotted edges become the color of the opposite player when a player moves the token to either incident vertex. Koki again showed a reduction to this game from the others to show universality. The nice part of that is that he then showed the PSPACE-completeness of Turning Tiles, co-oping the reductions to provide the same complexity for the others as well!</p><p><br /></p><p><b>Carlos Pereira dos Santos: "Chess and Combinatorial Game Theory"</b></p><p>Carlos commented that CGT isn't normally great for Chess, because it's too universal and games don't break down well. He first talked about prior connections between CGT and Chess, then showed ups and integers using a historic Chess zugzwang endgame as a component to build further positions. Then he showed how to create a 1/2. He followed that up by showing how to create a complicated position with <i>three rooks</i> that necessitates understanding how to derive 1/2 + 1/2 = 1 in order to find the White player's winning move! </p><p><b> </b><br /></p><p><b>Bernhard von Stengel: "Zero-Sum Games and Linear Programming Duality"</b></p><p>Bernhard used LP duality and classical game theory notions in zero-sum games, using mixed strategies with simultaneous moves. This leads to the equivalence of min-max and max-min strategies using a linear program. It turns out that the reverse direction also works using skew-symmetric payoff matrices proposed by Dantzig in 1951. Bernhard peeled apart what would happen if you ignored an extra assumption in that direction of the "equivalence", and then showed that you can still complete the proof, so now minimax really does imply the LP duality!</p><p><b> </b><br /></p><p><b>Bojan Bašić: "A Twist on the Classical Prisoners-in-a-Line Hat-Guessing Game"</b></p><p><b>Joint work with: Vlado Uljarevi</b><b>ć</b><b> </b></p><p>Bojan described an Olympiad problem from Russia in 1997: if some sages have to guess the color of the hat on each of their heads, and they can only look at the other sages in the line ahead of them, how many of them can be correct? What is the best algorithm for them if they can agree on conventions ahead of time? The working solution allows all of them them to guess correctly except for the first one (in the back of the line) using a little bit of binary arithmetic. </p><p>Bojan's twist allows them to turn side to side to see all hats in the line, but doesn't allow them to communicate as much info: they say "yes or no" to the question of whether they want to guess their hat's color (saying "no" is still a failed guess) but then they have to whisper the actual guess to the inquisitor so that part can't be used in information sharing with the others. However, everyone does hear whether they were correct in their guess. When c (the number of colors) is 4, Bojan showed that all but the first two sages can guess correctly by encoding the bitwise XOR sum. </p><p>Bojan then showed that this is actually true for c=5 by using the results of the first two guesses as additional information. He then looked at trying to figure out the maximum number of colors that can be figured out for any amount of wrong-guessing sages (in the beginning). For 3, the maximum number of colors they can handle is between 12 and 14.</p><p><b> </b><br /></p><p><b>Hironori Kiya: "Normal-Play with Dead-End-Winning Convention"</b></p><p><b>Joint work with: Koki Suetsugu</b></p><p>Hironori added a convention where Left wins if Right can't play (Normal) <i>or</i> if every subgame of the current position is a Left-End (Misere-ish). This comes from Shichinarabe, which is a popular card game in Japan. (It has some similarities to <a href="https://en.wikipedia.org/wiki/Rummikub">Rummikub</a>.) You win that game by either playing out your entire hand (a Left-end) or if your opponent cannot play, which explains the change from basic Normal Play.</p><p>It's a very interesting combination because it mixes the Normal and Misere rules in a way that makes sense for the many actual play-out games that exist (e.g. Uno). Hironori also showed how to find outcome classes under this play style.</p><p><br /></p><p><b>Silvia Heubach: "How to Win in Slow Exact k-Nim"</b></p><p><b>Joint work with Matthieu Dufour</b></p><p>In Slow Exact k-Nim, each play consists of taking exactly one token from k of the existing piles. Silvia showed how to win when k = n (the number of piles) - 1. Her proofs require a number of cases that use reduced pile combinations to categorize things. (Hilariously--to me anyways--this uses a "No stack Is Really Big" condition, which she shortened to NIRB, pronounced "Nerb".) </p><p>The breakdowns of P-positions often look like well-structured, triangular regions of the 2-d space of values. Each of these triangles either took the form of a checkerboard of P/N positions or a solid block of P or N.</p><p><br /></p><p><b>Keito Tanemura: "Chocolate Games with a Pass and an Application to Symbolic Regression to These Games"</b></p><p><b>Joint work with: Yuji Sasaki, Hikaru Manabe, Yuki Tokuni, and Ryohei Miyadera</b></p><p>Keito (an undergrad in Japan!) talked about a version of Chomp where you make a single cut, vertical or horizontal, instead of removing the grid-poset from a chosen square of chocolate. Keito then talked about<b> </b>what happens when you go to three dimensions. This is all equivalent to easy Nim games, so he talked about what happens when the initial 3-d position is not rectangular, but staircase-shaped instead. Keito's team then used symbolic regression (genetic programming) to discover formulas for the P-positions in the game. Then they were able to do the same for other nimbers. (1 and 2) They used their own library of functions and discovered formulas that gplearn failed to find.</p><p><br /></p><p>What a great day! I'm really looking forward to tomorrow!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-83441456624068854162022-12-23T13:22:00.003-08:002022-12-24T04:57:46.889-08:00Sprouts 2023 Scheduled for April 1<p>I have moved away from New England, but Craig and I are still coordinating for Sprouts. This year we'll have the main event on Saturday, April 1, 2023.<br /></p><p><br /></p><p>The website is up here: <a href="http://kyleburke.info/sprouts/sprouts2023/">http://kyleburke.info/sprouts/sprouts2023/</a></p><p> </p><p>The plan is to have a lot of cool activities again:</p><ul style="text-align: left;"><li>CGT explainer talks.</li><li>Keynote (speaker TBD)</li><li>A human tournament. The game this year is Flag Coloring, a new impartial game of Craig's creation. You can play the game here: <a href="http://kyleburke.info/DB/combGames/flagColoring.html">http://kyleburke.info/DB/combGames/flagColoring.html</a> </li><li>A computer player tournament. Please submit players! Here's the page where we'll run the tournament: <a href="http://kyleburke.info/sprouts/sprouts2023/flagColoringComputerTournament.php">http://kyleburke.info/sprouts/sprouts2023/flagColoringComputerTournament.php</a> You can create a basic player there and test it out.</li><li>Most important: talks from undergrads! Craig isn't teaching a section of his course this year, so we really need volunteers. There are lots of relevant areas we'd like talks in, so please check out our Call for Talks: <a href="http://kyleburke.info/sprouts/sprouts2023/#callForTalks">http://kyleburke.info/sprouts/sprouts2023/#callForTalks</a> Please submit a talk or encourage your students to submit a talk!<br /></li></ul><p>In addition, I may try to hold a local in-person Flag Coloring tournament here at Florida Southern the night before (March 31). I made a new site to use to help run Swiss-style tournaments (meaning no-eliminations): <a href="http://kyleburke.info/swissTournamentOrganizer.php">http://kyleburke.info/swissTournamentOrganizer.php</a> If I wind up having any other local events, I'll add that all to the webpage.<br /></p><p> <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-87225881489815017702022-05-01T10:33:00.004-07:002022-05-01T10:33:30.665-07:00Sprouts 2022: Extra Musings<p>Sprouts 2022 was awesome! It was a bit of a bummer to be virtual instead of in person, but there was a bright side to being virtual: we had a bunch of attendees and even talks that we wouldn't have had otherwise! (We had two attendees from South America!)<br /></p><p>Congratulations to our Popping Balloons tournament winners!</p><ul style="text-align: left;"><li>Craig Tennenhouse won our human tournament. There were ten participants. We did four rounds of Swiss, then cut to the top two (Craig and Svenja). Since one of those two (Svenja) had beaten the other, we decided that Craig would have to win twice in a row in the final to win the whole thing, which he did.<br /></li><li>Ian Grenville's player, NinePiecesOrLess won the computer tournament as the only participant.</li><li>NinePiecesOrLess defeated Craig in the "<a href="https://en.wikipedia.org/wiki/John_Henry_(folklore)">John Henry</a>" match. Congratulations to Ian Grenville!<br /></li></ul><p>Here are some things I learned this year: <br /></p><ul style="text-align: left;"><li>I need to create a webpage to organize tournaments among humans.</li><li>"Partizan" vs "Partisan" is not originally a UK English vs American English thing. Partizan was purposefully chosen for Combinatorial Games because of the political meaning behind partisan. Partisan may have been accidentally adopted by US gamesters as a misunderstanding. I guess we have to go update this in the book!</li><li>We need to manage a mailing list of attendees. I passed out information to attendees as they signed up, but then didn't email out any reminders as the event drew near.</li><li>When undergrads are presenting, I think it would be helpful for them to tell their major and year, for context. We had some great presentations from students outside of Math and CS.</li><li>I need to figure out how to attract more computer-player submissions. I'm willing to take any advice on this! (I know, at least, that we'll need to announce it sooner.) <br /></li></ul><p>We don't have any of the details figured out for next year yet. It may be partially in-person and partially virtual. No matter what happens, I'm looking forward to future years of Sprouts! <br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-60067337802166472402022-04-28T07:48:00.002-07:002022-04-28T07:48:12.677-07:00Sprouts 2022 Talks, Keynote and Session 2<p>Svenja Huntemann, Keynote: "Bounding the Boiling Point" <br /></p><p>Svenja gave our keynote on Saturday (the first Sprouts keynote ever!) that included an overview of temperature and cooling. She included hot, tepid and cold games, using switches as a reference. She then got into thermographs, explaining them from the basics. She talked about thermic options and confusion intervals, using these to show temperature bounds.</p><p>Svenja explained that the boiling point is the supremum of temperatures for a ruleset, then presented Berlekamp's conjecture that the boiling point of Domineering is only 2. Svenja's team found evidence in this direction, showing that the boiling point of snake-like boards is bounded above by 3. She explained the difficulties with generalizing this to all boards.</p><p><br /></p><p>From Session 2:<br /></p><p>Vikram Kher, "NP-hardness of a 2D, a 2.5D, and a 3D Puzzle Game"</p><p>Vikram talked about the computational complexity of two puzzle-based video games (of the three from his paper). For both he showed reductions from 3-SAT. First he showed how to create a Baba Is You board from a 3-SAT formula by using two tokens for each variable. Next he described the reduction for Fez, which uses rotating rings with the literals implemented as vines for the main character to cling to.</p><p><br /></p><p>Emma Jones, "Petals"</p><p>Emma talked about Petals, a partisan game she created. A position consists of a ring of petals: Red or Blue. A turn consists of removing three petals: two of your own color and one of the opponent's right between them. She found patterns that have value zero as well as some strands that have a variety of other values, including stars, fractions, and Up.</p><p><br /></p><p>Ian Grenville, "Loopy Game Values"</p><p>Ian gave the only talk about Loopy Games. (This might be the first ever Sprouts talk about loopy games!) He explained how they work, including the difference between winning and surviving. He showed some examples of game graphs and the Draw outcome class. Then he explained the values On, Off, Dud, Over, and Under. Finally, he talked about how stoppers can be used to simplify analysis, as well as how to deal with some cases where the position isn't a stopper.</p><p><br /></p><p>This was another great group of talks!</p><p>I'll post one more time about other things that came out of Sprouts this year.<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com1tag:blogger.com,1999:blog-49096384337620230.post-64463002644072403352022-04-27T11:09:00.000-07:002022-04-27T11:09:12.345-07:00Sprouts 2022 Talks, Session 1<p>This past Saturday (April 23, 2022) we held Sprouts for the first time since 2019. Here's some summaries of the talks from the first session:</p><p><br /></p><p>Lexi Nash, "Enumerating Distance Games"</p><p>Lexi showed how to use a polynomial profile to count the number of positions on a graph with different numbers of colored vertices. Then she showed how to use Auxiliary Bonds as a better counting method using Cartesian, Strong, and Categorical graph products. Generating functions can be built from regular expressions of colors of nodes for distance games, and she showed many examples of this technique.<br /></p><p><br /></p><p>Khoa Bui, "Reinforcement Learning Based Artificial Intelligence"</p><p>Khoa talked about Google's AlphaGo player and how he used those characteristics to create an AI to play Ultimate Tic-Tac-Toe. (This is the game played on a Tic-Tac-Toe board where each of the nine spaces consists of another Tic-Tac-Toe board. Khoa refers to this kind of recursive game structure as "Stacked".) He used reinforcement learning combined with a Monte Carlo Tree Search to implement his player. He wants to apply these techniques to stacked versions of distance games.</p><p><br /></p><p>Gracie Banning, "Kraken the Numbers!"</p><p>Gracie created an impartial game themed around a Kraken attacking people on a row of boats. Each boat is a Nim Heap, and the Kraken eats from three adjacent piles in the list, taking any triple of this form (floor(k/2), k, floor(k/2)). She showed values for many three-boat positions and proved that these formulas work by induction. She also discovered that four-boat positions are zero when all boats have the same size.</p><p><br /></p><p>Carolyn Curley, "Partisan Peg Solitaire"</p><p>Carolyn created a partizan game based off of jumping peg solitaire games. Players can make jumps in directions based on their identity (Left - Vertical, Right- Horizontal). She solved on and two-row positions by hand, as well as the 3x3 grid, where she found Up and Down values! She investigated a bunch of 3x3 sub-boards, as well as what happens when they are surrounded by extra holes. She looked at many other cases as well.</p><p><br /></p><p>These were all great talks! I'm really amazed at what great work undergraduates do in CGT.<br /></p><p>The next post will cover the Keynote talk as well as the talks from Session 2.<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com1tag:blogger.com,1999:blog-49096384337620230.post-55655788005344722712021-12-19T06:50:00.004-08:002021-12-19T06:50:47.557-08:00Using Spinoza with Python Objects (For in-class exercises)<p>During the COVID-19 pandemic, I started using Spinoza (https://spinoza.cs.brandeis.edu/) in Intro Programming. Spinoza lets students try out solving problems in Python. They get immediate feedback and there's lots of additional pedagogical features.<br /></p><p>It uses Brython to run the code. When it loads each page, parameters for functions are passed as strings. If you try to create the objects in the Test Generator box, they won't pass correctly when Spinoza executes the tests. Instead, you have to generate them using additional code that you put in the Solution box. For example, if you're asking students to write a get_height() method or function for a Monkey class, you have to set things up this way:<br /></p><ul style="text-align: left;"><li>Use a different name in the Method Name field. I always just append "_wrapper" to the end. (E.g. get_height_wrapper.)<br /><br /></li><li>For the number of parameters, use the total number of primitives you'll need to create any objects for the subject and all parameters.<br /><br /></li><li>Still put the original function/method header in the scaffolding box. E.g. def get_height(): If they're writing a method, put it inside the class. If there are other methods they'll need (__init__ or __str__) then you can include those here too. </li></ul><p><span style="font-family: courier;">class Monkey(object):</span></p><p><span style="font-family: courier;"> '''Models a monkey. Attributes: age, height, num_bananas.'''</span></p><p><span style="font-family: courier;"> def get_height(self):</span></p><p> </p><ul style="text-align: left;"><li>In the solution box, there are a bunch of additional things to do:<br /><br /></li><ul><li>Add a function that creates an instance of the object:</li></ul></ul><p><span style="font-family: courier;">def create_monkey(age, height, num_bananas):</span></p><p><span style="font-family: courier;"> monkey = Monkey()</span></p><p><span style="font-family: courier;"> monkey.age = age</span></p><p><span style="font-family: courier;"> monkey.height = height</span></p><p><span style="font-family: courier;"> monkey.num_bananas = bananas</span></p><p><span style="font-family: courier;"> return monkey </span></p><div style="text-align: left;"><span style="font-family: inherit;">(<span>This will change a lot if they've already created an __init__ and you include that in the scaffolding.)</span></span></div><ul style="text-align: left;"><ul><li>If you didn't create the class above, create it here. Also include any other classes you might need that you didn't put in the scaffolding.<br /><br /></li><li>Add the definition of the wrapper. It should create the objects, then call the function/method that the student is writing.</li></ul></ul><p><span style="font-family: courier;">def get_height_wrapper(age, height, num_bananas):</span></p><p><span style="font-family: courier;"> monkey = create_monkey(age, height, num_bananas)</span></p><p><span style="font-family: courier;"> return monkey.get_height()</span></p><ul style="text-align: left;"><ul><li>Add your correct version of the requested function. (E.g. my_get_height().) If they're writing a method, you'll have to write this as a function instead.</li></ul></ul><p><span style="font-family: courier;">def my_get_height(monkey):</span></p><p><span style="font-family: courier;"> return monkey.height </span><br /></p><ul style="text-align: left;"><ul><li>Add the solution function, which does the same thing as the wrapper, except that it calls your function instead of the student's.</li></ul></ul><p><span style="font-family: courier;">def solution(age, height, num_bananas):</span></p><p><span style="font-family: courier;"> monkey = create_monkey(age, height, num_bananas)</span></p><p><span style="font-family: courier;"> return my_get_height(monkey) </span></p><p><br /></p><p>It took me a long time to get this working back in 2020, so I hope this is helpful for other people that want to use Spinoza!<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-90349221272746400292021-08-25T07:01:00.000-07:002021-08-25T07:01:15.402-07:00A CGT Book for Undergrad Math Beginners<p>Craig Tennenhouse and I have finished the first version of our CGT book. Here is the <a href="https://turing.plymouth.edu/~kgb1013/CGTBook.php">book's homepage</a>. We designed it to be used by undergraduates who may or may not be math majors. That meant that we needed to include many discrete math concepts as well, to the point where Craig is currently using the text in his Discrete Math class as well.</p><p>I wanted this project to be a sabbatical project as early as eight years ago, in the spring of 2013, before I knew when my first sabbatical would be. At that time I was teaching my third CGT course at Wittenberg University. All three had been different: the first was as a Math/CS elective, the second was as a first-year college seminar course, and this third time was as an honors course for students with any major. It was during this third time that I realized I wanted my own thorough notes with lots of exercises in them. </p><p>I actually had some experience with text book exercises. Nearly a decade prior, I worked with Otto Bretscher on the solution manual for his <a href="https://www.pearson.com/us/higher-education/program/Bretscher-Linear-Algebra-with-Applications-Classic-Version-5th-Edition/PGM2059295.html">Linear Algebra text</a>. I wanted to have a similar large quantity of exercises so students could practice applying the concepts in a structured way.</p><p>I met Craig in the fall of 2013, and we have collaborated here and there since. I had switched schools, which meant my future first sabbatical was far waylaid. I got my feet under me at a new university, then, just a few years ago, I mentioned that I wanted to write my own book at a CGT event. I explained that I wanted something at a bit lower level that would be more appropriate for general undergrads. Craig asked whether we could write it together, which I was definitely on board with. We both wanted a freely-downloadable book and I was excited to try and adapt my student/instructor dual mode LaTeX code so we could hide some of the exercise solutions. (At this point, I don't think Craig realized just how many exercises I wanted to write.) <br /></p><p>In the summer of 2019, we met and came up with a good outline. Craig and I were on board with each others' ideas, such as doing impartial games before partisan, so things went very smoothly. I used that outline in my sabbatical proposal for the spring semester of 2021. That got accepted, then COVID-19 hit and Craig and I had to collaborate via video calls instead of in person. (Our universities are about a 2 hour drive apart.) We started writing in January, and we just finished enough for our first release. <br /></p><p>The result is a text book appropriate for either Discrete Math or Games. For students who already know the introductory discrete topics, it's easy to skip those sections (laid out as Math Diversions). There are over 400 exercises in the text, and about half of those have solutions in the back. There are also some "Computational Corner" pieces with programming examples in Python. </p><p>We aren't done. We expect to make a bunch of updates as we improve things (and find errors). The book will continue to get updated on the webpage. The chaos of the pandemic caused a bunch of delays, so there are definitely many topics we didn't flesh out as much as we wanted. Nevertheless, we are both very excited and look forward to hearing feedback from teachers, students, self-learners, and even people who just take a quick glance at the PDF. We have a space in the book to thank contributors who point out errors we need to fix. All kinds of feedback are very valuable!<br /></p><p>I want to give an extra ``Thank You!'' to Craig, without whom this project would never have been completed. I am so excited that we managed to get this done!<br /></p><p>Please feel free to use the comments section here as one avenue to leave us feedback.<br /></p>Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-80099881189532497732019-10-23T09:08:00.000-07:002019-10-23T09:08:13.815-07:00Berlekamp Memorial Workshop Talks, Day 2On the second (and final) day of the MSRI workshop, we had more talks, which I've attempted to summarize. As always, please feel free to comment to correct what I got wrong and add things I didn't include!<br />
<br />
<br />
Carlos Santos: "A Universal Ruleset"<br />
<br />
Carlos reprised a talk about a subject Elwyn really enjoyed: finding a universal ruleset. I didn't know this before, but this was a topic that Elwyn even inspired when he asked the question: What is the habitat of *2? This means, which rulesets contain *2? Even more general: which rulesets contain positions that equal all elements of the Short Conway Group? Any such ruleset can be called "Universal".<br />
<br />
Carlos mentioned multiple different procedural strategies he used to try to find such a ruleset. Although, he could have come up with a new one, as he reasoned, "If I invent something, I am cheating." So instead he attempted to use Amazons, Traffic Lights, Konane, then found victory with Generalized Konane, constructing everything in the SCG from that. He was very happy that Generalized Konane already existed in CGSuite, so he could use it without "cheating".<br />
<br />
Afterwards, Carlos spoke briefly about the supposed separation between recreational mathematics and "serious" mathematics, finishing with, "The opposite of fun is not serious."<br />
<br />
<br />
<br />
Svenja Huntemann: "Bounding the Boiling Point"<br />
<br />
(Joint work with Carlos Santos and Richard Nowkowski.)<br />
<br />
Svenja talked about temperature and "How much urgency is necessary to play at a specific position. This is the first talk where I really got an education about Thermography and thermographs. Svenja's work uses thermic versions of hot games--which are games with the same temperature but with only one option for each player. <br />
<br />
This thermic version makes it easier to find bounds on the temperature. The boiling point, then is the suprenum of temperatures of a class of games. If we can find bounds on the confusion intervals of games in the class, we can use that to find the boiling point!<br />
<br />
Svenja discussed the boiling point of Domineering and Elwyn's conjecture that it is 2. There is a bunch of work on this, including an example position with temperature 2. A new result here is that long "snakes" cannot have temperature above 3.<br />
<br />
<br />
<br />
Neil McKay: "Yellow-Brown Hackenbush"<br />
<br />
Neil presented work on a topic Elywn had published in GONC3. Yellow-Brown Hackenbush is different than Blue-Red Hackenbush because players cannot play on components where all the edges are yellow or all the edges are brown. (The three colors of edges: YeLlow edges are takeable by Left, BRown are takeable by Right, and OlivE are takeable by Everyone.) I felt very lucky that I could distinguish been the three colors in the slides. Neil stuck to those three colors to preserve the choices, but admitted that it was hard to see the difference on the actual slides.<br />
<br />
Unlike B-R Hackenbush, every Y-B Hackenbush position is dicotic. Thus, all positions are infinitesimals.<br />
<br />
Additionally, if playing a restricted version on stalks (path graphs), there are some cool simplifications you can do. Neil has done work and solved the outcomes for the game, but not yet for the actual canonical form values. This is something that Elwyn had left as an open problem. Neil concluded by listing a bunch of open problems remaining with both Yellow-Brown and Blue-Red Hackenbush.<br />
<br />
<br />
<br />
Richard Nowakowski: "Pic Ar<span style="color: black;">ê</span>te"<br />
<br />
Richard spoke about Pic Ar<span style="color: black;">ê</span>te, which is Dots & Boxes without the extra move for completing a box. Though it's actually played like Strings-and-Coins. The game was solved on the grid by Meyniel and Roudnoff in 1988. Richard considered playing on a general graph. It turns out that a French team (Blanc, Duch<span style="color: black;">êne, and Gravier) solved this in 2006, except for some cases. Apparently these solutions don't always find the optimal move, but find a move good enough to win anyways.</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">Richard extended this to say that each edge contains a game instead of a single move to cut it so that the edge doesn't disappear until the game there becomes { | }, or exactly zero. Then the overall game uses the same scoring mechanism as Strings & Coins. E.g. edge weight games of +1 and -1 give you a Blue-Red version of Pic Ar</span><span style="color: black;">ête. Richard showed some neat examples with simplications.</span><br />
<br />
<span style="color: black;">"I claim I solved it last night in a dream," Richard said of one of the problems he's looking at.</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;"><br /></span>
<span style="color: black;">Mike Fisher: "Beatty Games: Big and Small"</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">(Joint work with Mike Fraboni, Svenja, Urban, RJN, and Carlos)</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">Mike talked about Beatty Sequences and Games, and actually found the values for positions using different values of alpha. He then dove into the atomic weights. As Mike kept saying, a lot of this was just personal exercises he gave to himself to see what was going on. He found a relationship to the atomic weights and the number of consecutive numbers in the Beatty sequences below the number.</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">Mike then turned his attention to Octal Games, using the octal codes to describe Beatty games. These infinite octal codes cause interesting patterns of Grundy values that Mike plotted. Beyond all this, Mike then took Beatty sequences in another direction, investigating a partizan variant of the Beatty game. He discovered that Richard, Angela, Urban and other had already explained the Golden-Ratio version, so he looked at values and Reduced Canonical Forms of games based on other "Metallic Ratios", e.g. Silver, and Bronze. (I didn't know these existed!)</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;"><br /></span>
<span style="color: black;">David Wolfe: "Distinguishing Gamblers from Investors at the Blackjack Table"</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">David finished up the talks with some work back from 2002/2003. He first started by explaining basic Blackjack strategies, then talked about how card counting can enter into the mix. Counting perfectly can shift the advantage a player has from -.5% to +.5% David wanted to try to gauge the skill of a player by watching them play. He catered to us a bit by asking: "How can we assess the skill of people playing combinatorial games?" He added that the whole thing could be extended to evaluate anyone working in a competitive "gaming" field.</span><br />
<span style="color: black;"><br /></span>
<span style="color: black;">Since the variance is very high, you need to watch a player for a long time in order to try to evaluate this. Also, instead of awarding points for the money a player actually earns, you instead credit them for the expected value of each play. This is then compared to the baseline strategy for the game that doesn't include card counting. This was a really cool approach!</span><br />
<br />
<br />
These talks have been an excellent tribute to Elwyn. I was exposed to so much more about what he accomplished than I had known existed. I'm really fortunate that I was able to attend this meeting. I'm very appreciative to MSRI and all of the organizers, especially Aaron Siegel.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com11tag:blogger.com,1999:blog-49096384337620230.post-79621570184116978642019-10-22T07:09:00.001-07:002019-10-22T07:14:53.073-07:00Berlekamp Memorial Workshop Talks, Day 1Aaron Siegel: "Elwyn Berlekamp and Combinatorial Game Theory"<br />
<br />
Aaron gave an amazing history of Elwyn's 56 years of publishing about games. As he later mentioned, probably none of us at the workshop would have been in the field if it weren't for him. This was such a great talk. Here are some of the things I learned:<br />
<ul>
<li>At 10 years old, Elwyn was allowed to play Dots-and-Boxes with his friends in the back of the room during Math class, as he was bored by the lectures. Thank goodness for understanding teachers! In 2002, nearly 50 years later, he published a book on Dots-and-Boxes. In it there are four theorems. As Aaron summarized, if you only know theorem n and your opponent knows n+1, it's hopeless.</li>
<li>As an undergrad at MIT, Elwyn wrote one of the first chess-playing programs and published columns about Bridge in the newspaper. He would later publish about bridge-playing programs.</li>
<li>He learned about Nim at Bell Labs, where he spent three summers also during college.</li>
<li>He lost to a Dots-and-Boxes-playing program created by other students, so he learned more about it, then came back and won.</li>
<li>He worked at Bell Labs again later and wrote a paper connecting Dots and Boxes to Sprague-Grundy theory. His supervisors challenged him, asking why this was useful. He wrote a six-page response, which earned him vindication from the VP.</li>
<li>Winning Ways took a long time to complete. It began when Elwyn met Richard Guy in North Carolina in 1967. Elwyn proposed writing the book, and Guy suggested they team up with John Conway. The three of them met in 1969 at a conference at Oxford. They spent the next 13 years working on Winning Ways, which was published in 1982. I really had known nothing of the history of the creation of Winning Ways before this talk!</li>
<li>Elwyn got into Go in 1988 while working with David Wolfe. Elwyn created the 9-dan stumping problem, on which he could defeat some of the best Go players as either Black or White. As David explained, this position was about halfway between a natural endgame and the completely contrived boards that they had worked out a theory for using infinitesimals.</li>
<li>In 1996, Elwyn started using Coupon Stacks as a way to get a professional opinion on the temperature of a game.</li>
<li>In 2018, Elwyn published his final paper, this time about Entrepreneurial Chess, which we played at the game.</li>
</ul>
Elwyn's amazing career spanned multiple fields, but, as Aaron mentioned, "I think games were always what he loved best."<br />
<br />
<br />
<br />
Svenja Huntemann: "Introduction to CGT"<br />
<br />
Svenja gave an introduction to CGT to fill an unexpectedly empty slot. Svenja covered impartial games, outcome classes, and basic partisan notions explained via Domineering: fractions, switches, and infinitesimals. Her off-the-cuff version of this introduction is better than my planned and practiced version.<br />
<br />
<br />
<br />
Melissa Huggan: "The Cheating Robot"<br />
<br />
Melissa talked about work with Richard Nowakowski that continues her great PhD work on simultaneous games. In the simultaneous positions, what if Right knows what Left is going to do before they both make their move? (The name is derived from a Rock-Paper-Scissors <a href="https://youtu.be/ZVNnoOcohaU">robot that can cheat</a> and win by very quickly reacting to what the human player does.)<br />
<br />
In this cool model, it turns out that Zero is unique! It can only occur when both players can only move to zero (causing a draw). There can be other drawing scenarios, but they don't act like Zero when included in sums! Melissa took a closer look at Topping Dominoes and used this to show some interesting examples and how to play optimally in these scenarios. <br />
<br />
<br />
<br />
Urban Larsson: "The Fragility of Golden Games"<br />
<br />
Urban talked about some joint work with Yakov Babichenko on non-combinatorial games where payoffs (0 or 1) are on the leaves of a binary tree. Players alternate choosing between the two subtrees at each level, so the value of the game is easily decided recursively. If the payoffs are assigned at random, how often does the overall value change? If the Pr[leaf payoff is 1] is the golden ratio, then we call this a Golden Game.<br />
<br />
Fragility is then based on the Hamming Distance to change the outcome of the game. It turns out that Golden Games are very fragile, while non-Golden games are more robust. As Urban pointed out, "Golden Games are special with high probability." They want to look at some applications to machine learning with an interfering adversary. E.g. how many pixels need to be changed until a machine can no longer recognize that a photo is of either a dog or a wolf? How fragile are these algorithms?<br />
<br />
<br />
<br />
I'm definitely looking forward to the Day 2 talks! Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com2tag:blogger.com,1999:blog-49096384337620230.post-89071143931120160552019-07-01T17:37:00.004-07:002019-07-01T17:37:58.199-07:00Ten Years ProfessingTen years ago today I moved from Massachusetts to Ohio to teach at Wittenberg University. I was recently hooded, affianced, and ready for my shiny new job. I realized quickly that I always needed more time to prepare my teaching materials. A gentle disillusionment that explained why my professors were always so harried. Somehow keeping up hadn't been too difficult in grad school when I taught three courses over three semesters (instead of 3-4 courses each semester) and had other grad students to handle my grading. <br />
<br />
In the past ten years, the race-against-the-clock to implement new course materials continues. Luckily, the payoff in appreciation from students is tremendous. That positive attention from teaching is a fuel that first lent me it's energy in 2001 as an undergrad. I realized how much I wanted to teach then, a feeling reaffirmed when I taught in grad school at BU from 2007 to 2009.<br /><br />Being a good teacher does not require your own creation of course materials, however. I hope my work is actually reusable. If just one other person gets a jump start because they don't have to create all their own content, that would be worth all the extra effort to make it accessible.<br /><br />I can't make everything publicly available, because then students can just copy answers and solutions. Still, I've got <a href="https://turing.plymouth.edu/~kgb1013/lectureNotesLatexStyle.php">student versions of my lecture notes</a>, <a href="https://turing.plymouth.edu/~kgb1013/lectureNotesLatexStyle.php">a LaTeX package for writing lecture notes</a>, <a href="https://turing.plymouth.edu/~kgb1013/?main=teaching">publicly-available course pages (with assignments)</a>, an <a href="https://github.com/paithan/PythonProjectGrader">automated Python (3) grader</a>, and a <a href="https://turing.plymouth.edu/~kgb1013/pythonToJavaTutorial/start.php">Python-to-Java tutorial</a>. <br /><br />Ten years has changed a lot. I'm divorced, a parent, tenured, and have switched schools twice. As of today, I'm our department chair at Plymouth State. (This last bit is definitely not going to help me prepare my course materials.) I've seen a bunch of different students, but I'm still dedicated to their learning.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJF3vFB63rkmo06CkjnUmOroXMpBOqMlvkQbHdSd9flCwZPw__VMlC2ehWyB5WsaqJN3iaWAVKY_3IoFwHG0OkdCskQB0zGCkzLkljIioY775nJY-q3VvmUEickKq96WZQI1w1fLkVItQ/s1600/20190701_171142.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="900" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJF3vFB63rkmo06CkjnUmOroXMpBOqMlvkQbHdSd9flCwZPw__VMlC2ehWyB5WsaqJN3iaWAVKY_3IoFwHG0OkdCskQB0zGCkzLkljIioY775nJY-q3VvmUEickKq96WZQI1w1fLkVItQ/s320/20190701_171142.jpg" width="180" /></a></div>
<br />I got my copy of Games of No Chance 5, which has my Neighboring Nim paper. (I'm finally published in a GONC!) Neighboring Nim was something I proved hard back in July 2009, right after that big move to Ohio at the very start of my career.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-91378171199267994512019-07-01T11:56:00.002-07:002019-07-01T13:54:33.195-07:00Summer Software Engineering ReflectionsMy summer course just ended last week. I taught <a href="https://turing.plymouth.edu/~kgb1013/?course=4140">Software Engineering</a>, a senior-level course--which is against-the-norm for the summer. The class was kept intentionally small because I was ramping up a new project and using the very new style of grading I've been going with since last fall. (I was working on my own project solution concurrently with the students.)<br />
<br />
Without revealing too much to my students this fall, here's the <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph">DAG</a> for Project 0:<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiP4oQFWXjUj55y881WXXFZLdVPopfOFUAo543EVSyaYcaJ0AGKqxrX-P7Ce8MfqvDewv2l63xGDT6hlrGdZzFTfzuDkz9XG3PhwEqy4zEBrtOol5q3gOxIMma4h2tgJlrinuzLNuVYOEA/s1600/Photo+Album+-+Project+0+Reqs.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="750" data-original-width="1000" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiP4oQFWXjUj55y881WXXFZLdVPopfOFUAo543EVSyaYcaJ0AGKqxrX-P7Ce8MfqvDewv2l63xGDT6hlrGdZzFTfzuDkz9XG3PhwEqy4zEBrtOol5q3gOxIMma4h2tgJlrinuzLNuVYOEA/s400/Photo+Album+-+Project+0+Reqs.jpg" width="400" /></a></div>
<br />
<br />
The basic idea behind this is that students can't get points for completing something until they complete the stuff coming before it. They get the points by showing off their code to me in meetings. This both lets them redo stuff if it isn't really finished and breaks up the grading so I don't have to find a block of time to get them all done at once.<br />
<br />
I also like this because there are extra parts that are not necessary for moving on that students can do to exercise their creative sides. I can also let students propose new goals to add to the project DAG, then make that available to everyone in the course.<br />
<br />
The summer course went really well! The projects were all really great, and they were each very different even though we were all working in close proximity. I just barely finished my own version on the last day of class. (Pedagogically, this is upsetting; realistically, it's rarely feasible for me to complete all my assignments before the students see them on the first run. Ten years in and I still can't stay far enough ahead.) These students did amazing work, despite me lagging behind!<br />
<br />
Perhaps most important: this is the first time I got all of the students to really implement OO design patterns. This crop best knows what's going on here.<br />
<br />
It took nine tries to get this course right, but I really hope that this means everything will go smoothly starting this fall with the 10th iteration. (We'll be doing Photo Albums then too, but hopefully they won't get too much of a jump start from this post.)<br />
<br />
My current plan is to have the students program some Combinatorial Games again in the Fall of 2020.<br />
<br />
I have really good plans for the lecture notes for this course, but that's a ways down the line.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-82011816708168705272019-04-06T14:33:00.004-07:002019-04-06T14:33:43.620-07:00Sprouts 2019 Talks<a href="https://turing.plymouth.edu/~kgb1013/sprouts/sprouts2019/">Sprouts 2019</a> was yesterday and we had some excellent talks. Here are my little summaries of them!<br />
<br />
<br />
Nick Paolini: "Machine Learning in Combinatorial Games"<br />
<br />
Nick gave an intro to Machine Learning as a subcategory of AI, including explaining historic data, models, objective functions, and some optimization. He described Erik Jarlberg's recent work on Nim (This explored a question I've been <i>really</i> curious about for years!) Erik's work found that learning players can figure out how to make correct moves in Nim even when trained on a random player. Nick also talked about developments with AlphaZero, an AI player for Go, Chess, and Shogi. Nick then talked about his interest in trying to calculate NimSums via machine learning.<br />
<br />
<br />
Nathan Mozinski: "Displaying Col Moves Online"<br />
<br />
Nate showed the current progress on his senior project: displaying the moves in an active Col game being played between two Java players. That initial code is code I created for my Data Structures class. He's modified it to write the state of the game to a text file after each move. He then added a JavaScript-powered webpage to display that game: <a href="https://turing.plymouth.edu/~ncm1003/SP/col/">https://turing.plymouth.edu/~ncm1003/SP/col/</a>. Right now it displays the current board, the previous board, and the win-loss records of the two players in the on-going match.<br />
<br />
<br />
Craig Tennenhouse: "Towards an Impartial Short Tafl Variant"<br />
<br />
Craig talked about Hnefetafl and some impartial variants he's been exploring. In his rulesets, there is a King and one or more soldiers (who may or may not be attempting a coup). To make it short, the King can only move North and West and the game ends when it cannot move. The different rulesets are each based on a different rule for the movement of the soldiers. Surprisingly, even with only one soldier and a ruleset such as "The soldier must move closer to the king", P-positions appear in very unexpected places! For the rule "The soldier can only move south or east and can't go past the king", Craig seems to have solved for all the P-positions. Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com62tag:blogger.com,1999:blog-49096384337620230.post-42955784665251533772019-01-24T08:35:00.001-08:002019-01-24T08:35:32.730-08:00CGTC3 Talks: Day ThreeMore great talks on the final day of <a href="https://turing.plymouth.edu/~kgb1013/CGTMeetings.php">CGTC3</a>! Here are my summaries.<br />
<br />
<br />
Tomoaki Abuku: "On Nim-like Games Played on Graphs"<br />
<br />
Tomoaki investigated NimG with heaps on the edges. Fukuyama proved a bunch of results about these in 2003. Tomoaki's team used groups of independent zero-sum-valued vertices to find new results, including for many bipartite graphs.<br />
<br />
<br />
Svenja Huntemann: "Enumerating Domineering"<br />
<br />
Svenja build off work by Oh and Lee that counted independent sets on grids (accidentally) counting Kayles positions--as well as Col. By considering each square as falling into one of five categories, Svenja and her team found a formula for the number of positions on an m x n board. Even more complicated is enumerating the maximal positions--in order to build the polynomials, 3x3 matrices are needed instead of 2x2.<br />
<br />
<br />
Valentin Gledel: "Maker-Breaker Domination Number"<br />
<br />
Valentin and his team extended previous work on the Maker-Breaker Domination game. In the game, the Dominator tries to build a dominating set while the Staller chooses vertices to exclude. This new work investigates the number of moves the Dominator needs to win; a pair with each case of each player going first. They found graphs that work for any pair of numbers!<br />
<br />
<br />
Ravi Kant Rai: "Optimal Play in Duidoku Game"<br />
<br />
Ravi found Duidoku--a two-player game based on Sudoku that I had been playing back in 2011 (though under another name). Ravi found a set of permutation strategies for the second player to never lose (so either win or draw) from the initial position. Ravi generalizes this to grids of any size, showing that Player two has the advantage exactly when n is even.<br />
<br />
<br />
Hironori Kiya: "Two Player Tanhinmin and its Extension"<br />
<br />
Kiya introduces Tanhinmin as a combinatorial version of a Japanese card game, Daihinmin. In this game, players play increasing cards (or pass) until one player has emptied their hand (they then win). Kiya's team found a linear-time algorithm to determine winnability (assuming the cards are already in sorted order). Kiya extended this to show that it also works when you add in the 8-cut rule from Daihinmin.<br />
<br />
<br />
Matt Ferland: "Computational Properties of Slimetrail"<br />
<br />
Matt presented work he completed with me while an undergraduate at Plymouth State! Slimetrail is one of the games used by Ludus in their tournaments all across Portugal. Matt proved that a generalized version (on graphs) is PSPACE-complete. Matt showed the gadgets in the reduction from QBF.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-23554779835290403062019-01-24T06:55:00.001-08:002019-01-24T06:55:49.492-08:00CGTC3 Talks: Day TwoThe second day of talks at CGTC3 were also excellent! Here are short summaries.<br />
<br />
<br />
Yuki Irie: "p-Saturations of Welter's Game and the Irreducible Representations of Symmetric Groups"<br />
<br />
Yuki confirmed a long-standing conjecture by Mikio Sato (from the 70's!) stating that Welter's Game is related to the representations of groups. Yuki made the connection by generalizing Welter's game using p-Saturations. In these versions, the nimber values can be found via a formula using addition without carry in base p and Young diagrams!<br />
<br />
<br />
Thane Plambeck: "Shotgun Wedding: EGT & CGT"<br />
<br />
Thane showed a new potential method for combining EGT and CGT. In this, he considers some repeatable economic game where players have a set of options to choose from each round. The application of CGT comes from adding an alternating-turn game to generate those option sets. Thane's method of choosing includes switches, creating a first-mover advantage situation.<br />
<br />
<br />
Alda Carvalho: "Combinatorics of Jenga"<br />
<br />
Alda and her team considered perfect play in Jenga as a combinatorial game. Each row low enough in the tower (meaning, it has at least one full row above it) acts as a *2 component. The total value is not just a simple sum, however, because blocks are added to the top, revealing a new *2 pile after every three moves. Alda generalized this concept as Clock Nim, then found nimbers by considering it as a type of subtraction game.<br />
<br />
<br />
Koki Suetsugu: "On a Wythoff-type Extension of the General Subtraction Game"<br />
<br />
Koki and his team defined a variant of Cyclic Nimhoff ("Restricted Cyclic Nimhoff") where you can only take up to some given q sticks from a pile. Like Cyclic Nimhoff, they found a closed-form expression to find the nimber. He then generalized this further by defining separate subtraction-style sets for each of single-heap-removal moves. In this game, the nimber evaluation uses the Grundy evaluation functions of the corresponding subtraction games whenever the Grundy sequence is a p-stair.<br />
<br />
<br />
Fionn McInerney: "The Orthogonal Colouring Game"<br />
<br />
Fionn and his group have worked on some cool scoring games using two copies of a graph. Players can color vertices on either copy, but must adhere to an additional orthogonality restraint: the ordered pair of colors for any vertex and its copy cannot be repeated. Each graph "belongs" to a single player, but they can color in either; the score is determined by the number of vertices that get painted in the game. Fionn shows that Player 2 can always force a tie when there's a strictly-matched involution, but determining whether the involution exists can be NP-hard.<br />
<br />
<br />
Urban Larsson: "Cumulative Games"<br />
<br />
Urban took a different tack with combining EGT and CGT using subtraction games. Similar to Candy Nim, you keep track of how many total elements you've subtracted, hoping to collect more than your opponents. Unlike Candy Nim, you ignore who gets to play last; you're just concerned about the total collected. In this way, Urban's team was able to connect to extensive form games in EGT. To generalize this for other combinatorial games, a reward function is needed on the moves, along with an outcome function for n-player games.<br />
<br />
<br />
Melissa Huggan: "The Index: a Measure of Equality"<br />
<br />
Melissa delivered an update on her team's progress on simultaneous games. A lot has happened since I last saw this in Lyon. Here a game called Subtraction Squares is used, where players remove a number of squares from a strip. A removal can be made from either end. If we play a continued conjuctive sum, then the index, I(G), is a pair, (x, y), where x is the probability Left can win with a good mixed strategy and y is the same for Right. They can then show that equality of games happens exactly when the indices are the same.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0tag:blogger.com,1999:blog-49096384337620230.post-67992695220183512812019-01-22T06:58:00.001-08:002019-01-22T06:58:14.867-08:00CGTC3 Talks: Day OneIt's so exciting to be back in Lisbon for <a href="http://cgtc.eu/3">CGTC3</a>. Especially after missing it two years ago.<br />
<br />
The first day (Tuesday, January 22) started off with some great talks. Here are some very brief summaries.<br />
<br />
<br />
Richard Nowakowski: "What's happening in CGT (since 2010)"<br />
<br />
Richard opened the meeting by speaking about new branches of CGT that have appeared this decade. His survey included explaining Misere and Scoring play, simultaneous moves, ties, placement games, and more. It was best summarized by his statement: "What did they [BCG] not think about because they didn't need to?"<br />
<br />
<br />
Antoine Dailly: "Connected Subtraction Games on Graphs"<br />
<br />
Antoine described a new game inspired by subtraction games. CSG(S) is a game on a graph where you may remove k connected vertices from G where k is in S and the resulting graph is still connected. His team has shown some nice periodicity results when appending paths to an initial graph.<br />
<br />
<br />
Mike Fisher: "Beatty Games Big and Small"<br />
<br />
Mike explained Beatty sequences, then talked about some new Beatty-based games, including two partizan subtraction games, octal games, and even infinite octal games. The talk name is from these subtraction games: big values occur if the subtraction sets are exactly the Beatty sequences and small values happen if you include 1 to both sets.<br />
<br />
<br />
Carlos Pereira dos Santos: "Extended CGT"<br />
<br />
Carlos considers adding infinity and negative infinity to the set of game options as terminal moves: infinity is an automatic win for left (and vice versa), no matter what else is going on in other parts of a game sum. (He motivated this by Atari Go.) He calls these types of game Race Games.<br />
<br />
<br />
Marc Heinrich: "Partizan Subtraction Games"<br />
<br />
Marc and his team made nice progress on partizan subtraction games. I did not know that outcome classes are periodic here, though values are not always! Marc showed that the sizes of the sets can be much less important that the size of the numbers in the set.<br />
<br />
<br />
Bernhard von Stengel: "Computational Progress on the Catch-Up Game"<br />
<br />
Bernhard described Catch-Up, a kind of scoring game that doesn't use alternating play; instead, whomever has the LOWER score gets to take the next turn. Bernhard showed a really cool method he found to solve this for big games, using the representation of prior choices as a binary address for the table of values being generated.Kylehttp://www.blogger.com/profile/02448231492905040705noreply@blogger.com0