risk game ai agent

การใช้เกมความเสี่ยงและผู้เล่นตัวแทนปัญญาประดิษฐ์

1. บทคัดย่อ

1.1. คำอธิบายเกม

ความเสี่ยงเป็นเกมกระดานกลยุทธ์การเจรจาต่อรองความขัดแย้งและการพิชิตสำหรับผู้เล่นสองถึงหกคน หมุนหมุนในหมู่ผู้เล่นที่ควบคุมกองทัพของการเล่นชิ้นส่วนที่พวกเขาพยายามที่จะจับดินแดนจากผู้เล่นคนอื่น ๆ โดยมีผลลัพธ์ที่กำหนดโดยลูกเต๋าม้วน เป้าหมายของเกมคือการครอบครองทุกดินแดนบนกระดานและในการทำเช่นนั้นกำจัดผู้เล่นคนอื่น ๆ แต่ละเทิร์นประกอบด้วยการกระทำสองอย่าง:

1. ร่าง: ผู้เล่นจะเพิ่มหน่วยทหารจำนวนหนึ่งในดินแดนใด ๆ ที่พวกเขาเป็นเจ้าของ
2. การโจมตี: ผู้เล่นสามารถเลือกที่จะโจมตีดินแดนของศัตรูเพื่อนบ้านด้วยจำนวนกองทัพที่พวกเขาต้องการเพื่อพิชิตแผ่นดิน

1.2. เป้าหมายโครงการ

วัตถุประสงค์ของโครงการนี้คือการใช้เกมความเสี่ยงด้วยการเปลี่ยนแปลงบางอย่างที่เกิดขึ้นในกฎและเพื่อออกแบบตัวแทนอัจฉริยะที่มีความสามารถในการเล่นเกมอย่างถูกต้องและมีโอกาสสูงมากที่จะชนะเมื่อเผชิญหน้ากับคู่ต่อสู้อื่น ๆ ผู้เล่นหรือผู้เล่นตัวแทนอื่น ๆ

2. การใช้งานเกม

เกมดังกล่าวใช้งานโดยใช้ภาษาการเขียนโปรแกรม Java การควบคุมการเลี้ยวการดำเนินการของผู้เล่นที่ร้องขอการอัพเดตแผนที่เกมตรวจสอบว่าทุกอย่างเกิดขึ้นตามกฎ ฯลฯ เป็นสิ่งที่ส่วนหนึ่งของรหัสนี้ทำ เกม UI ได้รับการออกแบบผ่านไฟล์. FXML ที่วาดแผนที่และเป็นแพลตฟอร์มที่เชื่อมต่อเครื่องเล่นเข้ากับตรรกะของเกม

3. การใช้งาน AI Player

ส่วนนี้มุ่งเน้นไปที่การดำเนินการและการประเมินฮิวริสติกที่นำไปสู่ ​​AI ที่แข็งแกร่งสำหรับความเสี่ยงของเกม

3.1 อัลกอริทึม

การใช้งานจะขึ้นอยู่กับอัลกอริทึมการตัดแต่งกิ่ง Minimax Alpha-Beta ผู้เล่นสร้างแผนผังการทำนายตามอัลกอริทึม DFS

3.1.1 ต้นไม้ทำนาย

