Defense in Depth Game

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

Imagine a game played on an N by N grid in which there is a very fast runner who can make two moves in a turn where each move is southward or southwest or southeast.

For example, if the runner R starts at the top as shown

...R..
......
......
......
......
......

Then he can end up in any of the places having a lower case "r":

......
..rrr.
.rrrrr
......
......
......

That is, he must move one space or two spaces, but each move is one southward and at most one east or west. The tackles, and there are k of them (defender will choose) can each move one space in any direction: north, south, east, west, northwest, southwest, northeast, or southeast.

Starting here,

......
.T....
......
......
..T...
......

the northern most one can end up in the top 8 places and the southern most one can end up in the lower 8 places.

ttt...
t.t...
ttt...
.ttt..
.t.t..
.ttt..

The tackles win if they prevent the runner from moving. For example,


......
......
......
....R.
...TTT
......

The runner wins if it reaches the southern most rank.

Here is the game setup. You will be given a 10 by 10 grid. There is one runner and k defenders. The defender gets to pick k, but then his/her opponent gets k too when he/she is the defender. The runner begins anywhere he wants on the northern-most row. The k tackles then place themselves anywhere that is at least 3 spaces away from the runner. The runner has the first turn. After that, play alternates.

Your Task

To win, you must both trap your opponent when he/she is the runner using fewer defenders than he/she uses when you are the runner.

Architecture Team

Support the visualization of the game. So, you will show the grid and then show the evolution of the moves. You will also declare when the runner has reached the southernmost end of the grid or when the defender has trapped the runner.