This is a pretty easy scenario. At least, you don't have to cheat to win. All you need is good, solid play. It's probably good enough to just produce a bunch of Axemen and archers and win that way. However, that's a measure of how easy the scenario is, not how good the strategy is.
The fundamental problem you have to deal with here is that you don't have any gold or stone beyond your initial stockpile, and none can be obtained easily. However, it's a water map, so your fleet can do almost all the work. The best strategy in this scenario is to turtle until you have a powerful fleet and then to advance behind it, seizing resources as you go.
Start by producing a bunch of villagers. Get as many as 15. Put no more than 6 on food, because you won't need a lot of food at this time. Get a Scout immediately and explore as much of the map as possible. You can get as far as the north map corner, and maybe halfway along the SW side. In all that territory, all the ore you can access is a single gold mine on the NW side of the map.
Build a dock as soon as you know that this is a water map. Produce some Scout Ships and explore the sea. There is a heavily fortified island in the centre. Stay away from there. Explore the rest of the map if you like, but there isn't much point, because you won't be able to accomplish much. Just park half your ships on the left side of your base and half on the right side. You will need about 5 War Galleys on each side. Fishing is a poor idea at this time, because it's too dangerous.
Unless you want to produce and lose a bunch of Axemen, you will need a complete wall-in on each side of your base. Push the SE one as far forward as you can. The north wall should connect with the forest right beside your base. This won't give you a lot of space, but it will have to do for now. You should eat the Elephant King near your base before you build this wall. Use a minimum of 5 villagers to hunt it, and be very careful. The SE wall needs to be finished quite early. You will need to be careful where you get wood, because you don't want to cut a hole through the forest on the NW side of your base. You cannot afford any Towers at this time.
Produce one catapult and take out the Yellow Tower nearest your base. This will make it impossible for you to get a priest at this time. When you have about 10 War Galleys, produce a Transport and take a group of villagers over to the gold mine on the NW side of the map. Build a wall north of it, and then suck in that gold. You will now be able to afford one priest and 3 Cavalry. Save the rest of your gold for contingencies.
Both Yellow and Brown should be attacking you continuously by now. They send single warships and groups of ground troops. Fortunately, they don't try to invade you. Attacking Transports probably won't get through, but you don't want to be dealing with invasions. As long as the ground attacks come in along the coast, you won't need to worry about them, but when they start to come in along the very SW edge of the map, you will need to get some archers. Invest in about 5 Composite Bowmen. Basic archers will be too weak. You will most likely have to be building buildings outside your initial wall-in by now. You will probably need a second Transport to ship your ground units back and forth across your walls. You can try attacking Yellow with your cavalry, but you probably won't make much progress at this time.
The map is very unfavorable for your fleet operations. Not only is it completely open to your enemies, but the Red fortified island really cramps your maneuvers. The enemy fishing ships are actually more dangerous to you than their warships, because they will suck your warships into range of the Red position. Because you cannot possibly track all of your ships continuously, you will need to give them "stand fast" orders. However, this makes them vulnerable to enemy warships. The only solution to this problem is to totally saturate the map with your warships. You will need at least 15 War Galleys.
When you have a strong fleet and some Cavalry, crush Yellow. The main objective is to eliminate their villagers. One way to do this is with cavalry raids. The other way is to attack their dock with a naval squadron. When no more repairmen come out to play, and no more ships are being produced, you can conclude that Yellow is out of food and wood. At that point, you should leave their dock alone, because you may need it for gold later. Use your catapult to eliminate some of the Yellow Towers. You may or may not be able to find some ore in the Yellow base, but don't count on it.
About this time, Brown will enter the Iron Age. This isn't really a problem for the naval combat, because Yamato War Galleys are about as good as standard Triremes, but you don't have enough Bronze Age ground troops. The only reasonable place to get more gold is near the north corner of the map. Send your cavalry and catapult over there to eliminate the Brown Towers, wall the area off, bring in some villagers, and suck in the gold. Of course, you will also need to move at least a third of your fleet into the area.
You should be able to claim 4 full gold mines in the north map corner. This will get you into the Iron Age, which is the main thing, and allow you to get some more high-tech units and technology. However, you will definitely want more gold. Make sure that you get Coinage early. Brown will already be exploiting this area, and you can't count on getting any more gold or any stone in this area. If your advance has been too slow, and you don't even find enough gold to get into the Iron Age, the rest of the scenario will become more difficult.
The two most important upgrades you can get in the Iron Age are the Trireme upgrade and the missile weapon range upgrade. Neither of them requires gold, and either of them allows you to grind up the Red Towers with impunity, although you still have to deal with the Red artillery.
After Red's fortified island has been reduced, you can unleash the full power of your fleet. Brown has no chance at all of resisting your 15 Triremes. Then it's just a matter of collecting the artifact. You know from the Achievements menu that Red has it, i.e. it is right in the middle of the map.