Bandwidth Requirements
It's really hard to quantify exactly what bandwidth AI War requires, because that depends on a ton of factors. If there are more players, that greatly impacts the bandwidth requirements of the host, but to a far lesser extent each client. There is only one thing that actually causes bandwidth to even be used in AI War: commands. This is commands from the players clicking stuff to create ships or order them around, or commands from the AI (running on the host only) to order its ships around. The AI commands use about the same bandwidth as one player under normal load.
With a slow or packet-lossy connection, large commands (ordering around thousands of ships with one click) will cause lag. But, assuming that all players just sit there staring at the screen and not issuing any orders, it would just be the continual smaller amounts of AI orders, and the turn-synchronization orders themselves, which would mean any spikes would just be based on packet loss or routing problems based on latency. In other words, the more players are clicking around, the more load it creates, but generally that load is low enough as to not cause anything noticeable on most connections.
I wish I could be more specific with this, but to some degree you just have to try it and see with your specific connection, since there are more factors than just the bandwidth itself: stuff like latency, current business of that ISP and the backbone, and of course all of the factors such as the size of the game and what all is going on in it. Basic broadband will not work as well by any stretch, but I have played AI War with two players and no lag over a 3G phone being the modem for the client, with basically I think 1500 or 1600 Kbps down on the phone, and something like 150 Kbps up on the phone (I may be remembering wrong, but it was about that). So the floor is somewhere below that, but I don't know precisely where it is.
Latency Notes
AI War runs with 200ms turns under the hood. That is how long the game runs by default before it has to pause waiting for more input if more input has not yet arrived. The networking for the next turn happens simultaneously with the simulation for the last turn, which means that you need around a 100ms roundtrip time in order for it to be lag free. At anything higher, you'll see a corresponding percentage drop in game speed: at 300ms roundtrip time, that would lead to each 200ms turn having a 400ms pause at the end of it, which would be incredibly frustrating for players.
Network Skip
However, we do have a solution for this, as well as the general too-low-of-bandwidth problems. Basically, this is called Network Skip, and allows you to increase the length of game turns by 45ms per skip. So, when you have a network skip of +1, the turns are 245ms instead of 200ms, which means that to have no latency you need a roundtrip time of 122.5ms. If you use a network skip of +16, the turns are 920ms, meaning your roundtrip time has to be 460ms to have no lag. You can set network skip to whatever value gives you the best game experience, simply by using Ctrl+plus/minus while playing the game; if performance is bad at the start, then later gets better as you play, you can adjust as you go.
However, there is a downside to having longer turns (higher network skip): and that is command latency. The time it takes for a command to be issued from when you give it is 2x the time of the the turn length (since turns are scheduled, and since the network is run simultaneous, that is unavoidable). So, basically, you will wind up with normally it taking 400ms for the game to issue a command you give. At +16 network skip, it would take a whopping 1.8 seconds between your issuing an order and it happening. That can be frustrating on its own, but it is playable and if you are not a fast-clicker it matters comparably little: at least your game simulation is running at full speed, and the clock is ticking at a regular interval, etc. It's like playing with a radio delay to mars, rather than playing in slow-mo, basically.
Suggestions for playing on slower connections
So, the above gives you a lot of information on what is technically going on under the hood, and general thoughts about requirements and some solutions. Here are some tips on generally using those above facts to maximize performance if you are having issues:
1. Use network skip until the host doesn't see "(WAIT)" popping up next to player names. Clients do not see this.
2. If the game has been running fine for a while, the host may want to try reducing the network skip to see if a lower value is now acceptable.
3. Generally speaking, it is not a good idea for the host to also host voice chat, unless the host as a super good connection.
4. Generally speaking, players with very bad connections should not host voice chat, and they may want to consider not using voice chat at all, instead typing to players. Voice chat alone can eat up 30% of the bandwidth of an average broadband connection, or more in some cases.
5. Generally smaller maps will not really perform better in terms of the network, because there is a cap on how many commands the AI can issue per game turn. Granted, in smaller maps there are fewer ships for the AI to order around at any given point anyway, so you will see some benefit, but it's not going to make much difference between 60 and 120, for instance, because it will probably be at the cap either way, there. Might be some difference between 10 and 60, though, but I doubt it would be substantial. So play on the map sizes you want, in other words.
6. Playing with fewer players will lessen the load greatly on the host's network connection, and to a lesser degree for the clients. As far as the clients go, the only added load from having more players is the extra commands that those other players are issuing. Assuming that those players just sit there and issue no commands, the added network load on the clients is precisely zero. Realistically, though, they will generally be causing more commands and thus causing more load simply because there are more people telling ships what to do. It all depends on how click-happy the other players are, but if you're concerned about your network speed then keeping it to 2-3, maybe 4 players, is probably a good idea. And then if that works well, you can scale up to larger games if you want to try it.
This is such a good question that I'm moving it to tech support and stickying it!
