Anjali Bhagat, "Fork positions and 2-dimensional Toppling Dominoes"
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.
Ankita Dargad, "The temperatures of Robin Hood game"
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.
Prem Kant, "Bidding Combinatorial Games"
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.
Johan Wästlund, "Games and optimization on random structures"
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!
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!
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.
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.
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!"
This was such a cool talk because of how the different results related back to games in amazingly unexpected ways!
Satvik Sharma, "Symmetry in Combinatorial Games"
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.
Today was another great day of talks! These are excellent!
No comments:
Post a Comment