เมื่อใดก็ตามที่เป็นเทิร์นของเอเจนต์ที่จะเล่นต้นไม้จะถูกสร้างขึ้น โหนดต้นไม้เป็นสถานะของเกม (แผนที่ของเกมในสถานะนั้น) และแต่ละขอบคือการโจมตีที่เป็นไปได้ที่เกิดจากสถานะปัจจุบันไปยังสถานะผลลัพธ์ของการโจมตีของแผนที่ การกระทำการโจมตีประกอบด้วยพิกัดของดินแดนเริ่มต้นและ Target Territories และจำนวนหน่วยที่เลือกให้อยู่ในกองทัพโจมตี โหนดรูทคือสถานะปัจจุบันของแผนที่ที่ผู้เล่นต้องเลือกการเคลื่อนไหวจาก แม้ว่าต้นไม้จะไม่สามารถทำนายได้จนกว่าจะถึงสถานะสิ้นสุดของเกมเนื่องจากการเคลื่อนไหวที่เป็นไปได้จำนวนมากผู้เล่นสามารถมีได้ในแต่ละรัฐซึ่งการ จำกัด เวลาหน่วยความจำและเวลาไม่อนุญาต ดังนั้นผู้เล่นสามารถสร้างต้นไม้ได้ในระดับความลึกที่เรากำหนดไว้ในรหัสเท่านั้น นอกจากนี้ยังมีความเรียบง่ายบางอย่างที่นำไปใช้กับบางส่วนของกลยุทธ์การเล่นเกมของตัวแทนที่จะอธิบายทั้งหมดในส่วนต่อไปนี้ เพื่อที่จะทำให้การวิเคราะห์ฮิวริสติกการตัดสินใจที่ดีที่สุดถูกกำหนดไว้สำหรับโหนดที่ลึกที่สุด (ใบต้นไม้) ที่ประเมินว่ารัฐนั้นสามารถเป็นประโยชน์ต่อผู้เล่นได้มากแค่ไหน กล่าวว่าฮิวริสติกจะอธิบายเพิ่มเติมในรายงาน เมื่อค่าของใบถูกกำหนดต้นไม้จะถูกส่งต่อไปยังการตัดแต่งกิ่ง minimax alpha-beta และอัลกอริทึมที่รู้จักกันดีนี้จะพบชุดการกระทำที่ดีที่สุดที่ผู้เล่นสามารถมีได้

3.2. ฮิวริสติกและการทำให้เข้าใจง่าย

3.2.1. ขั้นตอนการร่าง

การจัดหาหน่วยไปยังดินแดนอาจเป็นงานที่ยุ่งยาก ในแง่ที่ว่าเราต้องการปรับปรุงพลังการโจมตีของเรา แต่ยังตรวจสอบให้แน่ใจว่ามีอำนาจการป้องกันที่เพียงพอในดินแดนที่ตกอยู่ในอันตรายจากการถูกโจมตี การปรับใช้หน่วยในประเทศที่อยู่ติดกับดินแดนของศัตรูอาจเป็นวิธีที่ชาญฉลาดในการรักษาสมดุลระหว่างสองเป้าหมายนี้

การทำให้เรียบง่ายแบบร่าง:
การทำนายและรวมถึงสถานการณ์ร่างที่เป็นไปได้ทั้งหมดในต้นไม้ทำนายจะนำไปสู่ต้นไม้ที่ซับซ้อนซึ่งจะต้องเผชิญกับปัญหาที่กล่าวถึงก่อนหน้านี้ ดังนั้นหนึ่งในความเรียบง่ายที่เกิดขึ้นคือเราใช้ฮิวริสติกการร่างซึ่งพิสูจน์แล้วว่ามีผลลัพธ์ที่ดีที่สุดเท่าที่จะเป็นไปได้และคาดการณ์ว่าฝ่ายตรงข้ามได้ทำวิธีนี้ในการร่างเช่นกัน กล่าวอีกนัยหนึ่งเราลบผลการร่างเป็นความเป็นไปได้ก่อให้เกิดแผนผังการทำนายและเปลี่ยนเป็นสถานการณ์ร่างที่ชัดเจน

เพื่อที่จะทำเช่นนั้นเราทำตามขั้นตอนต่อไปนี้:
ร่างฮิวริสติก:
ขั้นตอนที่ 1:
การรวมกันของทุกหน่วยในประเทศศัตรู y ที่อยู่ติดกับประเทศ X จะให้มาตรการที่เราเรียกว่าภัยคุกคามความปลอดภัยชายแดน (BST) ใน x

ขั้นตอนที่ 2:
การหาร BST นี้โดยหน่วยที่ตั้งอยู่ใน X ให้อัตราส่วนความปลอดภัยชายแดน (BSR) ซึ่งสามารถเปรียบเทียบได้ในทุกประเทศชายแดน

ประเทศที่มี BSR สูงมีแนวโน้มที่จะถูกเอาชนะโดยผู้เล่นศัตรูเนื่องจากจำนวนหน่วยศัตรูในประเทศศัตรูที่อยู่ติดกันค่อนข้างสูงกว่าจำนวนหน่วยในประเทศ การเลือกประเทศที่มี BSR สูงเพื่อจัดหาเพื่อเพิ่มความแข็งแกร่งในการป้องกันของพวกเขาโดยการลด BSR การจัดหาหน่วยไปยังประเทศที่มี BSR ต่ำกว่าซึ่งหมายความว่าพวกเขามีท่าทางการป้องกันที่ดีขึ้นแล้วจะเพิ่มความแข็งแกร่งที่น่ารังเกียจของพวกเขาเพิ่มโอกาสในการโจมตีที่ประสบความสำเร็จจากประเทศเหล่านี้

