Botnets are groups of compromised computers that botmasters (botherders) use to launch attacks over the Internet. To avoid detection, botnets use DNS fast flux to change the mapping between IP addresses and domain names periodically. Domain generation algorithms (DGAs) are employed to generate a large number of domain names. Detection techniques have been proposed to identify malicious domain names generated by DGAs. Three metrics, Kullback-Leibler (KL) distance, Edit distance (ED), and Jaccard index (JI), are used to detect botnet domains with up to 100% detection rate and 2.5% false-positive rate. In this paper, we propose two DGAs that use hidden Markov models (HMMs) and probabilistic context-free grammars (PCFGs), respectively. Experiment results show that DGA detection metrics (KL, JI, and ED) and detection systems (BotDigger and Pleiades) have difficulty detecting domain names generated using the proposed approaches. Game theory is used to optimize strategies for both botmasters and security personnel. Results show that, to optimize DGA detection, security personnel should use the ED detection technique with probability 0.78 and JI detection with probability 0.22, and botmasters should choose the HMM-based DGA with probability 0.67 and PCFG-based DGA with probability 0.33.