Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
กลยุทธ์สำหรับการเล่นเกมปลดโซ่ตรวนบนกราฟบางชนิด
Year (A.D.)
2025
Document Type
Thesis
First Advisor
Ratinan Boonklurb
Second Advisor
Sirirat Singhun
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Mathematics
DOI
10.58837/CHULA.THE.2025.242
Abstract
Unshackle game is a combinatorial game for two players that starts with prisoners and shackles on a board such that each shackle has two ends, and each end is shackled to one prisoner. Two players alternately play a turn by destroying a shackle on the board until all shackles have been destroyed. A prisoner is free when all shackles that are shackled to him are destroyed, and the player who makes the most prisoners free wins and the other loses. Both players draw if neither of them can win. The prisoners and the shackles on the board can be considered as vertices and edges of a graph. This dissertation constructs strategies and determines outcomes of the Unshackle games on various classes of graphs such as trees and forests, symmetric plane graphs and 2-dimensional grids.
Other Abstract (Other language abstract of ETD)
เกมปลดโซ่ตรวนเป็นเกมเชิงคอมบินาทอริก สำหรับผู้เล่นสองคน ซึ่งเริ่มต้นด้วยเหล่า นักโทษและโซ่ตรวนบนกระดาน โดยโซ่ตรวนแต่ละเส้นมีปลายสองด้าน และปลายแต่ละด้านถูก ล่ามอยู่กับนักโทษหนึ่งคน ผู้เล่นทั้งสองคนผลัดกันเล่น โดยทำลายโซ่ตรวนตาละหนึ่งเส้นบนกระดาน จนกระทั่งโซ่ตรวนทั้งหมดถูกทำลาย นักโทษแต่ละคนจะเป็นอิสระเมื่อโซ่ตรวนทุกเส้น ที่ล่ามเขาอยู่ถูกทำลาย และผู้เล่นที่ทำให้นักโทษเป็นอิสระได้มากที่สุดจะเป็นฝ่ายชนะ ส่วนอีก ฝ่ายจะเป็นฝ่ายแพ้ ผู้เล่นทั้งสองคนจะเสมอกันหากไม่มีผู้เล่นฝ่ายใดสามารถชนะได้ เหล่านักโทษและโซ่ตรวนบนกระดานสามารถพิจารณาได้ว่าเป็นจุดยอดและเส้นเชื่อมของกราฟ วิทยานิพนธ์ฉบับนี้สร้างกลยุทธ์และหาผลลัพธ์ของเกมปลดโซ่ตรวนบนกราฟในคลาสต่าง ๆ เช่น ต้นไม้และป่ากราฟเชิงระนาบแบบสมมาตร และกริดสองมิติ
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Leelathanakit, Thitiphut, "Strategies for playing unshackle games on some graphs" (2025). Chulalongkorn University Theses and Dissertations (Chula ETD). 75250.
https://digital.car.chula.ac.th/chulaetd/75250