Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

Genetic Algorithm for Planning and Scheduling Problem -- StarCraft II Build Order case study

, ,

DOI: http://dx.doi.org/10.15439/2023F6015

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 131–140 ()

Full text

Abstract. The Planning and Scheduling (PS) problem plays a vital role in several domains, such as economics, military, management, finance, and games, where finding the optimal plan and schedule to achieve specific goals is essential. In this article, we present a Genetic Algorithm for the Planning and Scheduling (GAPS) problem in the StarCraft II Build Order Optimization problem (SC2 BO) context -- as it signifies that modern strategy games present a more challenging environment than classical planning problems. We evaluate the performance of GAPS and compare it with state-of-the-art methods. Experimental results provide valuable insight into the effectiveness of GA in the context of the PS Problem under various configurations, notably in the context of Lamarckianism and the Baldwin Effect. Ultimately, this research enhances the understanding of GA application for the PS problem, offering notable insights regarding GA performance and potential for future work.

References

  1. Kovarsky, A., and Buro, M. (2006) "A first look at build-order optimization in real-time strategy games." Proceedings of the GameOn Conference. 2006.
  2. Justesen, Niels and Risi, Sebastian. (2017). Continual online evolutionary planning for in-game build order adaptation in StarCraft. 187-194. 10.1145/3071178.3071210.
  3. Wei, LZ and LW Sun. (2009) “Build Order Optimisation For Realtime Strategy Game”, http://www.nus.edu.sg/nurop/2009/SoC/nuropLimZhanWei.pdf
  4. Blackford, J., and Lamont, G. (2014) "The real-time strategy game multi-objective build order problem." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Vol. 10. No. 1. 2014.
  5. Churchill, D., and Buro M. (2011) "Build order optimization in starcraft." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Vol. 7. No. 1.
  6. Weber, Bryan S. (2018) "Standard economic models in nonstandard settings–starcraft: Brood war." 2018 IEEE Conference on Computational Intelligence and Games (CIG). IEEE,.
  7. Buro, M., and Kovarsky, A. (2007) "Concurrent action execution with shared fluents.", AAAI Conf. 2007: 950-955.
  8. Fox, M., and Derek Long. "PDDL2. 1: An extension to PDDL for expressing temporal planning domains." Journal of artificial intelligence research 20 (2003): 61-124.
  9. Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019). https://doi.org/10.1038/s41586-019-1724-z
  10. Liu, Ruo-Ze and Pang, Zhen-Jia and Meng, Zhou-Yu and Wang, Wenhai and Yu, Yang and Lu, Tong. (2022) "On Efficient Reinforcement Learning for Full-length Game of StarCraft II", Journal of Artificial Intelligence Research 75, 2022, pp.213-260.
  11. El-Nabarawy, Islam and Arroyo, K. and Wunsch, D. (2020). "StarCraft II Build Order Optimization using Deep Reinforcement Learning and Monte-Carlo Tree Search", https://arxiv.org/pdf/2006.10525.pdf.
  12. M. Kuchem, M. Preuss and G. R. (2013) "Multi-objective assessment of pre-optimized build orders exemplified for StarCraft 2" 2013 IEEE Conference on Computational Intelligence in Games (CIG), 2013, pp. 1-8, http://dx.doi.org/10.1109/CIG.2013.6633626.
  13. C.W. Leung, T.N. Wong, K.L. Mak, R.Y.K. Fung, (2010) Integrated process planning and scheduling by an agent-based ant colony optimization, Computers and Industrial Engineering, Vol. 59 (1), pp.166-180.
  14. Cobb, Charles W., and Paul H. Douglas. "A theory of production." (1928).