I studied this problem for a few months and the solution I found most economical (meaning speadup vs. difficulty programming) would be a hierarchial grid. There aren't alot of references to it online, but basically you just construct a series of grids with different resolutions.
X, 2X, 4X, 8X, etc.
Place bots in whichever grid level is the smallest that can still hold it (or there are other methods for placement). For shots you'd only need to check against adjacent grids, which brings the problem down from n^2 (or kn where k is the number of shots and n is the number of bots) to ck (where c is a constant).