8
$\begingroup$

This is a special case of a question asked but unanswered at MSE:

Consider the combinatorial game CHOMP (presented as in the linked notes so that the "poison" square is bottom-left). In any $2$-by-$n$ board, the "almost-passing" move (taking the top-right square) is winning; moreover, whenever it is a winning move, it is the only winning move. Intiutively I would expect it to be "usually" bad, but I don't see that it is:

Are there $m$-by-$n$ CHOMP boards on which "almost-passing" is a winning move for player 1, but with $\min\{m,n\}$ arbitrarily large?

Embarrassingly, I don't even know of an example going above $2$. Turns out there's a few - computer search has verified $6\times 11$, $6\times 15$, and $6\times 27$ (thanks to Peter Taylor and Sam Benner in the comments below). This raises a natural related question: are there infinitely many $n$ for which the $6\times n$-game is of this type?

$\endgroup$
10
  • $\begingroup$ (I was going to make a comment about how this move is important in the strategy-stealing argument that Chomp is a 1st player win, but I see you mention that as motivation in the MSE question, so I'm just leaving this parenthetical instead...) $\endgroup$ Commented Sep 7, 2023 at 1:41
  • 2
    $\begingroup$ @SamHopkins Oh indeed! That argument is my all-time favorite proof in mathematics, by the way, partly for nostalgiac reasons: it (circuitously) played a non-negligible role in getting me into logic. $\endgroup$ Commented Sep 7, 2023 at 1:50
  • 1
    $\begingroup$ Your memory appears incorrect, but if we assume you misremembered $\max$ for $\min$ some quick calculation shows $6\times 11$ as an example. $\endgroup$ Commented Sep 7, 2023 at 8:04
  • 1
    $\begingroup$ Other than $2×n$, $6×11$ is the smallest example, and $6×15$ the next smallest. I'll let you know when my computer reaches $6×19$... $\endgroup$
    – Sam Benner
    Commented Sep 7, 2023 at 16:26
  • 4
    $\begingroup$ I suggest we call it simply the minimal move instead of the "do-almost-nothing" move or the "almost passing" move, as the latter are cumbersome and not more descriptive than "minimal". But those phrases do seem fine to help motivate the question. $\endgroup$ Commented Sep 8, 2023 at 14:20

1 Answer 1

5
$\begingroup$

Using this code, I've searched up to $15×15$ and $6×65$. Improved memory management is required to go further. The only large (not $2×n$) boards on which the minimal move is winning in this range are $6×11$, $6×15$, and $6×27$.

Per my answer on the linked question, there are a finite number of boards $m×n$ for which the minimal move is winning for every $m$, so I conjecture that these are all the $6×n$ boards.

#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <iterator>

std::unordered_map<std::string, bool> cache;

std::string getCacheString(std::vector<int> const &game){
    std::ostringstream ss;
    std::copy(game.begin(), game.end()-1, std::ostream_iterator<int>(ss, ","));
    ss << game.back();
    return ss.str();
}

int checkCache(std::vector<int> const &game){
    std::string str = getCacheString(game);
    if (cache.find(str) != cache.end()){
        return cache[str];
    }
    return 2;
}

void addCache(std::vector<int> const &game, bool result){
    std::string str = getCacheString(game);
    // std::cout << "Added " << str << " to cache: " << result << std::endl;
    cache[str] = result;
}

bool checkGame(std::vector<int> game);

bool checkMove(std::vector<int> game, int x, int y){
    if (y == 0){
        while (x < game.size()){
            game.pop_back();
        }
    } else {
        for (int i = x; i < game.size(); i++){
            game[i] = y < game[i] ? y : game[i];
        }
    }
    int prevScore = checkCache(game);
    if (prevScore == 2){
        return checkGame(game);
    }
    return prevScore;
}

bool checkGame(std::vector<int> game){
    for (int i = 0; i < game.size(); i++){
        for (int j = 0; j < game[i]; j++){
            if (i == 0 && j == 0) continue;
            if (!checkMove(game, i, j)){
                addCache(game, true);
                return true;
            }
        }
    }
    addCache(game, false);
    return false;
}

int main(){
    cache["1"] = false;
    for (int i = 3; i < 1000; i++){
        bool result = checkGame({i, i, i, i, i, i-1});
        std::cout << i << ": " << result << std::endl;
    }
}
```
$\endgroup$
2
  • $\begingroup$ I guess "up to $15\times15$ and $6\times65$" means "all $m\times n$ where either $m\le15$ and $n\le15$ or else $m\le6$ and $n\le65$"? $\endgroup$
    – bof
    Commented Sep 8, 2023 at 22:05
  • $\begingroup$ @bof Yes, that's correct. $\endgroup$
    – Sam Benner
    Commented Sep 8, 2023 at 22:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .