Yup, I was thinking about something like Shogun, however than in a first-person view, so like Medal of Honor or Duke Nukem, but then without guns and with swords in the Middle Ages or in Japan in the time of the Samurai!

Indeed the AI will be hard and the regiment idea would be quite good, however you can start with small groups, say 5 players on each side or even less and build it up...