In drug development, there is often uncertainty about the most promising among a set of different treatments. Multi-arm multi-stage (MAMS) trials provide large gains in efficiency over separate randomised trials of each treatment. They allow a shared control group, dropping of ineffective treatments before the end of the trial and stopping the trial early if sufficient evidence of a treatment being superior to control is found. In this paper, we discuss optimal design of MAMS trials. An optimal design has the required type I error rate and power but minimises the expected sample size at some set of treatment effects. Finding an optimal design requires searching over stopping boundaries and sample size, potentially a large number of parameters. We propose a method that combines quick evaluation of specific designs and an efficient stochastic search to find the optimal design parameters. We compare various potential designs motivated by the design of a phase II MAMS trial. We also consider allocating more patients to the control group, as has been carried out in real MAMS studies. We show that the optimal allocation to the control group, although greater than a 1:1 ratio, is smaller than previously advocated and that the gain in efficiency is generally small.