The old saw still rings true: turn your research problem into a military application and the DoD will likely fund it. Perhaps instead modeling a chess board as a graph you model passable routes in a mountainous terrain. Instead of chess pieces, maybe the forces you're modeling are small groups with different movement characteristics?
"In this paper we assume all forces are ground-based and beyond any hope of air-support or resupply. Historical analysis of battle-field circumstance will reveal numerous instances--even in the modern period--of such occurrences. A more general result is beyond the scope or intention of this paper."
