Played Mzab very recently. Played it three times, first time was able to conquer Touggourt and part of Djerid but was crushed by Tunis, second time I conquered the whole interior and allied Tlemcen but was crushed by Tunis, third time I united the interior and found the opportunity to conquer some of Tlemcen in hopes of becoming large enough to take on Tunis, was declared on mid-war and crushed. Mameluks and Ottomans want nothing to do with me and Iberians see me as a heathen and also want nothing to do with me (Aragon is an exception but almost never independent to help me). Now I am not the best of players, so maybe that's why it happened, but I would have to agree that it is extremely frustrating.