ขั้นตอนที่ 3:
การทำให้ BSR เป็นปกติโดยการหารด้วยผลรวมของ BSR ทั้งหมดของประเทศผู้เล่นจะเป็นเจ้าของจะให้การวัดโดยตรงซึ่งใครบางคนสามารถจัดหน่วยได้ อัตราส่วนความปลอดภัยชายแดนปกติ (NBSR) คำนวณโดย:

มันให้อัตราส่วนโดยตรงของวิธีการกระจายหน่วยระหว่างประเทศ ณ จุดนี้เราจะเห็นว่าจะมีปัญหากับอัตราส่วนนี้เนื่องจากข้อมูลบางอย่างไม่เกี่ยวข้องและเราไม่ต้องการเพิ่มหน่วยในดินแดนทั้งหมดของเราดังนั้นเราจึงตั้งค่าเกณฑ์ระหว่างขั้นตอนที่สองถึงสามโดยการเรียงลำดับข้อมูล BSRX ใน คำสั่งจากมากไปน้อย (เรามุ่งเน้นไปที่การทำให้กำลังป้องกันแข็งแกร่งขึ้น) หารข้อมูลจากกลางและตั้งค่าในครึ่งล่างเป็นศูนย์

ขั้นตอนที่ 4:

ขั้นตอนที่ 4 จะดำเนินการต่อไปจนกว่าจะไม่มีหน่วยที่เหลืออีกแล้วที่จะเพิ่ม

3.2.2. การโจมตีขั้นตอน

มีความเรียบง่ายบางอย่างที่ใช้ในขั้นตอนการโจมตีเพื่อให้ต้นไม้มีความซับซ้อนน้อยลงเพื่อให้เราสามารถทำนายได้ในระดับที่ลึกกว่า สิ่งนี้สามารถทำได้โดยการตรวจสอบสถานการณ์การโจมตีที่มีโอกาสสูงกว่าที่จะชนะการต่อสู้และรวมไว้ในต้นไม้เท่านั้น

1. AttacksaryonlyInitiated FromterRitoriestHathAthAtleastOneunit มากกว่ากองทัพที่ปกป้อง
2. numberofunitsintheattackingingarmycanbeonlyequaltotheaverage ของหน่วยผู้โจมตีและผู้พิทักษ์ดินแดนที่กลมขึ้นไป
3. Intheoriginalgametheresultofattackisbased และ ... แต่เราคิดว่าถ้าผู้โจมตีมีส่วนร่วมในการต่อสู้กับหน่วยและผู้พิทักษ์ด้วยหน่วย D และมากกว่า D แน่นอนผู้โจมตีจะชนะเกมและจะมีหน่วยโฆษณาเหลืออยู่ ซึ่งหมายความว่าเรากำลังลบโหนดที่เป็นไปได้จำนวนมากไปยังโหนดที่แน่นอนหนึ่งโหนด
4. ผู้เล่นในแต่ละเทิร์นสามารถมีการโจมตีระหว่างศูนย์ถึงสูงสุดสามครั้งและถือว่าฝ่ายตรงข้ามทำเช่นเดียวกัน

3.2.3. ฮิวริสติกต้นไม้ทำนาย

เพื่อประเมินว่าใบต้นไม้มีประโยชน์อย่างไรสำหรับผู้เล่นที่เฉพาะเจาะจงนั้น เราได้กำหนดคุณสมบัติฮิวริสติกสี่แบบซึ่งพบน้ำหนักที่ดีที่สุดเท่าที่จะเป็นไปได้ในระหว่างการเรียนรู้เกี่ยวกับฮิวริสติกซึ่งจะอธิบายในภายหลัง ฟีเจอร์ทั้งหมดจะส่งคืนผลลัพธ์ระหว่างศูนย์ถึงหนึ่งเพราะเมื่อคุณสมบัติมีมูลค่าในอัตราส่วนใกล้ชิดกันการเรียนรู้และการกำหนดน้ำหนักจะแม่นยำยิ่งขึ้น

คุณสมบัติคือ:

