Math317Fa26 Lec19 BattleshipChomp
Watch on YouTube →
Overview
Steven Miller uses Battleship to show how row and column totals can describe multiple valid board layouts, then connects the same information and resource-allocation ideas to pooled COVID testing and integer programming. He finishes with a non-constructive strategy-stealing proof that the first player wins Chomp, followed by a brief Newton iteration for approximating √3.
Key takeaways
- Row and column totals can fail to identify a unique Battleship layout: two singleton ships on opposite diagonals of a 2-by-2 region have the same margins.
- When infection is rare, testing n rows and n columns in an n-by-n pool uses 2n initial tests; if two rows and two columns are positive, at most four intersections need individual retesting.
- Binary variables xᵢⱼ, together with row-sum and column-sum constraints, encode Battleship occupancy as an integer-programming feasibility problem, but matching total counts alone is not sufficient.
- Modeling actual ships requires more than cell counts: ship lengths, orientation, contiguity, and placement boundaries must also be represented in the constraints.
- Chomp's strategy-stealing argument proves that the first player has a winning strategy without constructing that strategy, illustrating the difference between proving existence and finding a solution.
- Newton's update xₙ₊₁ = ½(xₙ + 3/xₙ) approximates √3 with extraordinary speed, reaching errors near 10⁻⁵⁹ after six iterations.
Chapters
- Steven Miller introduces a Battleship puzzle where row and column totals reveal how many occupied cells appear in each line.
- Zero clues are especially useful because they eliminate an entire row or column; one clues are the next most informative.
- Small fleets, such as a single 1-by-1 or 1-by-2 ship, provide simple cases for testing whether the clues determine a unique layout.
- Two 1-by-1 ships placed on opposite diagonals of a 2-by-2 region produce identical row and column totals.
- The example shows that margins do not always uniquely determine a board, even when the total number of occupied cells is known.
- Puzzle makers typically require a unique solution, as in a properly constructed Sudoku, while real-world measurements may remain ambiguous.
- Medical imaging must balance diagnostic information against the cost and risk of taking additional pictures, including radiation exposure.
- COVID testing also consumes finite money, staff time, laboratory capacity, and tests, so testing everyone repeatedly is not automatically efficient.
- Operations research asks how to allocate limited resources to gain useful information while weighing the added safety against the cost.
- Arrange n² students in an n-by-n grid and combine samples by row and by column, requiring 2n pooled tests instead of n² individual tests.
- A negative row or column pool rules out infection for every student in that line, assuming perfectly accurate tests.
- If exactly two rows and two columns test positive, only their four intersections can contain infected students, so individual retesting requires at most four more tests.
- The resulting 2n + 4 tests can be far fewer than n² when infection is rare, though the method becomes less advantageous as positive pools increase.
- Define binary variable xᵢⱼ as 1 when cell (i,j) is occupied and 0 otherwise.
- Set each column sum equal to its clue Cⱼ and each row sum equal to its clue Rᵢ.
- Equal total row and column counts are necessary for a valid board, but they do not guarantee that the clues have any feasible arrangement.
- A proposed clue set can fail when a row demands more occupied cells than the available positive columns can support.
- Cell-occupancy variables alone describe a footprint but do not ensure that the occupied cells form the required connected ships.
- Ship-specific variables can encode lengths, such as a carrier of five cells and a battleship of four, as well as ship placement.
- One formulation can track a ship's starting cell and orientation, then require the consecutive cells along that direction to be occupied.
- Alternative formulations can impose a ship's length and neighboring-cell constraints, but boundary cases and orientation rules must be checked carefully.
- In Chomp, players alternately eat a chosen dot and all remaining dots above and to its right; the player who takes the last dot loses.
- For any finite board, either the first or second player has a winning strategy if both play optimally.
- Assume the second player has a winning strategy after the first player opens in the upper-right corner; the second player's response can then be used as the first player's opening move instead.
- That move swap gives the first player the winning position by contradiction, proving a win exists without identifying a concrete winning strategy.
- The iteration xₙ₊₁ = ½(xₙ + 3/xₙ) converges rapidly to √3.
- Miller notes errors of roughly 10⁻⁹ after three iterations and 10⁻⁵⁹ after six, connecting the calculation to fixed-point methods.
- The next class is previewed as an operations-research treatment of the German tank problem, with probability and statistics.
Transcript excerpt
0:00 All right, so welcome to math 317 operations research. Today we're going to be doing the battleship game and applications of that to the pandemic response, non-constructive proofs, and maybe a little bit more on fixed points. And then Friday's class we're going to do an operations research exercise. We're going to do probably the German tank problem. It is a great opportunity to talk about probability and statistics. If you have not taken those courses, I strongly urge you to take them before you graduate. I used to say you would have a job if you take these classes. You may not like your job, but you will have a job. With the way things are rapidly changing, I can no longer make that guarantee. But I think you would still have a decent chance. How many of you have ever played battleship?
0:47 Okay, and when you're playing battleship, what do you need? >> Enemy ships. >> Enemy ships, which means you basically need two players. So not everybody has a friend, unfortunately. So we're going to play a simpler version of battleship where you don't need a friend. How many of you have seen the one-person battleship game? So what they do is they give you numbers in each row and each column that tell you how many ship pieces are in that row or column. And then can you reproduce the deployment of the fleet based on those numbers? So for instance, you know that if they tell you that this number is a zero, you know there's nothing in the first row. If this is a zero, you know nothing in that column. It's It's similar to a lot of these
1:38 things where or if you've played Minesweeper. >> Yeah. >> I am actually under treaty obligation. I
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.