Maze-like maps are fun, but they unfortunately makes the game against AI much easier.
I was thinking about 4D hyper-cube map with attached opposite side (sorry, can't recall how it is properly called). Idea is that on 3x3x3x3 (81 provinces) hypercube any 2 provinces will be neigbours. On larger one - 4x4x4x4 some pairs won't be neighbours any more, but it will still be very open map. It sounds like a good idea, but I'm not sure how to visualise it in 2D. Ok for 3x3x3x3 map you don't really need anything complex - you just know that everything has a common border. But figuring out what borders and what not on 2D visualisation of 4x4x4x4 hypercube is non-trivial and '8' won't help much because there will be so many edges indicating connections
