Monte-carlo planning for pathfinding in real-time strategy games

Munir Naveed; Diane E Kitchin; Andrew Crampton

Monte-carlo planning for pathfinding in real-time strategy games

Munir Naveed, Diane E Kitchin, Andrew Crampton

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

In this work, we explore two Monte-Carlo planning approaches: Upper Confidence Tree (UCT) and Rapidly exploring Random Tree (RRT). These Monte-Carlo planning approaches are applied in a real-time strategy game for solving the path finding problem. The planners are evaluated using a grid-based representation of our game world. The results show that the UCT planner solves the path planning problem with significantly less search effort than the RRT planner. The game playing performance of each planner is evaluated using the mean, maximum and minimum scores in the test games. With respect to the mean scores, the RRT planner shows better performance than the UCT planner. The RRT planner achieves more maximum
scores than the UCT planner in the test games.

Original language	English
Title of host publication	Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling
Subtitle of host publication	joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010
Editors	Simone Fratini, Alfonso Gerevini, Derek Long, Alessandro Saetti
Publisher	Consiglio Nazionale delle Ricerche
Pages	125-139
Number of pages	15
Publication status	Published - 1 Dec 2010
Event	28th Workshop of the UK Special InterestGroup on Planning and Scheduling : joint meeting with the 4th Italian Workshop on Planning and Scheduling - Brescia, Italy Duration: 1 Dec 2010 → 2 Dec 2010 Conference number: 28

Publication series

Name	Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling
Publisher	Consiglio Nazionale delle Ricerche
ISSN (Print)	1368-5708

Workshop

Workshop	28th Workshop of the UK Special InterestGroup on Planning and Scheduling
Abbreviated title	PlanSIG2010
Country/Territory	Italy
City	Brescia
Period	1/12/10 → 2/12/10

Cite this

Naveed, M., Kitchin, D. E., & Crampton, A. (2010). Monte-carlo planning for pathfinding in real-time strategy games. In S. Fratini, A. Gerevini, D. Long, & A. Saetti (Eds.), Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling: joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010 (pp. 125-139). (Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling). Consiglio Nazionale delle Ricerche.

Naveed, Munir ; Kitchin, Diane E ; Crampton, Andrew. / Monte-carlo planning for pathfinding in real-time strategy games. Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling: joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010. editor / Simone Fratini ; Alfonso Gerevini ; Derek Long ; Alessandro Saetti. Consiglio Nazionale delle Ricerche, 2010. pp. 125-139 (Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling).

@inbook{5321c1e23858459da6e14e38fe466d59,

title = "Monte-carlo planning for pathfinding in real-time strategy games",

abstract = "In this work, we explore two Monte-Carlo planning approaches: Upper Confidence Tree (UCT) and Rapidly exploring Random Tree (RRT). These Monte-Carlo planning approaches are applied in a real-time strategy game for solving the path finding problem. The planners are evaluated using a grid-based representation of our game world. The results show that the UCT planner solves the path planning problem with significantly less search effort than the RRT planner. The game playing performance of each planner is evaluated using the mean, maximum and minimum scores in the test games. With respect to the mean scores, the RRT planner shows better performance than the UCT planner. The RRT planner achieves more maximumscores than the UCT planner in the test games.",

keywords = "Upper Confidence Tree (UCT), Rapidly exploring Random Tree (RRT), Monte-Carlo planning approaches",

author = "Munir Naveed and Kitchin, {Diane E} and Andrew Crampton",

year = "2010",

month = dec,

day = "1",

language = "English",

series = "Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling",

publisher = "Consiglio Nazionale delle Ricerche",

pages = "125--139",

editor = "Simone Fratini and Alfonso Gerevini and Derek Long and Alessandro Saetti",

booktitle = "Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling",

address = "Italy",

note = "28th Workshop of the UK Special InterestGroup on Planning and Scheduling : joint meeting with the 4th Italian Workshop on Planning and Scheduling , PlanSIG2010 ; Conference date: 01-12-2010 Through 02-12-2010",

}

Naveed, M, Kitchin, DE & Crampton, A 2010, Monte-carlo planning for pathfinding in real-time strategy games. in S Fratini, A Gerevini, D Long & A Saetti (eds), Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling: joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010. Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling, Consiglio Nazionale delle Ricerche, pp. 125-139, 28th Workshop of the UK Special InterestGroup on Planning and Scheduling , Brescia, Italy, 1/12/10.

Monte-carlo planning for pathfinding in real-time strategy games. / Naveed, Munir; Kitchin, Diane E; Crampton, Andrew.

Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling: joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010. ed. / Simone Fratini; Alfonso Gerevini; Derek Long; Alessandro Saetti. Consiglio Nazionale delle Ricerche, 2010. p. 125-139 (Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Monte-carlo planning for pathfinding in real-time strategy games

AU - Naveed, Munir

AU - Kitchin, Diane E

AU - Crampton, Andrew

N1 - Conference code: 28

PY - 2010/12/1

Y1 - 2010/12/1

N2 - In this work, we explore two Monte-Carlo planning approaches: Upper Confidence Tree (UCT) and Rapidly exploring Random Tree (RRT). These Monte-Carlo planning approaches are applied in a real-time strategy game for solving the path finding problem. The planners are evaluated using a grid-based representation of our game world. The results show that the UCT planner solves the path planning problem with significantly less search effort than the RRT planner. The game playing performance of each planner is evaluated using the mean, maximum and minimum scores in the test games. With respect to the mean scores, the RRT planner shows better performance than the UCT planner. The RRT planner achieves more maximumscores than the UCT planner in the test games.

AB - In this work, we explore two Monte-Carlo planning approaches: Upper Confidence Tree (UCT) and Rapidly exploring Random Tree (RRT). These Monte-Carlo planning approaches are applied in a real-time strategy game for solving the path finding problem. The planners are evaluated using a grid-based representation of our game world. The results show that the UCT planner solves the path planning problem with significantly less search effort than the RRT planner. The game playing performance of each planner is evaluated using the mean, maximum and minimum scores in the test games. With respect to the mean scores, the RRT planner shows better performance than the UCT planner. The RRT planner achieves more maximumscores than the UCT planner in the test games.

KW - Upper Confidence Tree (UCT)

KW - Rapidly exploring Random Tree (RRT)

KW - Monte-Carlo planning approaches

UR - https://core.ac.uk/download/pdf/53061.pdf

M3 - Chapter

T3 - Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling

SP - 125

EP - 139

BT - Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling

A2 - Fratini, Simone

A2 - Gerevini, Alfonso

A2 - Long, Derek

A2 - Saetti, Alessandro

PB - Consiglio Nazionale delle Ricerche

T2 - 28th Workshop of the UK Special InterestGroup on Planning and Scheduling

Y2 - 1 December 2010 through 2 December 2010

ER -

Naveed M, Kitchin DE, Crampton A. Monte-carlo planning for pathfinding in real-time strategy games. In Fratini S, Gerevini A, Long D, Saetti A, editors, Proceedings of the 28th Workshop of the UK Special Interest Group on Planning and Scheduling: joint meeting with the 4th Italian Workshop on Planning and Scheduling: PlanSIG2010. Consiglio Nazionale delle Ricerche. 2010. p. 125-139. (Proceedings of the Workshop of the UK Special Interest Group on Planning and Scheduling).

Monte-carlo planning for pathfinding in real-time strategy games

Abstract

Publication series

Workshop

Other files and links

Fingerprint

Cite this