1. theratiOfthenumberofalltheterritoriesaplayerownstoall ดินแดนที่แผนที่มี
2. theratiOfthenumberofalltheunitsaplayerownstoallunitsthatare ในแผนที่
3. foreachterritoryxthelayerowns, foreachenemyterritoryyadjacent กับมันเราคำนวณ:
   
   หลังจากนั้นเราคำนวณค่าเฉลี่ยของ Z ทั้งหมดและผลลัพธ์คือคุณสมบัติที่สามที่เราใช้ มันแสดงให้เห็นถึงพลังการป้องกันของเราและยิ่งใกล้เข้ามาถึงหนึ่งในนั้นแสดงให้เห็นว่าเรามีความแข็งแกร่งในการป้องกันที่สูงขึ้น
4. foreachterritoryxthedeplayerowns, Ifyisnumberofneighborenemy Territories และ Z คือจำนวนดินแดนเพื่อนบ้านที่ผู้เล่นเป็นเจ้าของ P จะถูกคำนวณ:
   
   หลังจากนั้นเราคำนวณค่าเฉลี่ยของ P's ทั้งหมด = AVGP (1 - AVGP) บ่งชี้ว่าดินแดนของเราหนาแน่นและอยู่ใกล้กันมากแค่ไหนซึ่งยิ่งดีกว่าเพราะกลยุทธ์การชนะสำหรับเกมนี้เช่นเมื่อมีทวีปคือการมุ่งเน้นไปที่หนึ่งทวีปและพิชิตทั้งหมดแล้วย้ายไปยังทวีปอื่น ๆ .

3.3. การเรียนรู้และพันธุกรรม

การให้น้ำหนักกับฮิวริสติกในส่วนก่อนหน้านี้ช่วยประเมินว่าแต่ละคนมีความสำคัญและมีอิทธิพลต่อพวกเขาในการชนะเกมอย่างไร กระบวนการค้นหาน้ำหนักเหล่านี้ผ่านทางพันธุกรรมและเรียนรู้ ยีนแต่ละตัวเป็นชุดของสี่น้ำหนักสำหรับคุณสมบัติทั้งสี่นั้น เราเริ่มต้นด้วยการสร้างน้ำหนักสุ่ม 100 ชุดในช่วง [0,10] หลังจากนั้น 10 การแข่งขันจะเกิดขึ้น สำหรับแต่ละทัวร์นาเมนต์ 10 ยีนจากประชากรหลักจะถูกเลือกแบบสุ่ม ยีนที่เป็นไปได้ทุกคู่จะเล่นกันและผลลัพธ์ของแต่ละเกมในแต่ละทัวร์นาเมนต์จะได้รับการบันทึกไว้ ฟังก์ชั่นการออกกำลังกายหมายถึง (จำนวนการชนะ / จำนวนเกม) สำหรับแต่ละยีน ยีนสามอันดับแรกในแต่ละทัวร์นาเมนต์ (ขึ้นอยู่กับฟังก์ชั่นการออกกำลังกาย) จะถูกเลือกดังนั้นตอนนี้เรามียีนที่เลือกไว้ 30 ยีน ในบรรดาสิ่งเหล่านี้เราเลือกคู่สุ่ม 12 คู่และแต่ละคู่ทำการครอสโอเวอร์ซึ่งกำลังสร้างยีนใหม่โดยการคำนวณน้ำหนักเฉลี่ยของคู่ของยีน ดังนั้นตอนนี้เรามียีนใหม่ 12 ยีนจากครอสโอเวอร์นี้ ในทางกลับกันยีน 3 จะถูกสุ่มเลือกภายใน 30 ยีนที่เรามีและกลายพันธุ์โดยการเปลี่ยนน้ำหนักสุ่มหนึ่งครั้งของแต่ละน้ำหนักสุ่มในช่วง [0,10] หลังจากทั้งหมดนี้เรามียีนใหม่ 15 ยีนที่อยู่ในประชากรหลักแทนที่ 15 ที่ดีน้อยที่สุดที่เรามีอยู่แล้ว ณ จุดนี้ยีนรุ่นที่สองจะถูกสร้างขึ้น กระบวนการนี้จะดำเนินการซ้ำต่อไปจนกว่าจะมีการสร้างยีนรุ่นที่ 4 ยีนชั้นนำในประชากรนั้นจะถูกเลือกให้เป็นน้ำหนักที่ดีที่สุดของเราสำหรับคุณสมบัติของฮิวริสติกของเราที่ตัวแทนจะใช้ในการเล่น