Quantitative genetic trait prediction based on high-density genotyping arrays plays an important role for plant and animal breeding. The prediction can be very helpful to develop breeding strategies. Epistasis, the phenomena where the SNPs interact with each other, has been studied extensively in Genome Wide Association Studies (GWAS) but received relatively less attention for quantitative genetic trait prediction. As the number of possible interactions is in general extremely large, even pairwise interactions is very challenging. To our knowledge, there is no solid solution yet to utilize epistasis to improve genetic trait prediction. In this work, we studied the multi-locus epistasis problem where the interactions with more than two SNPs are considered. We first analyzed the traditional additive epistasis model and we showed that the model has certain limitations, such as it prefers epistasis interactions with more SNPs, and it does not assume a small set of very significant epistasis effects. Then we developed an efficient algorithm SAME to improve the genetic trait prediction with the help of multi-locus epistasis. Our experiments on both simulated and real data showed that SAME is not only efficient but also effective to improve the genetic trait prediction. SAME also achieved very significant improvements on a real plant data set. To our knowledge, this is the first work that is able to achieve such significant improvements with the help of epistasis.