First AI i rolled was Toku. Thoughts? This was first game I rolled and I went random. Or should I start more centre of the map.
The general location of start dictates how the game will pay out. If you spawn center of the map, you're going to be DoW'ed a lot on all sides unless you dogmatically fall in line with one of the religious blocks, which only keeps one side of your empire safe, and only if stack 5 longbows + walls/castle, otherwise the aggressive AI will backstab you even at Pleased/Friendly. The good news is you don't have to worry about fishing boat harass when you're in the center of the map.
That being said, despite Tok'us starting tech (fishing), his traits are (Agg/Pro) are the best for spawning in the center of the map. Make sure you kill the nearest neighbor that's Imperialist or Creative (enemy leaders with these traits will suffocate you if they aren't killed asap). Chop and whip three axes from 4-5 cities and kill them fast, you can spent the early idle turns slow building a barracks while researching working techs and bronze worikng.
Toku's traits work best when paired with other civs other than Japan (unless you get a coastal start), but you should overall be fine.
I do however recommend rerolling a good coastal start since you do start wish fishing as Japan. Make sure there's two fish and marble so you oracle CoL for courthouse when you conquer the most threatening neighbor, try to bulb math and research currency after (make sure a library completes before the oracle in a city different than the oracle for a GS instead of GP) and get the Colossus
As for Permanent Alliances, I have never won on Immortal without securing a PA, very rarely won Emperor without a PA (post 2300 AD victories), and even Monarch can be an extreme grind without a PA (post 2050 AD victory).
Safe leaders to invest your PA's in are the religious leaders, such as Izzy or Hattie or Saladin, when you have a coastal start, or the "Reasonable Warmongers" such as Ragnar, Shaka or Monty, if you spawn center of the map. You'll be in so many wars if you spawn center you're better off declaring them yourself at Shaka's request for the +500000 diplo and PA.
You will have to be Friendly and either have massive tech lead (at the expense of army size,), or a massive army (at the expense of being behind in tech) for them to accept your PA offer; leaders like Elizabeth excel at the former; leaders like Toku excel at the latter. The only loophole is if you want a PA with a religious leader, and only you and that leader share the religion, in which case, being Friendly is the only requirement to get the PA instantly upon researching communism.
A lot of my games should be tited "Me and Izzy against the world." So if just you and the religious leader of another civ are the only ones sharing the religion, when they ask your help in war, accept and Dow whoever they ask you to, capture cities for them and them gift them the cities you capture (this allows you to abuse the AI's handicaps for maintenance costs), because you're gonna PA with them later anyway, so why have a distant captured city drain your wallet when you can just give to Izzy/Hattie/Saladin, which allows them to build monster stacks of doom. I usually leave the game after I secure the PA with Izzy/Hattie, because combined we're both so dominant the game is already won lol (thanks to gifting captured cities earlier in the game).
The most fun games you'll have are when Monty spreads his religion and sends all his minion civs at you and your religious block. Those games typically go in the modern/future era. Pure bloodsheed all game. Christo Redentor is a must have in these games if you're not Spiritual civ.
Also dont' get immediately discouraged if a leader like Zara or Surry mananges to take 2/5 to 3/5 the map. You can send spies and put yourself in starting civics (barbarism, decentralization) and keep changing their civics and virtually halt their research for the rest of the game ( do not allow them to be in State Property, Free Speech, etc; switch them to all of the starting civics + vassalage (since its high upkeep)). Of course only do this after you secure a PA with a good techer like Mansu or Wilhem. Eventually you'll have tanks and Zara/Surry will still be making elephants. Also, don't underestimate what a stack of 400+ war elephants can do, even if you have tanks (yes...400 Ballista+ Elephants, I actually had to nuke it)
I also swear by the Chicen Itza wonder when you spawn middle of the map (. I will not play without stone if I spawn center of the map on Immortal,and its the only wonder I build on Immortal, other than the Oracle or the Great Wall. If I spawn coastal then I aim for the Colossus instead of the Chicen Itza, since the commerce allows me to defend via slight tech advantage (and with less units, since there's only one side of my empire to defend).