Sunday, July 14, 2024
Context: In my role as division director of Information and Intelligent Systems (IIS) at NSF, I’m sending out a short message to the IIS mailing list on the Second Tuesday Every Month (STEM). This is the installment for July 2024. It’s a few days late, sorry. (I’m doing pretty well on average, though. What’s that expression? “Close enough for government work”?)
Hi IIS Community,
Last time I told you about the AI Aspirations event. This time, I wanted to let you know that videos of the presentations are now posted at: https://ai.gov/aspirations/ . I think it’s interesting to see how IIS topics are on display at an “all of government” level. I am sorry to report that my brief moment on stage to reset the speakers’ podium display was not captured. However, I did get a very flattering shoutout from Arati Prabhakar (director of the White House’s Office of Science and Technology Policy), in her concluding remarks:
https://www.youtube.com/watch?v=MlcSbuW6S3Q&list=PLVq83uNTPbQSVla6Ybce5vOKUoXmGSuS5&index=17&t=70s .
I’m hoping these topics get some traction and AI is able to play a role addressing tough society-level problems.
The other topic last time was a puzzle:
The other day, I was texting with my good friend and superstar researcher/administrator/educator Charles Isbell. He had, once again, rhetorically outmaneuvered me and I acknowledged that sometimes it seems like he is playing three-dimensional chess while I play 1-dimensional tic tac toe. But then it occurred to me that 1-dimensional tic tac toe is moderately interesting, especially if played on an infinite board. Assuming that X goes first, determine whether infinite 1-dimensional tic tac toe is a win for X, a win for O, or a draw (meaning that both players have strategies that they can use to avoid losing, even over an infinitely long game).
I wasn’t sure what people would think of the puzzle, but the replies I got used a variety of adjectives including “nice”, “trivial” (paired with in incorrect proof), “interesting”, “cute”, and “serious” (which was definitely intended to be tongue-in-cheek).
The answer is that it’s a draw, and I was looking for a strategy for O (player 2) and an argument that this strategy guarantees that X won’t win if O follows the strategy. I had an inductive proof to this effect that I thought was clever, but I was sent two tighter strategies, which I’ll share.
“Keep your enemies closer”
Strategy for O: Place an O immediately to the left of the most recent X placed. If this space is already taken, place an O immediately to the right of the most recent X placed. If both are taken, play arbitrarily.
Argument: Let's suppose for contradiction that X wins, meaning that at some point the string XXX appears on the board. Call these positions i, i+1, and i+2. The first of these three Xs to be played must be i (the leftmost X), since O otherwise would have immediately played in one of the empty squares to its left. But the second X can’t be i+1, because O would have moved into i+2, and the second X can’t be i+2, because O would have moved into i+1. So the assumption of three Xs in a row not viable.
Commentary: It is not enough for O to choose arbitrarily between moving to X’s right or moving to X’s left. Doing so could lead to a board that looks like OX-X-XO, which is a win for X no matter how O moves next. That was the most common error I received. Of course, O can consistently move to X’s left when available, or consistently move to X’s right when available. Right outnumbered left 5-to-1 in the responses I got (!). That’s similar to the ratio of righthanded to lefthanded people, but I don’t know if that’s why I got a skewed sample.
“Two peas in a pod”
Strategy: Number the board by the integers, Z. Think of the two locations 2i (even) and 2i+1 (the odd to its right) as a "couple" for all i in Z. Now, whenever X moves into one cell of a couple, O responds by moving into the other.
Argument: Note that any three in a row must have some couple 2i and 2i+1 where X is in both cells. O’s strategy prevents this condition from arising, thus avoiding three Xs in a row.
Commentary: Arguably, the first strategy is nicer because it doesn’t require absolute coordinates, but this one has a certain symmetry to it that I like, where blocking can be to X’s left or right. Plus, it’s just so simple, especially compared to my original (37-line!) solution. One of the chatbots I tried came up with a similar strategy, but grouped cells into triples (“thruples”?), which simply doesn’t work for this problem.
In sum, O can play so that at no point will X achieve 3 in a row. Charles may be playing 3-dimensional chess, but at least I won’t lose in my one-dimensional world.
Until next time!
-Michael