Since playing a few incomplete games to learn the ropes, I have beaten the "tough" AI 1 v. 1 in the smallest galaxy, and beaten 2 tough AI's in the 3rd smallest galaxy. One game was at beta 4 and one at 1.1.

The 1 on 1 game, I sort of out colony rushed him, then just stayed ahead of him in tech, particularly military tech. That was an easy win.

I thought the game against the 2 AI's was going to be difficult because I was sandwiched in the middle of the Korx and the Torians, and the Torians grabbed a lot of juicy worlds quickly. They out colonized me initially seemed like, but for some reason they let me flank them and take colonies on the far reaches of their empire. I had maybe 2 or 3 extra colonies, but they had nice worlds, and spent a lot less time and effort to get them. The Korx only grabbed 4 worlds. Since I was playing Yor and made evil choices, the weak Korx were my friends and the Torians did not like me a bit. Since the Korx were no long term threat, I made sure they would stay with me, trading a bit and giving them some useless tech gifts. The Torians had much better resources available to them, which they did use. Nonetheless, they went seriously wrong somewhere in the middle game, not getting military techs. Just as I was spitting out 5 medium ships with 4 mass driver/4 defense against their tech (mass driver), they built an armada of small ships with 2 mass driver and no defense. They just sat them on their planets doing nothing. Once I started my attack, they built a lot of transports that they sent out unescorted which were picked off again and again. This was on 1.1.

I am not really eager to go higher than tough because the AI cheats, but I guess I'll have too. I don't have the patience to play too much bigger of a galaxy than the 3rd smallest. Maybe could go up a size or two and add another AI if that would make it harder.

I guess some AI are different (tougher?) than others...don't recall the AI in the 1 v. 1, but the Torians at "tough" certainly were not tough.