A competitive coevolutionary algorithm is a probabilistic search method that imitates the biological process that two or more species competitively coevolve through evolutionary arms race. The algorithm has been used to efficiently solve adversarial problems that can be formulated as the search for a solution that is correct over a large space of test cases. We develop an efficient competitive coevolutionary algorithm to solve adversarial problems with high complexity. The algorithm developed in this paper employs three methods: tournament competitions, exchanging of entry fee, and localized coevolution. Analyzed in this paper are the effects of the methods on the performance of the proposed algorithm. The extensive experiments show that our algorithm can progress an evolutionary arms race between competitive coevolving species and then outperforms existing approaches to solving the adversarial problems.