กลยุทธ์ที่บริสุทธิ์และผสมผสาน เกมกลยุทธ์ล้วนๆ

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

หนึ่งเดียว - กลยุทธ์เดียว ดังนั้น เมื่อนับว่าเป็นปฏิปักษ์ที่มีเหตุผล ทางเลือกนี้ควรถูกกำหนดโดยหลักการมินิแมกซ์ การปฏิบัติตามกลยุทธ์สูงสุดของเรา สำหรับพฤติกรรมใดๆ ของคู่ต่อสู้ เรารับประกันว่าตนเองจะได้รับชัยชนะเท่ากับราคาที่ต่ำกว่าของเกม a คำถามที่เป็นธรรมชาติเกิดขึ้น: เป็นไปได้ไหมที่จะรับประกันว่าตัวเองจะได้รับกำไรโดยเฉลี่ย มากกว่า a หากคุณไม่ใช้กลยุทธ์ "บริสุทธิ์" เพียงอย่างเดียว แต่เป็นทางเลือก สุ่มหลายกลยุทธ์?

กลยุทธ์ที่รวมกันดังกล่าวประกอบด้วยการใช้กลยุทธ์บริสุทธิ์หลายอย่างสลับกันตามกฎสุ่มที่มีอัตราส่วนความถี่ที่แน่นอนเรียกว่ากลยุทธ์แบบผสมในทฤษฎีเกม

เห็นได้ชัดว่า แต่ละกลยุทธ์ล้วนเป็นกรณีพิเศษของกลยุทธ์แบบผสม ซึ่งกลยุทธ์ทั้งหมด ยกเว้นหนึ่ง ใช้กับความถี่เป็นศูนย์ และกลยุทธ์นี้ - ด้วยความถี่ 1

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

ข้อความข้างต้นประกอบด้วยเนื้อหาที่เรียกว่าทฤษฎีบทหลักของทฤษฎีเกม ทฤษฎีบทนี้ได้รับการพิสูจน์ครั้งแรกโดยฟอน นอยมันน์ในปี ค.ศ. 1928 การพิสูจน์ทฤษฎีบทนี้ค่อนข้างซับซ้อน ดังนั้นเราจึงนำเสนอเฉพาะสูตรของมันเท่านั้น

ท้ายเกมแต่ละเกมมีวิธีแก้ปัญหาอย่างน้อยหนึ่งวิธี (อาจอยู่ในพื้นที่ของกลยุทธ์แบบผสม)

กำไรที่เกิดจากการตัดสินใจเรียกว่าต้นทุนของเกม ทฤษฎีบทหลักบอกเป็นนัยว่าทุกเกมจำกัดมีราคา เห็นได้ชัดว่าราคาของเกม v อยู่ระหว่างราคาที่ต่ำกว่าของเกม a และราคาสูงกว่าของเกมเสมอ:

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

กลยุทธ์ ไม่ว่าในกรณีใด เราจะไม่ทำให้ความสามารถของเราแย่ลง ดังนั้น

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

ดังนั้นความไม่เท่าเทียมกันที่พิสูจน์แล้ว (3.1) ตามมา

ให้เราแนะนำสัญลักษณ์พิเศษสำหรับกลยุทธ์แบบผสม ตัวอย่างเช่น หากกลยุทธ์แบบผสมของเราประกอบด้วยการใช้กลยุทธ์ AL ด้วยความถี่ เราจะแสดงถึงกลยุทธ์นี้

ในทำนองเดียวกัน กลยุทธ์ผสมของศัตรูจะแสดงโดย:

ความถี่ที่กลยุทธ์ผสมอยู่ที่ไหน

สมมติว่าเราพบวิธีแก้ปัญหาของเกมซึ่งประกอบด้วยสองกลยุทธ์แบบผสมที่เหมาะสมที่สุด S, S. ในกรณีทั่วไป ไม่ใช่กลยุทธ์ที่บริสุทธิ์ทั้งหมดที่มีให้สำหรับผู้เล่นรายใดรายหนึ่งรวมอยู่ในกลยุทธ์แบบผสมที่เหมาะสมที่สุดของเขา แต่มีเพียงบางส่วนเท่านั้น เราจะเรียกกลยุทธ์ที่รวมอยู่ในกลยุทธ์แบบผสมที่ดีที่สุดของผู้เล่นกลยุทธ์ที่ "มีประโยชน์" ของเขา

ปรากฎว่าทางแก้ของเกมมีอีกทางหนึ่ง คุณสมบัติที่ยอดเยี่ยม: หากผู้เล่นคนใดคนหนึ่งปฏิบัติตามกลยุทธ์การผสมที่ดีที่สุดของเขา 5 (5) จากนั้นผลตอบแทนจะยังคงไม่เปลี่ยนแปลงและเท่ากับราคาของเกม v ไม่ว่าผู้เล่นคนอื่นจะทำอะไรก็ตาม ถ้าเขาเป็นเช่นนั้น อย่าไปเกินกลยุทธ์ที่ "มีประโยชน์" ของพวกเขา ตัวอย่างเช่น เขาสามารถใช้กลยุทธ์ที่ "มีประโยชน์" ในรูปแบบที่บริสุทธิ์ และยังสามารถผสมในสัดส่วนใดก็ได้

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

กลยุทธ์ที่ "มีประโยชน์" ตามลำดับ ประกอบด้วยกลยุทธ์ที่ "มีประโยชน์" สามแบบผสมกัน

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

แม้ว่าฉันจะจบการศึกษาจากคณะฟิสิกส์และเทคโนโลยี แต่มหาวิทยาลัยก็ไม่ได้สอนทฤษฎีเกม แต่เนื่องจากฉันอยู่ใน ปีนักศึกษาฉันเล่นบ่อยมาก อันดับแรกในความชอบ และจากนั้นในบริดจ์ ทฤษฎีเกมทำให้ฉันสนใจ และฉันเชี่ยวชาญหนังสือเรียนเล่มเล็กๆ และเมื่อเร็ว ๆ นี้ผู้อ่านเว็บไซต์ Mikhail ได้แก้ปัญหาเกี่ยวกับทฤษฎีเกม เมื่อตระหนักว่างานนั้นไม่ได้มอบให้ฉันในทันที ฉันจึงตัดสินใจทบทวนความรู้เกี่ยวกับทฤษฎีเกมในความทรงจำ ฉันนำเสนอหนังสือเล่มเล็ก ๆ แก่คุณ - การอธิบายองค์ประกอบของทฤษฎีเกมและวิธีการแก้เกมเมทริกซ์ที่เป็นที่นิยม แทบไม่มีหลักฐานและแสดงให้เห็นประเด็นหลักของทฤษฎีพร้อมตัวอย่าง หนังสือเล่มนี้เขียนขึ้นโดยนักคณิตศาสตร์และผู้มีชื่อเสียงของวิทยาศาสตร์ Elena Sergeevna Ventzel วิศวกรโซเวียตหลายชั่วอายุคนศึกษาจากหนังสือเรียน "ทฤษฎีความน่าจะเป็น" ของเธอ Elena Sergeevna ยังเขียนอีกหลายอย่าง งานวรรณกรรมภายใต้นามแฝงของ I. Grekov

เอเลน่า เวนท์เซล. องค์ประกอบของทฤษฎีเกม - M.: Fizmatgiz, 1961 .-- 68 น.

ดาวน์โหลด เรื่องย่อในรูปแบบหรือ

§ 1. เรื่องของทฤษฎีเกม แนวคิดพื้นฐาน

เมื่อแก้ไขงานเชิงปฏิบัติจำนวนหนึ่ง (ในด้านเศรษฐศาสตร์ การทหาร ฯลฯ) จำเป็นต้องวิเคราะห์สถานการณ์ที่มีฝ่ายสงครามสองฝ่าย (หรือมากกว่า) ไล่ตามเป้าหมายที่ตรงกันข้าม และผลลัพธ์ของแต่ละเหตุการณ์ของ ฝ่ายขึ้นอยู่กับแนวทางปฏิบัติที่ศัตรูจะเลือก เราจะเรียกสถานการณ์ดังกล่าวว่า "สถานการณ์ความขัดแย้ง"

มีตัวอย่างสถานการณ์ความขัดแย้งมากมายจากแนวปฏิบัติที่หลากหลาย สถานการณ์ใด ๆ ที่เกิดขึ้นในระหว่างการสู้รบถือเป็นสถานการณ์ความขัดแย้ง: ฝ่ายต่อสู้แต่ละฝ่ายใช้มาตรการทั้งหมดที่มีอยู่เพื่อป้องกันไม่ให้ศัตรูประสบความสำเร็จ สถานการณ์ความขัดแย้งยังรวมถึงสถานการณ์ที่เกิดขึ้นเมื่อเลือกระบบอาวุธ วิธีการต่อสู้ และโดยทั่วไปเมื่อวางแผนปฏิบัติการทางทหาร: การตัดสินใจแต่ละครั้งในพื้นที่นี้ควรคำนึงถึงการกระทำของศัตรูที่เป็นประโยชน์น้อยที่สุด เรา. สถานการณ์ด้านเศรษฐศาสตร์จำนวนหนึ่ง (โดยเฉพาะอย่างยิ่งเมื่อมีการแข่งขันอย่างเสรี) อยู่ในสถานการณ์ความขัดแย้ง บริษัทการค้าทำหน้าที่เป็นฝ่ายต่อสู้ ผู้ประกอบการอุตสาหกรรมเป็นต้น

ความจำเป็นในการวิเคราะห์สถานการณ์ดังกล่าวก่อให้เกิดเครื่องมือทางคณิตศาสตร์พิเศษ ทฤษฎีเกมโดยพื้นฐานแล้วไม่มีอะไรมากไปกว่าทฤษฎีทางคณิตศาสตร์ของสถานการณ์ความขัดแย้ง เป้าหมายของทฤษฎีนี้คือการพัฒนาข้อเสนอแนะสำหรับแนวทางปฏิบัติที่มีเหตุผลสำหรับคู่ต่อสู้แต่ละคนในสถานการณ์ความขัดแย้ง สถานการณ์ความขัดแย้งแต่ละอย่างที่เกิดขึ้นโดยตรงจากการปฏิบัตินั้นซับซ้อนมาก และการวิเคราะห์นั้นถูกขัดขวางโดยปัจจัยที่เกี่ยวข้องมากมาย เพื่อทำให้การวิเคราะห์ทางคณิตศาสตร์ของสถานการณ์เป็นไปได้ จำเป็นต้องสรุปจากปัจจัยรองและปัจจัยที่เกิดขึ้นโดยบังเอิญ และสร้างแบบจำลองสถานการณ์ที่เรียบง่ายและเป็นทางการของสถานการณ์ เราจะเรียกโมเดลนี้ว่า "เกม"

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

เกมที่มีการจัดระเบียบและควบคุมอย่างเป็นทางการดังกล่าวเป็นตัวแทนของเกมมากที่สุด วัสดุที่เหมาะสมเพื่อแสดงและฝึกฝนแนวคิดพื้นฐานของทฤษฎีเกม คำศัพท์ที่ยืมมาจากการฝึกฝนของเกมดังกล่าวยังใช้ในการวิเคราะห์สถานการณ์ความขัดแย้งอื่น ๆ อีกด้วย: ฝ่ายที่เข้าร่วมในพวกเขาจะถูกเรียกว่า "ผู้เล่น" ตามอัตภาพและผลของการปะทะกันคือ "ชนะ" ของฝ่ายใดฝ่ายหนึ่ง .

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

เราเริ่มการนำเสนอทฤษฎีเกมเบื้องต้นด้วยการกำหนดแนวคิดพื้นฐานบางอย่าง เราจะพิจารณาเกมคู่ที่ผู้เล่นสองคน A และ B ที่มีความสนใจตรงกันข้ามเข้าร่วม โดย "เกม" เราหมายถึงเหตุการณ์ที่ประกอบด้วยชุดของการกระทำของฝ่าย A และ B เพื่อให้เกมได้รับการวิเคราะห์ทางคณิตศาสตร์ กฎของเกมจะต้องได้รับการกำหนดอย่างแม่นยำ โดย "กฎของเกม" เราหมายถึงระบบของเงื่อนไขที่ควบคุมตัวเลือกที่เป็นไปได้สำหรับการกระทำของทั้งสองฝ่าย จำนวนข้อมูลที่แต่ละฝ่ายมีเกี่ยวกับพฤติกรรมของอีกฝ่าย ลำดับของ "การเคลื่อนไหว" สลับกัน (การตัดสินใจเป็นรายบุคคล ในระหว่างเกม) เช่นเดียวกับผลหรือผลของเกมที่ชุดของการเคลื่อนไหวที่กำหนด ผลลัพธ์นี้ (กำไรหรือขาดทุน) ไม่ได้มีนิพจน์เชิงปริมาณเสมอไป แต่โดยปกติ ด้วยการตั้งค่ามาตราส่วนการวัด มันสามารถแสดงได้ด้วยจำนวนที่แน่นอน ตัวอย่างเช่น ในเกมหมากรุก กำไรสามารถกำหนดค่าตามอัตภาพ +1, แพ้ –1, เสมอ 0

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

เนื่องจากในเกมผลรวมศูนย์ ผลตอบแทนของผู้เล่นคนใดคนหนึ่งเท่ากับผลตอบแทนของอีกฝ่ายด้วย เครื่องหมายตรงข้ามเห็นได้ชัดว่าเมื่อวิเคราะห์เกมดังกล่าว เราสามารถพิจารณาผลตอบแทนของผู้เล่นเพียงคนเดียว ปล่อยให้เป็นเช่นผู้เล่น A ในสิ่งต่อไปนี้เพื่อความสะดวกเราจะเรียกฝ่าย A "เรา" และฝ่าย B - "ศัตรู" ตามอัตภาพ

ในกรณีนี้ ฝ่าย A ("เรา") จะถือเป็น "ชัยชนะ" และฝ่าย B ("ฝ่ายตรงข้าม") จะถือเป็น "ฝ่ายแพ้" เงื่อนไขที่เป็นทางการนี้ไม่ได้หมายความถึงความได้เปรียบที่แท้จริงสำหรับผู้เล่นคนแรก มันง่ายที่จะเห็นว่ามันถูกแทนที่ด้วยอันตรงข้ามถ้าเครื่องหมายที่ชนะถูกกลับรายการ

เราจะจินตนาการถึงการพัฒนาของเกมในเวลาที่ประกอบด้วยขั้นตอนต่อเนื่องกันหรือ "การเคลื่อนไหว" ทฤษฎีการเคลื่อนไหวในเกมคือการเลือกหนึ่งในตัวเลือกที่มีให้โดยกฎของเกม การเคลื่อนไหวแบ่งออกเป็นส่วนบุคคลและแบบสุ่ม การเคลื่อนไหวส่วนบุคคลเป็นทางเลือกที่มีสติโดยหนึ่งในผู้เล่นของการเคลื่อนไหวที่เป็นไปได้ในสถานการณ์ที่กำหนดและการดำเนินการ ตัวอย่างของการเคลื่อนไหวส่วนบุคคลคือการเคลื่อนไหวใดๆ ในเกมหมากรุก ในการดำเนินการในครั้งต่อไป ผู้เล่นจะต้องเลือกหนึ่งในตัวเลือกที่เป็นไปได้สำหรับการจัดเรียงชิ้นส่วนบนกระดาน ชุดตัวเลือกที่เป็นไปได้สำหรับการเคลื่อนไหวส่วนบุคคลแต่ละครั้งถูกควบคุมโดยกฎของเกมและขึ้นอยู่กับจำนวนรวมของการเคลื่อนไหวก่อนหน้าของทั้งสองฝ่าย

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

บางเกมสามารถประกอบด้วยการเคลื่อนไหวแบบสุ่ม (ที่เรียกว่าการพนันล้วนๆ) หรือการเคลื่อนไหวส่วนบุคคลเท่านั้น (หมากรุกหมากฮอส) ส่วนใหญ่ การ์ดเกมเป็นของเกมส์ แบบผสมกล่าวคือ มีทั้งการเคลื่อนไหวแบบสุ่มและส่วนบุคคล

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

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

หนึ่งในแนวคิดพื้นฐานของทฤษฎีเกมคือแนวคิดของ "กลยุทธ์" กลยุทธ์ของผู้เล่นคือชุดของกฎที่กำหนดตัวเลือกเฉพาะสำหรับการเคลื่อนไหวส่วนบุคคลของผู้เล่นแต่ละคน ขึ้นอยู่กับสถานการณ์ที่พัฒนาขึ้นในระหว่างเกม โดยปกติ การตัดสินใจ (ตัวเลือก) สำหรับการเคลื่อนไหวส่วนบุคคลแต่ละครั้งจะทำโดยผู้เล่นในระหว่างเกม ขึ้นอยู่กับสถานการณ์เฉพาะที่พัฒนาขึ้น อย่างไรก็ตาม ตามทฤษฎีแล้ว สิ่งต่างๆ จะไม่เปลี่ยนแปลงหากเราจินตนาการว่าการตัดสินใจทั้งหมดนี้เกิดขึ้นโดยผู้เล่นล่วงหน้า ในการทำเช่นนี้ ผู้เล่นจะต้องรวบรวมรายการสถานการณ์ทั้งหมดที่เป็นไปได้ล่วงหน้าในระหว่างเกมและจัดเตรียมวิธีแก้ปัญหาของตนเองสำหรับแต่ละสถานการณ์ โดยหลักการแล้ว (หากไม่ใช่ในทางปฏิบัติ) เป็นไปได้สำหรับเกมใดๆ หากใช้ระบบการตัดสินใจดังกล่าว แสดงว่าผู้เล่นได้เลือกกลยุทธ์บางอย่างแล้ว

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

ขึ้นอยู่กับจำนวนของกลยุทธ์ที่เป็นไปได้ เกมแบ่งออกเป็น "จำกัด" และ "ไม่มีที่สิ้นสุด" เกมจำกัดคือเกมที่ผู้เล่นแต่ละคนมีกลยุทธ์จำนวนจำกัดเท่านั้น เกมสุดท้ายที่ผู้เล่น A มี มกลยุทธ์และผู้เล่น B - นกลยุทธ์เรียกว่าเกม mxn

พิจารณาเกม mxn ของผู้เล่นสองคน A และ B (“เรา” และ “คู่ต่อสู้”) เราจะระบุกลยุทธ์ของเรา A 1, A 2, ..., A m ของกลยุทธ์ของศัตรู B 1, B 2,…, B n ให้แต่ละฝ่ายเลือกกลยุทธ์เฉพาะ สำหรับเรามันจะเป็น A i สำหรับศัตรู B j หากเกมประกอบด้วยการเคลื่อนไหวส่วนบุคคล ทางเลือกของกลยุทธ์ A i, B j จะกำหนดผลลัพธ์ของเกมโดยเฉพาะ - เงินรางวัลของเรา ให้เราแสดงว่ามันเป็น ij หากเกมมีการเคลื่อนไหวแบบสุ่ม นอกเหนือจากส่วนบุคคลแล้ว ผลตอบแทนสำหรับกลยุทธ์ A i, B j จะเป็นค่าสุ่มที่ขึ้นอยู่กับผลลัพธ์ของการเคลื่อนไหวแบบสุ่มทั้งหมด ในกรณีนี้ การประมาณการตามธรรมชาติของผลตอบแทนที่คาดหวังคือมูลค่าเฉลี่ย ( มูลค่าที่คาดหวัง). เราจะแสดงด้วยเครื่องหมายเดียวกันทั้งผลตอบแทน (ในเกมที่ไม่มีการเคลื่อนไหวแบบสุ่ม) และค่าเฉลี่ย (ในเกมที่มีการเคลื่อนไหวแบบสุ่ม)

แจ้งให้เราทราบถึงค่าผลตอบแทน ij (หรือผลตอบแทนเฉลี่ย) สำหรับกลยุทธ์แต่ละคู่ ค่าสามารถเขียนได้ในรูปของตารางสี่เหลี่ยม (เมทริกซ์) แถวที่สอดคล้องกับกลยุทธ์ของเรา (A i) และคอลัมน์ที่สอดคล้องกับกลยุทธ์ของศัตรู (B j) ตารางดังกล่าวเรียกว่าเมทริกซ์การจ่ายหรือเพียงแค่เมทริกซ์ของเกม เมทริกซ์เกม mxn แสดงในรูปที่ หนึ่ง.

รูปที่. 1. เมทริกซ์ mxn

ในระยะสั้นเราจะแสดงถึงเมทริกซ์ของเกม ‖а ij ‖ มาดูตัวอย่างเบื้องต้นของเกมกัน

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

เรามีสองกลยุทธ์: A 1 - เพื่อเลือกเสื้อคลุมแขนและ A 2 - เพื่อเลือกหาง; ฝ่ายตรงข้ามมีสองกลยุทธ์เหมือนกัน: B 1 - เสื้อคลุมแขนและ B 2 - หาง ดังนั้นเกมนี้จึงเป็นเกม 2 × 2 ลองพิจารณาการชนะของเหรียญเป็น +1 เกมเมทริกซ์:

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

อันที่จริง สมมติว่าเรา (ผู้เล่น A) ได้เลือกกลยุทธ์บางอย่างสำหรับตัวเราเอง (เช่น A1) และยึดติดกับมัน จากนั้น จากผลของการเคลื่อนไหวสองสามครั้งแรก ศัตรูจะเดาเกี่ยวกับกลยุทธ์ของเราและจะตอบสนองด้วยวิธีที่ได้เปรียบน้อยที่สุดสำหรับเรา กล่าวคือ เลือกหาง เห็นได้ชัดว่าไม่เป็นประโยชน์สำหรับเราที่จะใช้กลยุทธ์ใดกลยุทธ์หนึ่งเสมอ เพื่อไม่ให้เป็นฝ่ายแพ้ บางครั้งเราต้องเลือกเสื้อแขน บางครั้ง - ก้อย อย่างไรก็ตาม หากเราสลับเสื้อคลุมแขนและหางเป็นลำดับ (เช่น หลังหนึ่ง) ศัตรูก็สามารถเดาเกี่ยวกับเรื่องนี้และตอบสนองต่อกลยุทธ์นี้ได้ในทางที่แย่ที่สุดสำหรับเรา แน่นอน วิธีที่เชื่อถือได้เพื่อให้แน่ใจว่าศัตรูไม่รู้ว่ากลยุทธ์ของเราคือจัดระเบียบทางเลือกในทุกการเคลื่อนไหว เมื่อเราไม่รู้ล่วงหน้า (สามารถมั่นใจได้ เช่น โดยการโยนเหรียญ) ดังนั้น โดยการให้เหตุผลโดยสัญชาตญาณ เราจึงมาถึงหนึ่งในแนวคิดที่สำคัญของทฤษฎีเกม - สู่แนวคิดของ "กลยุทธ์แบบผสม" กล่าวคือ เช่นเมื่อกลยุทธ์ "บริสุทธิ์" - ในกรณีนี้ A 1 และ A 2 - สุ่มสลับกับความถี่ที่แน่นอน ในตัวอย่างนี้ จากการพิจารณาความสมมาตร เป็นที่ชัดเจนล่วงหน้าว่ากลยุทธ์ A 1 และ A 2 จะต้องสลับกันด้วยความถี่เดียวกัน ในเกมที่ซับซ้อนมากขึ้น วิธีแก้ปัญหาอาจไม่ใช่เรื่องเล็กน้อย

ตัวอย่างที่ 2ผู้เล่น A และ B พร้อมกันและเป็นอิสระจากกันเขียนตัวเลขหนึ่งในสามตัว: 1, 2 หรือ 3 หากผลรวมของตัวเลขที่เขียนเป็นเลขคู่ B จะจ่าย A จำนวนนี้เป็นรูเบิล ถ้ามันแปลก ในทางกลับกัน A จะจ่ายจำนวนนี้ให้กับ B จำเป็นต้องวิเคราะห์เกมและวาดเมทริกซ์ของเกม

การตัดสินใจ เกมดังกล่าวประกอบด้วยสองการเคลื่อนไหว ทั้งสองเป็นเรื่องส่วนตัว เรา (A) มีสามกลยุทธ์: A 1 - เขียน 1; และ 2 - เขียน 2; และ 3 - เขียน 3 ฝ่ายตรงข้าม (B) มีสามกลยุทธ์เหมือนกัน เกมดังกล่าวเป็นเกม 3 × 3:

เห็นได้ชัดว่า ในกรณีก่อนหน้านี้ ศัตรูสามารถตอบสนองต่อกลยุทธ์ที่เราเลือกได้แย่ที่สุดสำหรับเรา แท้จริงแล้วถ้าเราเลือกเช่นกลยุทธ์ A1 ศัตรูจะตอบโต้ด้วยกลยุทธ์ B2 เสมอ ในกลยุทธ์ A 2 - โดยกลยุทธ์ B 3; ในกลยุทธ์ A 3 - โดยกลยุทธ์ B 2; ดังนั้นการเลือกกลยุทธ์บางอย่างย่อมนำเราไปสู่ความสูญเสียอย่างหลีกเลี่ยงไม่ได้ (อย่างไรก็ตาม ไม่จำเป็นต้องลืมว่าศัตรูอยู่ในสถานการณ์ที่ลำบากเช่นเดียวกัน) วิธีแก้ปัญหาของเกมนี้ (เช่น ชุดกลยุทธ์ที่ได้เปรียบที่สุดของผู้เล่นทั้งสอง) จะได้รับใน § 5

ตัวอย่างที่ 3เรามีอาวุธสามประเภทให้เลือก: А 1, А 2, А 3; ศัตรูมีเครื่องบินสามประเภท: B 1, B 2, B 3 งานของเราคือชนเครื่องบิน หน้าที่ของศัตรูคือการทำให้เขาไม่ได้รับผลกระทบ เมื่อใช้อาวุธ A 1 เครื่องบิน B 1, B 2, B 3 จะถูกโจมตีด้วยความน่าจะเป็น 0.9, 0.4 และ 0.2 ตามลำดับ; ด้วยอาวุธ A 2 - ด้วยความน่าจะเป็น 0.3, 0.6 และ 0.8; ด้วยอาวุธ A 3 - ด้วยความน่าจะเป็น 0.5, 0.7 และ 0.2 จำเป็นต้องกำหนดสถานการณ์ในแง่ของทฤษฎีเกม

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

เป้าหมายของทฤษฎีเกมคือการให้คำแนะนำสำหรับ พฤติกรรมที่สมเหตุสมผลผู้เล่นใน สถานการณ์ความขัดแย้งกล่าวคือ การกำหนด "กลยุทธ์ที่เหมาะสมที่สุด" สำหรับแต่ละคน กลยุทธ์ที่ดีที่สุดของผู้เล่นในทฤษฎีเกมคือกลยุทธ์ที่เมื่อเกมซ้ำหลายครั้ง ให้ผู้เล่นที่กำหนดได้รับค่าเฉลี่ยสูงสุดที่เป็นไปได้ (หรือการสูญเสียเฉลี่ยขั้นต่ำที่เป็นไปได้) ในการเลือกกลยุทธ์นี้ พื้นฐานของการให้เหตุผลคือข้อสันนิษฐานว่าอย่างน้อยศัตรูก็ฉลาดพอๆ กับตัวเราเอง และทำทุกอย่างเพื่อป้องกันไม่ให้เราบรรลุเป้าหมาย

ในทฤษฎีเกม คำแนะนำทั้งหมดมีขึ้นบนพื้นฐานของหลักการเหล่านี้ ดังนั้นจึงไม่คำนึงถึงองค์ประกอบของความเสี่ยงที่มีอยู่ในทุกกลยุทธ์จริงอย่างหลีกเลี่ยงไม่ได้ เช่นเดียวกับการคำนวณที่ผิดพลาดและข้อผิดพลาดของผู้เล่นแต่ละคน ทฤษฎีเกม อะไรก็ได้ แบบจำลองทางคณิตศาสตร์ปรากฏการณ์ที่ซับซ้อนมีข้อ จำกัด ของตัวเอง สิ่งที่สำคัญที่สุดคือกำไรจะลดลงเหลือหนึ่ง เอกพจน์... ในสถานการณ์ความขัดแย้งในทางปฏิบัติส่วนใหญ่ เมื่อมีการพัฒนากลยุทธ์ที่สมเหตุสมผล จำเป็นต้องคำนึงถึงพารามิเตอร์ตัวเลขไม่ใช่ตัวเดียว แต่มีหลายอย่าง - เกณฑ์สำหรับความสำเร็จของเหตุการณ์ กลยุทธ์ที่เหมาะสมที่สุดในเกณฑ์หนึ่งไม่จำเป็นต้องเหมาะสมกับเกณฑ์อื่นเสมอไป อย่างไรก็ตาม เมื่อตระหนักถึงข้อจำกัดเหล่านี้และดังนั้นจึงไม่ปฏิบัติตามคำแนะนำที่ได้รับจากวิธีการของเกมอย่างสุ่มสี่สุ่มห้า เรายังคงสามารถใช้เครื่องมือทางคณิตศาสตร์ของทฤษฎีเกมอย่างสมเหตุสมผลเพื่อพัฒนาได้ หากไม่ "เหมาะสมที่สุด" ไม่ว่าในกรณีใด ก็ถือว่า "ยอมรับได้" กลยุทธ์.

§ 2 ราคาที่ต่ำกว่าและด้านบนของเกม หลักการมินิแมกซ์

พิจารณาเกม mxn ที่มีเมทริกซ์ดังในรูปที่ 1. ให้แทนด้วยตัวอักษร i จำนวนของกลยุทธ์ของเรา ตัวอักษร j คือจำนวนกลยุทธ์ของฝ่ายตรงข้าม มากำหนดภารกิจกัน: เพื่อกำหนดกลยุทธ์ที่เหมาะสมที่สุดของเรา มาวิเคราะห์แต่ละกลยุทธ์ของเราตามลำดับโดยเริ่มจาก A 1

การเลือกกลยุทธ์ А ฉัน เราควรนับความจริงที่ว่าศัตรูจะตอบโต้ด้วยกลยุทธ์ В j ซึ่งผลตอบแทนของเรานั้นน้อยมาก ให้เรากำหนดมูลค่าของผลตอบแทน เช่น ค่าต่ำสุดของตัวเลข a ij in ผมบรรทัดที่ ให้เราแสดงมันโดย α i:

ที่นี่เครื่องหมายขั้นต่ำ (ขั้นต่ำใน j) หมายถึงค่าต่ำสุดของพารามิเตอร์นี้สำหรับ j ที่เป็นไปได้ทั้งหมด ให้เราเขียนตัวเลข α i; ถัดจากเมทริกซ์ทางด้านขวาเป็นคอลัมน์พิเศษ:

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

หรือโดยคำนึงถึงสูตร (2.1)

ค่า α เรียกว่าราคาที่ต่ำกว่าของเกม กล่าวอีกนัยหนึ่ง - ค่าสูงสุดที่ชนะหรือเพียงแค่ค่าสูงสุด จำนวน α อยู่ในเส้นหนึ่งของเมทริกซ์ กลยุทธ์ของผู้เล่น A ที่สอดคล้องกับบรรทัดนี้เรียกว่ากลยุทธ์สูงสุด แน่นอน หากเรายึดมั่นในกลยุทธ์สูงสุด สำหรับพฤติกรรมใดๆ ของศัตรู เรารับประกันว่าจะได้รับผลตอบแทน อย่างน้อยก็ไม่น้อยกว่า α ดังนั้นค่าของ α จึงเรียกว่า "ราคาเกมที่ต่ำกว่า" นี่คือการรับประกันขั้นต่ำที่เราสามารถจัดหาได้เองโดยปฏิบัติตามกลยุทธ์ที่ชาญฉลาดที่สุด ("การประกันภัยต่อ")

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

และหาค่าต่ำสุดของ β j:

ค่า β เรียกว่าราคาสูงสุดของเกม หรืออีกนัยหนึ่งคือ "minimax" กลยุทธ์ของฝ่ายตรงข้ามที่สอดคล้องกับกำไรขั้นต่ำเรียกว่า "กลยุทธ์ขั้นต่ำ" ของเขา ฝ่ายตรงข้ามปฏิบัติตามกลยุทธ์ขั้นต่ำสุดที่ระมัดระวังที่สุดของเขา: ไม่ว่าเราจะทำอะไรกับเขา เขาจะสูญเสียจำนวนเงินไม่เกิน β ไม่ว่าในกรณีใดๆ หลักการของความระมัดระวังซึ่งกำหนดทางเลือกของกลยุทธ์ที่เหมาะสม (maximin และ minimax) สำหรับผู้เล่น มักเรียกว่า "หลักการ minimax" ในทฤษฎีเกมและการใช้งาน กลยุทธ์ maximin และ minimax ที่ระมัดระวังที่สุดของผู้เล่นบางครั้งแสดงไว้ คำทั่วไป"กลยุทธ์มินิแม็กซ์".

ตัวอย่างเช่น เรากำหนดราคาเกมที่ต่ำกว่าและสูงกว่าและกลยุทธ์ขั้นต่ำสุดสำหรับตัวอย่าง 1, 2 และ 3 ของ § 1

ตัวอย่างที่ 1ตัวอย่างที่ 1 § 1 ให้เกมที่มีเมทริกซ์ต่อไปนี้:

เนื่องจากค่า α i และ β j เป็นค่าคงที่และเท่ากับ –1 และ +1 ตามลำดับ ราคาเกมที่ต่ำกว่าและบนจึงเป็น –1 และ +1: α = –1, β = +1 กลยุทธ์ใดๆ ของผู้เล่น A คือกลยุทธ์สูงสุดของเขา และกลยุทธ์ใดๆ ของผู้เล่น B คือกลยุทธ์ขั้นต่ำสุดของเขา ข้อสรุปเป็นเรื่องเล็กน้อย: โดยการปฏิบัติตามกลยุทธ์ของเขา ผู้เล่น A สามารถรับประกันได้ว่าเขาจะแพ้ไม่เกิน 1 ผู้เล่น B สามารถรับประกันได้เช่นเดียวกัน

ตัวอย่างที่ 2ตัวอย่างที่ 2 § 1 ให้เกมที่มีเมทริกซ์:

ราคาที่ต่ำกว่าของเกมคือ α = –3; ราคาสูงสุดของเกม β = 4 กลยุทธ์สูงสุดของเราคือ А 1; โดยการใช้อย่างเป็นระบบ เราสามารถคาดหวังได้อย่างแน่วแน่ว่าจะชนะอย่างน้อย –3 (แพ้มากที่สุด 3) กลยุทธ์ขั้นต่ำสุดของคู่ต่อสู้คือกลยุทธ์ B 1 และ B 2; ประยุกต์ใช้อย่างเป็นระบบ ยังไงก็ได้ รับรองได้เลยว่าแพ้ไม่เกิน 4 ถ้าเราเบี่ยงเบนจากกลยุทธ์สูงสุดของเรา (เช่น เลือกกลยุทธ์ A2) ฝ่ายตรงข้ามสามารถ "ลงโทษ" เราด้วยการใช้กลยุทธ์ B 3 และการลดชัยชนะของเราคือ -5; ในทำนองเดียวกัน การถอยของฝ่ายตรงข้ามจากกลยุทธ์ minimax ของเขาสามารถเพิ่มการสูญเสียของเขาเป็น 6

ตัวอย่างที่ 3ตัวอย่างที่ 3 § 1 ให้เกมที่มีเมทริกซ์:

ราคาที่ต่ำกว่าของเกมคือ α = 0.3; ค่าสูงสุดของเกม β = 0.7 กลยุทธ์ที่อนุรักษ์นิยมมากที่สุด (สูงสุด) ของเราคือ A 2; การใช้อาวุธ A2 เรารับประกันว่าเราจะโจมตีเครื่องบินโดยเฉลี่ยอย่างน้อย 0.3 ในทุกกรณี กลยุทธ์ของศัตรูที่ระมัดระวังที่สุด (minimax) คือ B 2; โดยใช้เครื่องบินลำนี้ ศัตรูสามารถมั่นใจได้ว่าเขาจะโดนไม่เกิน 0.7 ของทุกกรณี

ตัวอย่างสุดท้ายสะดวกที่จะสาธิตหนึ่ง ทรัพย์สินที่สำคัญกลยุทธ์ minimax - ความไม่แน่นอนของพวกเขา ให้เราใช้กลยุทธ์ที่ระมัดระวังที่สุด (สูงสุด) А 2 และศัตรู - กลยุทธ์ที่ระมัดระวังที่สุด (ขั้นต่ำสุด) В 2 ตราบใดที่ฝ่ายตรงข้ามทั้งสองปฏิบัติตามกลยุทธ์เหล่านี้ ผลตอบแทนเฉลี่ยคือ 0.6; มันมากกว่าอันที่ต่ำกว่า แต่น้อยกว่าราคาบนของเกม ตอนนี้ สมมติว่าปฏิปักษ์ได้เรียนรู้ว่าเรากำลังใช้กลยุทธ์ A 2; เขาจะตอบสนองต่อมันทันทีด้วยกลยุทธ์ B 1 และลดเงินรางวัลเหลือ 0.3 ในทางกลับกัน เรามีคำตอบที่ดีสำหรับกลยุทธ์ B 1: กลยุทธ์ A 1 ซึ่งให้ผลตอบแทนแก่เรา 0.9 เป็นต้น

ดังนั้น ตำแหน่งที่ผู้เล่นทั้งสองใช้กลยุทธ์ minimax ของพวกเขาจึงไม่เสถียรและสามารถละเมิดได้โดยข้อมูลที่ได้รับเกี่ยวกับกลยุทธ์ของฝ่ายตรงข้าม อย่างไรก็ตาม มีบางเกมที่กลยุทธ์ minimax มีเสถียรภาพ นี่คือเกมที่ราคาที่ต่ำกว่าเท่ากับเกมบน: α = β หากราคาที่ต่ำกว่าของเกมเท่ากับราคาบน มูลค่ารวมจะเรียกว่าราคาสุทธิของเกม (บางครั้งเป็นเพียงราคาของเกม) เราจะระบุด้วยตัวอักษร ν

มาดูตัวอย่างกัน ให้เมทริกซ์ให้เกม 4 × 4:

ลองหาราคาที่ต่ำกว่าของเกม: α = 0.6 มาหาราคาที่สูงกว่าของเกมกัน: β = 0.6 กลับกลายเป็นว่าเหมือนกัน ดังนั้น เกมดังกล่าวจึงมีราคาสุทธิเท่ากับ α = β = ν = 0.6 องค์ประกอบ 0.6 ที่เน้นในเมทริกซ์ผลตอบแทน เป็นทั้งค่าต่ำสุดในแถวและค่าสูงสุดในคอลัมน์ ในเรขาคณิต จุดบนพื้นผิวที่มีคุณสมบัติคล้ายกัน (จุดต่ำสุดพร้อมกันตามพิกัดหนึ่งและจุดสูงสุดพร้อมกัน) เรียกว่าจุดอาน โดยการเปรียบเทียบ คำนี้ยังใช้ในทฤษฎีเกมด้วย องค์ประกอบของเมทริกซ์ที่มีคุณสมบัตินี้เรียกว่าจุดอานของเมทริกซ์ และมีการกล่าวถึงเกมว่ามีจุดอาน

จุดอานสอดคล้องกับกลยุทธ์ขั้นต่ำคู่หนึ่ง (ในตัวอย่างนี้ A 3 และ B 2) กลยุทธ์เหล่านี้เรียกว่าเหมาะสมที่สุด และการรวมกันของกลยุทธ์เหล่านี้เรียกว่าวิธีแก้ปัญหาของเกม การแก้ปัญหาของเกมมีคุณสมบัติที่โดดเด่นดังต่อไปนี้ หากผู้เล่นคนใดคนหนึ่ง (เช่น A) ปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุดของเขา และผู้เล่นอีกคนหนึ่ง (B) เบี่ยงเบนไปจากกลยุทธ์ที่เหมาะสมของเขาในทางใดทางหนึ่ง ดังนั้นสำหรับผู้เล่นที่เบี่ยงเบน สิ่งนี้จะไม่เป็นประโยชน์เช่น การเบี่ยงเบนของผู้เล่น B สามารถปล่อยให้เงินรางวัลไม่เปลี่ยนแปลงได้ดีที่สุดและในกรณีที่เลวร้ายที่สุด - เพิ่มขึ้น ในทางกลับกัน หาก B ยึดมั่นในกลยุทธ์ที่เหมาะสมที่สุด และ A เบี่ยงเบนไปจากกลยุทธ์ของตัวเอง วิธีนี้ก็ไม่อาจเป็นประโยชน์สำหรับ A ได้ในทุกกรณี

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

ดังนั้น สำหรับเกมจุดอานทุกเกม มีวิธีแก้ปัญหาที่กำหนดกลยุทธ์ที่เหมาะสมที่สุดสำหรับทั้งสองฝ่าย ซึ่งมีคุณสมบัติดังต่อไปนี้

1) หากทั้งสองฝ่ายปฏิบัติตามกลยุทธ์ที่เหมาะสม ผลตอบแทนเฉลี่ยจะเท่ากับราคาสุทธิของเกม ν ซึ่งเป็นราคาที่ต่ำกว่าและสูงกว่าพร้อมกัน

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

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

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

§ 3 กลยุทธ์ที่บริสุทธิ์และผสมผสาน การแก้ปัญหาของเกมในกลยุทธ์แบบผสม

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

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

ข้อความข้างต้นประกอบด้วยเนื้อหาที่เรียกว่าทฤษฎีบทหลักของทฤษฎีเกม ทฤษฎีบทนี้ได้รับการพิสูจน์ครั้งแรกโดยฟอน นอยมันน์ในปี ค.ศ. 1928 การพิสูจน์ทฤษฎีบทนี้ค่อนข้างซับซ้อน ดังนั้นเราจึงนำเสนอเฉพาะสูตรของมันเท่านั้น

ท้ายเกมแต่ละเกมมีวิธีแก้ปัญหาอย่างน้อยหนึ่งวิธี (อาจอยู่ในพื้นที่ของกลยุทธ์แบบผสม)

กำไรที่เกิดจากการตัดสินใจเรียกว่าต้นทุนของเกม ทฤษฎีบทหลักบอกเป็นนัยว่าทุกเกมจำกัดมีราคา เห็นได้ชัดว่าราคาของเกม ν อยู่ระหว่างราคาที่ต่ำกว่าของเกม α และราคาสูงกว่าของเกม β เสมอ:

(3.1) α ≤ ν ≤ β

อันที่จริง α เป็นผลตอบแทนที่รับประกันสูงสุดที่เราสามารถจัดหาได้โดยใช้กลยุทธ์ที่บริสุทธิ์ เนื่องจากเป็นกรณีพิเศษ กลยุทธ์แบบผสมรวมถึงกลยุทธ์ที่บริสุทธิ์ทั้งหมด จากนั้น ยอมรับ นอกเหนือจากกลยุทธ์ที่บริสุทธิ์แล้ว ยังรวมถึงกลยุทธ์แบบผสมด้วย ไม่ว่าในกรณีใดๆ เราจะไม่ทำให้ความสามารถของเราแย่ลง ดังนั้น ν ≥ α ในทำนองเดียวกัน เมื่อพิจารณาถึงความสามารถของคู่ต่อสู้ เราแสดงว่า ν ≤ β ซึ่งแสดงถึงความไม่เท่าเทียมกันที่พิสูจน์แล้ว (3.1)

ให้เราแนะนำสัญลักษณ์พิเศษสำหรับกลยุทธ์แบบผสม ตัวอย่างเช่น หากกลยุทธ์แบบผสมของเราประกอบด้วยการใช้กลยุทธ์ A 1, A 2, A 3 ที่มีความถี่ p 1, p 2, p 3 และ p 1 + p 2 + p 3 = 1 เราจะแสดงว่ากลยุทธ์นี้

ในทำนองเดียวกัน กลยุทธ์ผสมของศัตรูจะแสดงโดย:

โดยที่ q 1, q 2, q 3 - ความถี่ที่กลยุทธ์ B 1, B 2, B 3 ผสมกัน q 1 + q 2 + q 3 = 1

สมมติว่าเราพบวิธีแก้ปัญหาของเกมซึ่งประกอบด้วยสองกลยุทธ์แบบผสมที่เหมาะสมที่สุด S A *, S B * ในกรณีทั่วไป ไม่ใช่ทุกกลยุทธ์ที่มีให้สำหรับผู้เล่นรายใดรายหนึ่งจะรวมอยู่ในกลยุทธ์ผสมที่เหมาะสมที่สุดของเขา แต่มีเพียงบางส่วนเท่านั้น เราจะเรียกกลยุทธ์ที่รวมอยู่ในกลยุทธ์แบบผสมที่ดีที่สุดของผู้เล่นกลยุทธ์ที่ "มีประโยชน์" ของเขา ปรากฎว่าการแก้ปัญหาของเกมมีคุณสมบัติที่โดดเด่นอีกอย่างหนึ่ง: หากผู้เล่นคนใดคนหนึ่งปฏิบัติตามกลยุทธ์ผสมที่ดีที่สุดของเขา SA * (SB *) ผลตอบแทนจะยังคงไม่เปลี่ยนแปลงและเท่ากับราคาของเกม ν โดยไม่คำนึงถึง สิ่งที่ผู้เล่นคนอื่นทำ เว้นแต่เขาจะทำเกินกว่ากลยุทธ์ที่ "มีประโยชน์" ตัวอย่างเช่น เขาสามารถใช้กลยุทธ์ที่ "มีประโยชน์" ในรูปแบบที่บริสุทธิ์ และยังสามารถผสมในสัดส่วนใดก็ได้

§ 4. วิธีการเบื้องต้นในการแก้เกม เกมส์2x2 และ 2xน

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

เป็นเรื่องง่ายที่จะทำให้แน่ใจว่ากลยุทธ์ А 3 ซ้ำกัน ("ซ้ำกัน") กลยุทธ์ А 1 ดังนั้น กลยุทธ์ใดในสองกลยุทธ์นี้ก็สามารถลบได้ นอกจากนี้ เมื่อเปรียบเทียบแถว A 1 และ A 2 เราจะเห็นว่าแต่ละองค์ประกอบของแถว A2 มีค่าน้อยกว่า (หรือเท่ากับ) องค์ประกอบที่สอดคล้องกันของแถว A 1 เห็นได้ชัดว่าเราไม่ควรใช้กลยุทธ์ A2 เพราะเป็นการจงใจไม่สร้างกำไร โดยการลบ A 3 และ A 2 เรานำเมทริกซ์ไปที่ more ใจง่าย... นอกจากนี้ เราสังเกตว่ากลยุทธ์ B 3 เห็นได้ชัดว่าไม่เป็นประโยชน์สำหรับคู่ต่อสู้ การลบออก เรานำเมทริกซ์มาสู่รูปแบบสุดท้าย:

ดังนั้นเกม 4 × 4 จะลดลงเหลือ 2 × 3 เกมโดยกำจัดกลยุทธ์ที่ซ้ำซ้อนและเสียเปรียบอย่างเห็นได้ชัด

ขั้นตอนในการลบกลยุทธ์ที่ซ้ำซ้อนและไม่เอื้ออำนวยควรมาก่อนการตัดสินใจของเกมเสมอ กรณีที่ง่ายที่สุดของเกมไฟไนต์ซึ่งสามารถแก้ไขได้โดยวิธีการพื้นฐานคือเกม 2 × 2 และ 2xn

พิจารณาเกม 2 × 2 ที่มีเมทริกซ์:

สองกรณีสามารถเกิดขึ้นได้ที่นี่: 1) เกมมีจุดอาน; 2) เกมไม่มีจุดอาน ในกรณีแรก วิธีแก้ปัญหานั้นชัดเจน: เป็นกลยุทธ์คู่หนึ่งที่ตัดกันที่จุดอาน อย่างไรก็ตาม โปรดทราบว่าในเกม 2 × 2 การปรากฏตัวของจุดอานมักจะสอดคล้องกับการมีอยู่ของกลยุทธ์ที่เสียเปรียบโดยเจตนาซึ่งควรลบทิ้งในการวิเคราะห์เบื้องต้น

อย่าให้มีจุดอาน ดังนั้นราคาที่ต่ำกว่าของเกมจึงไม่เท่ากับราคาบน: α ≠ β จำเป็นต้องหากลยุทธ์ผสมที่ดีที่สุดของผู้เล่น A:

ทรัพย์สินนั้นแตกต่างจากการกระทำของฝ่ายตรงข้าม (เว้นแต่เขาจะเกินขอบเขตของกลยุทธ์ที่ "มีประโยชน์" ของเขา) ผลตอบแทนจะเท่ากับราคาเกม ν ในเกม 2 × 2 กลยุทธ์ของศัตรูทั้งสอง "มีประโยชน์" ไม่เช่นนั้นเกมจะมีวิธีแก้ปัญหาเชิงกลยุทธ์ที่บริสุทธิ์ (จุดอาน) ซึ่งหมายความว่าหากเราปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุด (4.1) ฝ่ายตรงข้ามสามารถใช้กลยุทธ์ B 1, B 2 ที่แท้จริงของเขาโดยไม่ต้องเปลี่ยนผลตอบแทนเฉลี่ย ν ดังนั้นเราจึงมีสองสมการ:

จากนั้นเมื่อพิจารณาว่า p 1 + p 2 = 1 เราได้รับ:

เราหาค่าของเกม ν โดยการแทนค่า p 1, p 2 ลงในสมการใดก็ได้ (4.2)

หากทราบราคาของเกมแล้วให้กำหนดกลยุทธ์ที่ดีที่สุดของฝ่ายตรงข้าม

สมการเดียวก็เพียงพอแล้ว ตัวอย่างเช่น

ดังนั้นเมื่อพิจารณาว่า q 1 + q 2 = 1 เรามี:

ตัวอย่างที่ 1ให้เราหาวิธีแก้ปัญหาของเกม 2 × 2 ที่พิจารณาในตัวอย่างที่ 1 § 1 ด้วยเมทริกซ์:

เกมดังกล่าวไม่มีจุดอาน (α = –1; β = +1) ดังนั้นการแก้ปัญหาจะต้องอยู่ในขอบเขตของกลยุทธ์แบบผสม:

คุณต้องหา p 1, p 2, q 1 และ q 2 สำหรับ p 1 เรามีสมการ

1 * p 1 + (–1) (1 - p 1) = (–1) p 1 + 1 (1 - p 1)

โดยที่ p 1 = 1/2, p 2 = 1/2

ในทำนองเดียวกัน เราพบ: q 1 = 1/2, q 2 = 1/2, ν = 0

ดังนั้น กลยุทธ์ที่เหมาะสมที่สุดสำหรับผู้เล่นแต่ละคนคือการสุ่มสลับกลยุทธ์บริสุทธิ์ทั้งสองอย่างโดยสุ่ม โดยใช้แต่ละกลยุทธ์เท่าๆ กัน ในกรณีนี้ ผลตอบแทนเฉลี่ยจะเท่ากับศูนย์

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

ตัวอย่างที่ 2เกมมีดังนี้ มีไพ่สองใบ: เอซและผีสาง ผู้เล่น A สุ่มจับหนึ่งในนั้น B ไม่เห็นไพ่ใบไหนที่เขาหยิบออกมา ถ้า A หยิบเอซออกมา เขาประกาศว่า: "ฉันมีเอซ" และเรียกร้องจากฝ่ายตรงข้าม 1 รูเบิล ถ้า A หยิบผีออกมา เขาสามารถ A 1) พูดว่า "ฉันมีเอซ" และเรียกร้อง 1 รูเบิลจากคู่ต่อสู้ หรือ A 2) ยอมรับว่าเขามีผีและจ่ายเงินให้ฝ่ายตรงข้าม 1 รูเบิล

ศัตรูถ้าเขาได้รับเงินโดยสมัครใจ 1 รูเบิลก็สามารถยอมรับได้ หากมีการเรียกร้อง 1 รูเบิลจากเขา เขาสามารถ B 1) เชื่อผู้เล่น A ว่าเขามีเอซและให้ 1 รูเบิลแก่เขา หรือ B 2) เรียกเช็คเพื่อให้แน่ใจว่าข้อความ A นั้นตรวจสอบแล้วกลายเป็นว่า A มีเอซจริงๆ B ต้องจ่าย A 2 rubles หากปรากฎว่า A นอกใจและเขามีผีสาง ผู้เล่น A จ่ายผู้เล่น B 2 รูเบิล จำเป็นต้องวิเคราะห์เกมและค้นหากลยุทธ์ที่เหมาะสมที่สุดสำหรับผู้เล่นแต่ละคน

การตัดสินใจเกมนี้มีโครงสร้างที่ค่อนข้างซับซ้อน มันประกอบด้วยการสุ่มย้ายที่จำเป็น - ผู้เล่น A เลือกหนึ่งในไพ่สองใบ - และการเคลื่อนไหวส่วนตัวสองใบซึ่งไม่จำเป็นต้องเกิดขึ้น แท้จริงแล้วถ้า A หยิบเอซออกมา เขาก็จะไม่เคลื่อนไหวส่วนตัวใดๆ เลย: เขามีโอกาสเพียงครั้งเดียว - เพื่อเรียกร้อง 1 รูเบิล ซึ่งเขาทำได้ ในกรณีนี้ การย้ายส่วนบุคคล - เชื่อหรือไม่เชื่อ (เช่น จ่ายหรือไม่จ่าย 1 รูเบิล) - จะถูกโอนไปยังผู้เล่น B หาก A เป็นผลมาจากการย้ายแบบสุ่มครั้งแรกได้รับสอง เขาจะได้รับส่วนบุคคล ย้าย: จ่าย 1 รูเบิลหรือพยายามโกงศัตรูและเรียกร้อง 1 รูเบิล (โดยย่อ: "อย่าหลอกลวง" หรือ "หลอกลวง") หาก A เลือกตัวเลือกแรก B ต้องยอมรับ 1 รูเบิลเท่านั้น ถ้า A เลือกอย่างหลัง ผู้เล่น B จะได้รับการเคลื่อนไหวส่วนบุคคล: เชื่อหรือไม่เชื่อ A (นั่นคือ จ่าย A 1 รูเบิลหรือการยืนยันความต้องการ)

กลยุทธ์ของผู้เล่นแต่ละคนเป็นกฎที่ระบุว่าผู้เล่นควรทำตัวอย่างไรเมื่อเขาได้รับการเคลื่อนไหวส่วนตัว เห็นได้ชัดว่า A มีเพียงสองกลยุทธ์: A 1 - เพื่อโกง A 2 - ไม่โกง B มีสองกลยุทธ์: B 1 - เชื่อ B 2 - ไม่เชื่อ มาสร้างเมทริกซ์เกมกันเถอะ ในการทำเช่นนี้ เราคำนวณผลตอบแทนเฉลี่ยสำหรับกลยุทธ์แต่ละชุดรวมกัน

1. A 1 B 1 (A หลอกลวง B เชื่อ) หาก A ได้รับเอซ (ความน่าจะเป็นของสิ่งนี้คือ ½ แสดงว่าเขาไม่ได้รับการเคลื่อนไหวส่วนตัว เขาต้องการ 1 รูเบิล และผู้เล่น B เชื่อเขา การเพิ่มของ A ในรูเบิลคือ 1 หาก A ได้รับสอง (ความน่าจะเป็นของสิ่งนี้) เท่ากับ ½) ตามกลยุทธ์ของเขา เขาโกงและเรียกร้อง 1 รูเบิล เชื่อในตัวเขาและจ่าย ผลตอบแทน A ก็เท่ากับ 1 ผลตอบแทนเฉลี่ย: 11 = ½ * 1 + ½ * 1 = 1

2. A 1 B 2 (A หลอกลวง B ไม่เชื่อ) ถ้า A ได้เอซ เขาไม่มีการเคลื่อนไหวส่วนตัว เขาต้องการ 1 รูเบิล; ตามกลยุทธ์ของเขาเขาไม่เชื่อและจากเช็คจ่าย 2 รูเบิล (กำไรของ A คือ +2) ถ้า A ได้ผี ตามกลยุทธ์ของเขา เขาต้องการ 1 รูเบิล; ข ตามของเขาเอง ไม่เชื่อ; เป็นผลให้ A จ่าย 2 rubles (กำไรของ A คือ –2) ผลตอบแทนเฉลี่ย: a 12 = ½ * (+ 2) + ½ * (- 2) = 0

3. A 2 B 1 (A ไม่หลอกลวง B เชื่อ) ถ้า A นำเอซออกมา เขาต้องการ 1 รูเบิล; B ตามกลยุทธ์ของเขา จ่าย; กำไรของ A คือ +1 ถ้า A หยิบผีออกมา เขาจ่าย 1 รูเบิลตามกลยุทธ์ของเขา เหลือเพียงการยอมรับ (กำไรของ A คือ –1) ผลตอบแทนเฉลี่ย: a 21 = ½ * (+ 1) + ½ * (- 1) = 0

4. A 2 B 2 (A ไม่หลอกลวง B ไม่เชื่อ) ถ้า A นำเอซออกมา เขาต้องการ 1 รูเบิล; B เช็คและจากเช็คจ่าย 2 รูเบิล (ชนะคือ +2) ถ้า A นำผีออกมา เขาจ่าย 1 รูเบิล; เหลือเพียงการยอมรับ (ผลตอบแทนคือ 1) ผลตอบแทนเฉลี่ย: 22 = ½ * (+ 2) + ½ * (- 1) = ½

เราสร้างเมทริกซ์เกม:

เมทริกซ์ไม่มีจุดอาน ราคาที่ต่ำกว่าของเกมคือ α = 0 ราคาที่สูงขึ้นของเกมคือ β = ½ มาค้นหาวิธีแก้ปัญหาของเกมในด้านกลยุทธ์แบบผสมกัน ใช้สูตร (4.3) เราได้รับ:

เหล่านั้น ผู้เล่น A ควรใช้กลยุทธ์แรก (โกง) ในหนึ่งในสามของทุกกรณี และกลยุทธ์ที่สอง (ไม่โกง) ในสองในสาม ในกรณีนี้เขาจะชนะในราคาของเกมโดยเฉลี่ย ν = 1/3

ค่า ν = 1/3 บ่งชี้ว่าภายใต้เงื่อนไขเหล่านี้ เกมจะเป็นประโยชน์สำหรับ A และไม่เอื้ออำนวยสำหรับ B การใช้กลยุทธ์ที่เหมาะสมที่สุดของเขา A สามารถให้ผลตอบแทนเฉลี่ยที่เป็นบวกแก่ตนเองได้เสมอ โปรดทราบว่าหาก A ใช้กลยุทธ์ที่ระมัดระวังที่สุด (สูงสุด) ของเขา (ในกรณีนี้ ทั้งกลยุทธ์ A 1 และ A 2 เป็นกลยุทธ์สูงสุด) เขาจะมีผลตอบแทนเฉลี่ยเท่ากับศูนย์ ดังนั้น การใช้กลยุทธ์แบบผสมทำให้ A มีโอกาสที่จะตระหนักถึงความได้เปรียบของเขาเหนือ B ซึ่งเกิดขึ้นภายใต้กฎที่กำหนดของเกม

มากำหนดกลยุทธ์ที่เหมาะสมที่สุด B เรามี: q 1 * 1 + q 2 * 0 = 1/3, q 1 = 1/3, q 2 = 2/3 จากไหน

กล่าวคือ ผู้เล่น B ต้องไว้วางใจ A ในหนึ่งในสามของทุกกรณีและจ่าย 1 รูเบิลให้เขาโดยไม่ต้องตรวจสอบและในสองในสามของกรณี - ตรวจสอบ จากนั้นเขาจะแพ้โดยเฉลี่ย 1/3 สำหรับแต่ละเกม ถ้าเขาใช้กลยุทธ์ขั้นต่ำสุด B 2 (อย่าเชื่อ) เขาจะแพ้โดยเฉลี่ย 1/2 สำหรับแต่ละเกม

วิธีแก้ปัญหาของเกม 2 × 2 สามารถให้การตีความทางเรขาคณิตอย่างง่าย ให้มีเกม 2 × 2 กับเมทริกซ์

ใช้ส่วนของแกน abscissa ที่มีความยาว 1 (รูปที่ 4.1) ปลายด้านซ้ายของส่วน (จุดที่มี abscissa x = 0) จะแสดงกลยุทธ์ A 1; ด้านขวาสุดของส่วน (x = 1) - กลยุทธ์ A 2 ลองวาดเส้นตั้งฉากสองอันกับแกน abscissa ผ่านจุด А 1 และ А 2: ผม-ผมและแกน II – II... บนแกน ผม-ผมเราจะเลื่อนการชนะสำหรับกลยุทธ์ A 1; บนแกน II – II-ชนะด้วยกลยุทธ์ A 2 พิจารณากลยุทธ์ของฝ่ายตรงข้าม B 1; มันให้สองจุดบนแกน ผม-ผมและ II – IIด้วยพิกัด 11 และ 21 ตามลำดับ ให้เราวาดเส้นตรง B 1 B 1 ผ่านจุดเหล่านี้ แน่นอนว่าถ้าใช้กลยุทธ์ของศัตรู B 1 เราจะใช้กลยุทธ์แบบผสม

แล้วผลตอบแทนเฉลี่ยของเรา ซึ่งเท่ากับในกรณีนี้คือ 11 p 1 + a 21 p 2 จะแสดงด้วยจุด M บนเส้น B 1 B 1 abscissa ของจุดนี้เท่ากับ p 2 เส้นตรง В 1 В 1 ซึ่งแสดงถึงผลตอบแทนในกรณีของกลยุทธ์ В 1 จะถูกเรียกว่า "กลยุทธ์ В 1" ตามอัตภาพ

เห็นได้ชัดว่ากลยุทธ์ B2 สามารถสร้างได้ในลักษณะเดียวกันทุกประการ (รูปที่ 4.2)

เราจำเป็นต้องค้นหากลยุทธ์ที่เหมาะสมที่สุด S A * นั่นคือกลยุทธ์ที่ผลตอบแทนขั้นต่ำ (สำหรับพฤติกรรมใดๆ ของ B) จะกลายเป็นค่าสูงสุด ในการทำเช่นนี้ เราสร้างขอบเขตผลตอบแทนที่ต่ำกว่าสำหรับกลยุทธ์ B 1, B 2 เช่น เส้นหัก B 1 NB 2 ทำเครื่องหมายในรูปที่ 4.2 มีเส้นหนา ขอบเขตล่างนี้จะแสดงผลตอบแทนขั้นต่ำของผู้เล่น A สำหรับกลยุทธ์แบบผสมใดๆ ของเขา จุด N ซึ่งการได้รับขั้นต่ำนี้ถึงจุดสูงสุด จะกำหนดการตัดสินใจและราคาของเกม ง่ายต่อการตรวจสอบว่าพิกัดของจุด N คือราคาของเกม ν และ abscissa ของมันเท่ากับ p 2 - ความถี่ของการใช้กลยุทธ์ A 2 ในกลยุทธ์ผสมที่เหมาะสม S A *

ในกรณีของเรา การตัดสินใจของเกมถูกกำหนดโดยจุดตัดของกลยุทธ์ อย่างไรก็ตาม มันจะไม่เป็นเช่นนั้นเสมอไป ในรูป 4.3 แสดงกรณีที่แม้ว่าจะมีจุดตัดของกลยุทธ์ แต่วิธีแก้ปัญหาให้กลยุทธ์ที่บริสุทธิ์สำหรับผู้เล่นทั้งสอง (A 2 และ B 2) และราคาของเกม ν = a 22 ในกรณีนี้ เมทริกซ์มีจุดอาน และกลยุทธ์ A 1 นั้นไม่ได้ประโยชน์อย่างเห็นได้ชัด เนื่องจาก สำหรับกลยุทธ์ที่บริสุทธิ์ใดๆ ของปฏิปักษ์ มันให้ผลกำไรน้อยกว่า A2

ในกรณีที่ฝ่ายตรงข้ามมีกลยุทธ์ที่ไม่เอื้ออำนวยโดยเจตนา การตีความทางเรขาคณิตมีรูปแบบที่แสดงในรูปที่ 4.4.

ในกรณีนี้ ขอบเขตล่างของผลตอบแทนจะสอดคล้องกับกลยุทธ์ B 1 กลยุทธ์ B 2 นั้นไม่มีประโยชน์สำหรับคู่ต่อสู้อย่างเห็นได้ชัด

การตีความทางเรขาคณิตทำให้สามารถเห็นภาพราคาที่ต่ำกว่าและด้านบนของเกม (รูปที่ 4.5)

เพื่อแสดงให้เห็น เราสร้างการตีความทางเรขาคณิตของเกม 2 × 2 ที่พิจารณาในตัวอย่างที่ 1 และ 2 (รูปที่ 4.6 และ 4.7)

เราได้ทำให้แน่ใจว่าเกม 2 × 2 ใด ๆ สามารถแก้ไขได้ด้วยลูกเล่นเบื้องต้น เกม 2xn ใด ๆ สามารถแก้ไขได้ในลักษณะเดียวกันทุกประการ ที่เรามีเพียงสองกลยุทธ์และศัตรูมีหมายเลขโดยพลการ

สมมติว่าเรามีสองกลยุทธ์: А 1, А 2 และศัตรู - n กลยุทธ์: В 1, В 2, ..., В n. กำหนดเมทริกซ์ ‖a ij ‖ ประกอบด้วยสองแถวและ n คอลัมน์ ในทำนองเดียวกันกับกรณีของสองกลยุทธ์ เราให้ปัญหาด้วยการตีความทางเรขาคณิต n กลยุทธ์ของฝ่ายตรงข้ามจะแสดงด้วย n เส้นตรง (รูปที่ 4.8) เราสร้างขอบเขตล่างของเงินที่ชนะ (เส้นหัก B 1 MNB 2) และหาจุด N ด้วยพิกัดสูงสุด จุดนี้ให้คำตอบกับเกม (กลยุทธ์ ) พิกัดของจุด N เท่ากับราคาของเกม ν และ abscissa เท่ากับความถี่ p 2 ของกลยุทธ์ A 2

ในกรณีนี้ กลยุทธ์ที่ดีที่สุดของฝ่ายตรงข้ามได้มาจากการใช้กลยุทธ์ที่ "มีประโยชน์" สองแบบผสมกัน: B 2 และ B 4 ตัดกันที่จุด N กลยุทธ์ B 3 นั้นไม่ได้ผลกำไรอย่างเห็นได้ชัด และกลยุทธ์ B 1 นั้นไม่มีประโยชน์สำหรับกลยุทธ์ที่ดีที่สุด SA *. หาก A ยึดมั่นในกลยุทธ์ที่เหมาะสมที่สุด ผลตอบแทนจะไม่เปลี่ยนแปลง ไม่ว่ากลยุทธ์ที่ "มีประโยชน์" ของเขา B จะใช้อย่างไรก็ตาม มันจะเปลี่ยนไปหาก B เปลี่ยนไปใช้กลยุทธ์ B 1 หรือ B 3 ในทฤษฎีเกม ได้รับการพิสูจน์แล้วว่า mxn เกมจำกัดใดๆ มีวิธีแก้ปัญหาซึ่งจำนวนของกลยุทธ์ที่ "มีประโยชน์" ของทั้งสองฝ่ายไม่เกินตัวเลขอย่างน้อยสองตัว m และ n โดยเฉพาะอย่างยิ่ง จากนี้ไปเกม 2xm มักจะมีวิธีแก้ปัญหาซึ่งกลยุทธ์ "มีประโยชน์" ไม่เกินสองกลยุทธ์เข้าร่วมทั้งสองด้าน

การใช้การตีความทางเรขาคณิต เราสามารถให้วิธีง่ายๆ ในการแก้เกม 2xm ใดๆ จากรูปวาดโดยตรง เราพบกลยุทธ์ที่ "มีประโยชน์" ของคู่ต่อสู้ B j และ B k ซึ่งตัดกันที่จุด N (หากมีมากกว่าสองกลยุทธ์ตัดกันที่จุด N เราจะนำกลยุทธ์สองอันมาตัดกัน) เรารู้ว่าหากผู้เล่น A ปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุด ผลตอบแทนจะไม่ขึ้นอยู่กับสัดส่วนที่เขาใช้ B กับกลยุทธ์ที่ "มีประโยชน์" ของเขา ดังนั้น

จากสมการเหล่านี้และเงื่อนไข p 2 = 1 - p 1 เราพบ p1, p2 และราคาของเกม ν เมื่อทราบราคาเกมแล้ว คุณสามารถกำหนดกลยุทธ์ที่เหมาะสมได้ทันที ผู้เล่น B ตัวอย่างเช่น สำหรับสิ่งนี้ สมการถูกแก้: qja 1 j + qka 1 k = ν โดยที่ qj + qk = 1 ในกรณีที่เรามีกลยุทธ์ m และศัตรูมีเพียงสอง เห็นได้ชัดว่า ปัญหาได้รับการแก้ไขในลักษณะที่คล้ายกันอย่างสมบูรณ์ ; ก็เพียงพอแล้วที่จะสังเกตว่าการเปลี่ยนเครื่องหมายของการชนะไปเป็นแบบตรงกันข้าม สามารถเปลี่ยนผู้เล่น A จาก "ชนะ" เป็น "แพ้" ได้ คุณสามารถแก้เกมได้โดยไม่ต้องเปลี่ยนเครื่องหมายที่ชนะ จากนั้นปัญหาจะได้รับการแก้ไขโดยตรงสำหรับ B แต่ไม่ต่ำกว่า แต่มีการสร้างผลตอบแทนสูงสุด (รูปที่ 4.9) ที่ชายแดน จะหาจุด N ที่มีพิกัดขั้นต่ำ ซึ่งเป็นราคาเกม ν

พิจารณาและแก้ไขตัวอย่างต่างๆ ของเกม 2 × 2 และ 2xm ซึ่งเป็นตัวอย่างเกมแบบง่ายที่มีความสำคัญในทางปฏิบัติ

ตัวอย่างที่ 3ฝั่ง A ส่งเครื่องบินทิ้งระเบิดสองลำไปยังพื้นที่ศัตรู B ผมและ II; ผมบินอยู่ข้างหน้า, II- ข้างหลัง. หนึ่งในเครื่องบินทิ้งระเบิด - ไม่ทราบล่วงหน้าว่าอันไหน - จะต้องบรรทุกระเบิด อีกเครื่องหนึ่งทำหน้าที่เป็นผู้คุ้มกัน ในพื้นที่ของศัตรู เครื่องบินทิ้งระเบิดถูกโจมตีโดยเครื่องบินรบด้าน B เครื่องบินทิ้งระเบิดมีอาวุธปืนอัตราการยิงต่างๆ ถ้านักสู้โจมตีเครื่องบินทิ้งระเบิดด้านหลัง IIมีเพียงปืนใหญ่ของเครื่องบินทิ้งระเบิดเท่านั้นที่ยิงใส่มัน ถ้าเขาโจมตีเครื่องบินทิ้งระเบิดหน้า ปืนใหญ่ของเครื่องบินทิ้งระเบิดทั้งสองจะยิงใส่เขา ความน่าจะเป็นที่จะตีนักสู้ในกรณีแรกคือ 0.3 ใน 0.7 วินาทีที่สอง

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

a) สำหรับด้าน A: เครื่องบินทิ้งระเบิดชนิดใดควรใช้เป็นเรือบรรทุกเครื่องบิน?

b) สำหรับฝ่าย B: เครื่องบินทิ้งระเบิดตัวไหนที่จะโจมตี?

การตัดสินใจ เรามีกรณีง่าย ๆ ของเกม 2 × 2; ความน่าจะเป็นที่ชนะไม่ใช่ความพ่ายแพ้ของผู้ให้บริการ กลยุทธ์ของเรา: A 1 - เรือบรรทุกเครื่องบิน - เครื่องบินทิ้งระเบิด ผม; A 2 - ผู้ให้บริการ - เครื่องบินทิ้งระเบิด II... กลยุทธ์ของศัตรู: B 1 - เครื่องบินทิ้งระเบิดถูกโจมตี ผม; B 2 - เครื่องบินทิ้งระเบิดโจมตี II... มาเขียนเมทริกซ์ของเกมกัน นั่นคือ หาผลตอบแทนเฉลี่ยสำหรับกลยุทธ์แต่ละแบบรวมกัน

1.A 1 B 1 (ผู้ให้บริการ ผม, ถูกโจมตี ผม). สายการบินจะไม่ถูกโจมตีหากเครื่องบินทิ้งระเบิดยิงเครื่องบินขับไล่ตกหรือไม่ยิง แต่จะไม่โดนเป้าหมาย: 11 = 0.7 + 0.3 * 0.4 = 0.82

2.A 2 B 1 (ผู้ให้บริการ II, ถูกโจมตี ผม). 21 = 1

3.A 1 B 2 (ผู้ให้บริการ ผม, ถูกโจมตี II). A 12 = 1

4.A 2 B 2 (ผู้ให้บริการ II, ถูกโจมตี II). A 22 = 0.3 + 0.7 * 0.4 = 0.58

เมทริกซ์เกมมีรูปแบบ:

ราคาต่ำสุดของเกมคือ 0.82; ราคาสูงสุด 1. เมทริกซ์ไม่มีจุดอาน เรากำลังมองหาวิธีแก้ปัญหาในด้านกลยุทธ์แบบผสม เรามี:

p 1 * 0.82 + p 2 * 1 = ν

p 1 * 1 + p 2 * 0.58 = ν

หน้า 1 = 0.7; หน้า 2 = 0.3

กลยุทธ์ที่ดีที่สุดของเรา คือว่าในฐานะที่เป็นพาหะ คุณควรเลือกบ่อยขึ้น ผมกว่า II... ราคาของเกมคือ ν = 0.874 เมื่อทราบ ν เราจะกำหนด q 1 และ q 2 - ความถี่ของกลยุทธ์ B 1 และ B 2 ในกลยุทธ์ที่ดีที่สุดของศัตรู SB * เรามี: q 1 * 0.82 + q 2 * 1 = 0.874 และ q 2 = 1 - q 1 ดังนั้น q 1 = 0.7; q 2 = 0.3 นั่นคือกลยุทธ์ที่ดีที่สุดของคู่ต่อสู้คือ .

ตัวอย่างที่ 4ด้าน A โจมตีวัตถุ ด้าน B ปกป้องมัน ด้าน A มีระนาบสองระนาบ ฝ่าย B มีปืนต่อต้านอากาศยานสามกระบอก เครื่องบินแต่ละลำมีอาวุธทำลายล้างที่ทรงพลัง เพื่อให้วัตถุถูกกระแทก มันก็เพียงพอแล้วที่เครื่องบินอย่างน้อยหนึ่งลำจะทะลุผ่านเข้าไปได้ เครื่องบิน Side A สามารถเลือกทิศทางใดก็ได้จากสามทิศทางเพื่อเข้าใกล้สิ่งอำนวยความสะดวก: ผม, II, สาม(รูปที่ 4.10) ศัตรู (ด้าน B) สามารถวางปืนของเขาไปในทิศทางใดก็ได้ ในกรณีนี้ อาวุธแต่ละชนิดจะยิงเฉพาะพื้นที่ที่เกี่ยวข้องกับ ทิศทางนี้และไม่ยิงทิศทางเพื่อนบ้าน ปืนแต่ละกระบอกสามารถยิงได้บนเครื่องบินลำเดียวเท่านั้น เครื่องบินที่ยิงถูกยิงด้วยความน่าจะเป็น 1. ฝ่าย A ไม่รู้ว่าปืนอยู่ที่ไหน ฝ่าย B ไม่รู้ว่าเครื่องบินจะมาจากไหน งานของ Side A คือการตีวัตถุ หน้าที่ของฝ่าย B คือป้องกันความพ่ายแพ้ของเขา หาทางออกให้กับเกม

การตัดสินใจ เกมดังกล่าวเป็นเกม 2 × 3 ผลตอบแทนคือความน่าจะเป็นที่จะชนวัตถุ กลยุทธ์ที่เป็นไปได้ของเราคือ: A 1 - ส่งเครื่องบินครั้งละหนึ่งลำในสองทิศทางที่แตกต่างกัน และ 2 - ส่งเครื่องบินทั้งสองลำไปในทิศทางเดียวกัน กลยุทธ์ของศัตรู: B 1 - วางอาวุธหนึ่งชิ้นในแต่ละทิศทาง ใน 2 - วางปืนสองกระบอกในทิศทางเดียวและอีกด้านหนึ่ง ใน 3 - วางปืนทั้งสามกระบอกไปในทิศทางเดียวกัน เราแต่งเมทริกซ์ของเกม

1.A 1 B 1 (เครื่องบินบินตาม ทิศทางต่างๆ; ปืนถูกวางทีละนัด) เห็นได้ชัดว่าในกรณีนี้ ไม่มีระนาบเดียวที่จะทะลุผ่านไปยังวัตถุได้: a 11 = 0

2. А 2 В 1 (เครื่องบินบินไปด้วยกันในทิศทางเดียวกันโดยวางปืนทีละตัว) แน่นอน ในกรณีนี้ เครื่องบินหนึ่งลำจะผ่านไปยังวัตถุโดยไม่ทำการยิง: 21 = 1

3. А 1 В 2 (เครื่องบินบินทีละลำศัตรูปกป้องสองทิศทางและปล่อยให้เครื่องบินลำที่สามไม่มีการป้องกัน) ความน่าจะเป็นที่เครื่องบินอย่างน้อยหนึ่งลำจะทะลุผ่านไปยังวัตถุนั้นเท่ากับความน่าจะเป็นที่เครื่องบินลำหนึ่งจะเลือกทิศทางที่ไม่มีการป้องกัน: 12 = 2/3

4. А 2 В 2 (เครื่องบินบินไปด้วยกันในทิศทางเดียว ศัตรูป้องกันทิศทางเดียวด้วยปืนสองกระบอก และอีกกระบอกหนึ่งมีหนึ่งกระบอก นั่นคือ จริง ๆ แล้วปกป้องทิศทางเดียวและปล่อยให้สองลำไม่มีการป้องกัน ความน่าจะเป็นที่เครื่องบินอย่างน้อยหนึ่งลำจะทะลุผ่านไปยังวัตถุนั้นเท่ากับความน่าจะเป็นของระนาบคู่หนึ่งที่เลือกทิศทางที่ไม่มีการป้องกันจริงๆ: 22 = 2/3

5. A 1 B 3 (เครื่องบินบินทีละลำ ศัตรูป้องกันทิศทางเดียวด้วยปืนสามกระบอก): a 13 = 1

6. А 2 В 3 (เครื่องบินทั้งสองบินพร้อมกัน ศัตรูป้องกันทิศทางเดียวด้วยปืนสามกระบอก) สำหรับวัตถุที่จะโดน เครื่องบินจะต้องเลือกทิศทางที่ไม่มีการป้องกัน: 23 = 2/3

เกมเมทริกซ์:

จากเมทริกซ์จะเห็นได้ว่ากลยุทธ์ В 3 นั้นเสียเปรียบอย่างเห็นได้ชัดเมื่อเทียบกับ В 2 (สิ่งนี้สามารถแก้ไขได้ล่วงหน้า) ข้ามกลยุทธ์ ใน 3 เกมลดลงเป็น 2 × 2 เกม:

เมทริกซ์มีจุดอาน: ราคาต่ำสุดของเกม 2/3 เกิดขึ้นพร้อมกับราคาบน ในเวลาเดียวกัน เราสังเกตว่าสำหรับเรา (A) กลยุทธ์ A 1 นั้นไม่ได้ประโยชน์อย่างเห็นได้ชัด สรุป: ทั้งสองฝ่าย A และ B ควรใช้กลยุทธ์ที่บริสุทธิ์ A 2 และ B 2 เสมอ นั่นคือ เราต้องส่งเครื่องบินทีละ 2 ลำ สุ่มเลือกทิศทางที่จะส่งคู่ ฝ่ายตรงข้ามจะต้องวางอาวุธของเขาในลักษณะต่อไปนี้: สองทิศทางหนึ่งทิศทางและการเลือกทิศทางเหล่านี้จะต้องสุ่ม (ดังที่เราเห็นในที่นี้ "กลยุทธ์ที่บริสุทธิ์" รวมถึงองค์ประกอบของโอกาส) . การใช้กลยุทธ์ที่เหมาะสมที่สุดเหล่านี้ เราจะได้รับผลตอบแทนเฉลี่ยคงที่ที่ 2/3 เสมอ (เช่น วัตถุจะถูกโจมตีด้วยความน่าจะเป็น 2/3) โปรดทราบว่าวิธีแก้ปัญหาที่พบสำหรับเกมไม่ใช่วิธีเดียว นอกจากการตัดสินใจใน กลยุทธ์ที่สะอาดมีทั้งส่วนของกลยุทธ์ผสมของผู้เล่น A ซึ่งเหมาะสมที่สุดตั้งแต่ p 1 = 0 ถึง p 1 = 1/3 (รูปที่ 4.11)

เป็นเรื่องง่าย ตัวอย่างเช่น เพื่อดูโดยตรงว่าจะได้รับผลตอบแทนเฉลี่ยเท่ากันที่ 2/3 หากเราใช้กลยุทธ์ A1 และ A2 ในสัดส่วน 1/3 และ 2/3

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

การตัดสินใจเรายังคงมีสองกลยุทธ์ที่เป็นไปได้: A 1 - ส่งเครื่องบินทีละลำ, A 2 - ส่งเครื่องบินสองลำด้วยกัน ศัตรูมีห้ากลยุทธ์ที่เป็นไปได้: B 1 - วางอาวุธหนึ่งชิ้นในแต่ละทิศทาง ใน 2 - วางปืนสองกระบอกในสองทิศทางที่ต่างกัน ใน 3 - วางปืนสองกระบอกในทิศทางเดียวและทีละปืนอีกสองกระบอก ที่ 4 วางปืนสามกระบอกในทิศทางเดียวและอีกด้านหนึ่ง ที่ 5 - วางปืนทั้งสี่กระบอกไปในทิศทางเดียวกัน กลยุทธ์ B 4, B 5 จะถูกยกเลิกล่วงหน้าเนื่องจากไม่ได้ประโยชน์อย่างเห็นได้ชัด การให้เหตุผลคล้ายกับตัวอย่างก่อนหน้านี้ เราสร้างเมทริกซ์ของเกม:

ราคาเกมที่ต่ำกว่าคือ 1/2 ตัวบนคือ 3/4 เมทริกซ์ไม่มีจุดอาน การแก้ปัญหาอยู่ในพื้นที่ของกลยุทธ์แบบผสม ใช้การตีความทางเรขาคณิต (รูปที่ 4.12) ให้เราแยกแยะกลยุทธ์ที่ "มีประโยชน์" ของศัตรู: B 1 และ B 2

ความถี่ p 1 และ p 2 ถูกกำหนดจากสมการ: p 1 * 0 + (1 - p 1) * 1 = ν และ p 1 * 5/6 + (1 - p 1) * 1/2 = ν; โดยที่ p 1 = 3/8; หน้า 2 = 5/8; ν = 5/8 นั่นคือ กลยุทธ์ที่ดีที่สุดของเราคือ ... เมื่อใช้มัน เรารับประกันว่าตัวเองจะได้รับเงินรางวัลเฉลี่ย 5/8 เมื่อทราบราคาของเกม ν = 5/8 เราจะพบความถี่ q 1 และ q 2 ของกลยุทธ์ที่ "มีประโยชน์" ของคู่ต่อสู้: q 1 * 0 + (1 - q 1) * 5/6 = 5/8, q 1 = ¼, q 2 = ¾ กลยุทธ์ที่ดีที่สุดของศัตรูคือ: .

ตัวอย่างที่ 6ด้าน A มีสองกลยุทธ์ A 1 และ A 2 ด้าน B มีสี่ B 1, B 2, B 3 และ B 4 เมทริกซ์เกมมีรูปแบบ:

หาทางออกให้กับเกม

การตัดสินใจ ราคาเกมที่ต่ำกว่า 3; top 4 การตีความทางเรขาคณิต (รูปที่ 4.13) แสดงให้เห็นว่ากลยุทธ์ที่เป็นประโยชน์ของผู้เล่น B คือ B 1 และ B 2 หรือ B 2 และ B 4:

ผู้เล่น A มีกลยุทธ์ผสมที่ดีที่สุดมากมาย: ในกลยุทธ์ที่เหมาะสมที่สุด p 1 สามารถเปลี่ยนแปลงได้ตั้งแต่ 1/5 ถึง 4/5 ราคาของเกม ν = 4 ผู้เล่น B มีกลยุทธ์ที่เหมาะสมที่สุด B 2

§ 5. วิธีการทั่วไปในการแก้เกมจำกัด

จนถึงตอนนี้ เราได้พิจารณาเฉพาะเกมพื้นฐานที่สุดของประเภท 2xn ซึ่งสามารถแก้ไขได้ง่ายมาก และให้การตีความทางเรขาคณิตที่สะดวกและใช้งานง่าย ในกรณีทั่วไป การแก้ปัญหาเกม mxn เป็นปัญหาที่ค่อนข้างยาก และความซับซ้อนของปัญหาและจำนวนการคำนวณที่จำเป็นในการแก้ปัญหานั้นเพิ่มขึ้นอย่างมากเมื่อเพิ่ม m และ n อย่างไรก็ตาม ปัญหาเหล่านี้ไม่ได้มีลักษณะพื้นฐานและเกี่ยวข้องกับการคำนวณจำนวนมากเท่านั้น ซึ่งในบางกรณีอาจกลายเป็นสิ่งที่ทำไม่ได้ในทางปฏิบัติ ลักษณะพื้นฐานของวิธีการในการค้นหาวิธีแก้ปัญหายังคงเหมือนเดิมสำหรับ m ใดๆ

มาอธิบายเรื่องนี้ด้วยตัวอย่างเกม 3xn ให้การตีความทางเรขาคณิต - แล้วเป็นเชิงพื้นที่ สามกลยุทธ์ A 1, A 2 และ A 3 ของเราจะแสดงด้วยสามจุดบนเครื่องบิน เฮ้; ครั้งแรกอยู่ที่จุดกำเนิด (รูปที่ 5.1) ที่สองและสาม - บนแกน โอ้และ OUที่ระยะ 1 จากจุดเริ่มต้น

ขวานลากผ่านจุด A 1, A 2 และ A 3 ผม – ผม, II – IIและ สาม – สามตั้งฉากกับระนาบ เฮ้... บนแกน ผม – ผมกำไรจะถูกฝากไว้กับกลยุทธ์ A 1 บนแกน II – IIและ สาม – สาม- ชนะด้วยกลยุทธ์ A 2, A 3 แต่ละกลยุทธ์ของศัตรู B j นั้นแสดงโดยเครื่องบินที่ตัดบนแกน ผม – ผม, II – IIและ สาม – สามกลุ่มที่เท่ากับผลตอบแทนสำหรับกลยุทธ์ที่เกี่ยวข้อง A 1, A 2 และ A 3 และกลยุทธ์ B j เมื่อสร้างกลยุทธ์ทั้งหมดของศัตรูแล้ว เราก็ได้เครื่องบินแบบครอบครัวเหนือสามเหลี่ยม A 1, A 2 และ A 3 (รูปที่ 5.2) สำหรับตระกูลนี้ คุณยังสามารถสร้างขอบเขตผลตอบแทนที่ต่ำกว่า ดังที่เราทำในกรณี 2xn และหาที่จุดขอบเขต N ที่มีความสูงสูงสุดเหนือระนาบ เฮ้... ความสูงนี้จะเป็นต้นทุนของเกม ν

ความถี่ p 1, p 2, p 3 ของกลยุทธ์ A 1, A 2 และ A 3 ในกลยุทธ์ที่เหมาะสม SA * จะถูกกำหนดโดยพิกัด (x, y) ของจุด N คือ: p 2 = x, p 3 = y, p 1 = 1 - p 2 - p 3 อย่างไรก็ตาม โครงสร้างทางเรขาคณิตดังกล่าว แม้กระทั่งสำหรับเคส 3xn นั้นไม่ง่ายที่จะนำไปใช้และต้องใช้เวลาและความพยายามอย่างมากในจินตนาการ อย่างไรก็ตาม ในกรณีทั่วไปของเกม มันจะถูกถ่ายโอนไปยังพื้นที่มิติ m และสูญเสียความชัดเจนทั้งหมด แม้ว่าการใช้คำศัพท์ทางเรขาคณิตในหลายกรณีอาจกลายเป็นประโยชน์ เมื่อแก้เกม mxn ในทางปฏิบัติจะสะดวกกว่าที่จะใช้ไม่ใช่การเปรียบเทียบทางเรขาคณิต แต่เป็นวิธีวิเคราะห์เชิงคำนวณ โดยเฉพาะอย่างยิ่งเนื่องจากวิธีการเหล่านี้เป็นวิธีเดียวที่เหมาะสำหรับการแก้ปัญหาบนคอมพิวเตอร์

วิธีการทั้งหมดเหล่านี้มีผลอย่างยิ่งต่อการแก้ปัญหาโดยการทดลองต่อเนื่องกัน แต่การจัดลำดับการทดลองช่วยให้คุณสามารถสร้างอัลกอริทึมที่นำไปสู่การแก้ปัญหาด้วยวิธีที่ประหยัดที่สุด ในที่นี้เราจะพูดถึงวิธีการคำนวณหนึ่งวิธีในการแก้เกม mxn สั้นๆ ซึ่งเรียกว่าวิธี "การเขียนโปรแกรมเชิงเส้น" สำหรับสิ่งนี้ อันดับแรกเราให้คำชี้แจงทั่วไปเกี่ยวกับปัญหาในการค้นหาวิธีแก้ปัญหาของเกม mxn ให้เกม mxn กับ m กลยุทธ์ A 1, A 2,…, A m ของผู้เล่น A และ n กลยุทธ์ B 1, B 2,…, B n ของผู้เล่น B ได้รับและให้เมทริกซ์ผลตอบแทน ‖a i j ‖ จำเป็นต้องหาวิธีแก้ปัญหาของเกมเช่น สองกลยุทธ์ผสมที่ดีที่สุดของผู้เล่น A และ B

โดยที่ p 1 + p 2 + ... + p m = 1; q 1 + q 2 +… + q n = 1 (ตัวเลขบางตัว p i และ q j อาจเท่ากับศูนย์)

กลยุทธ์ที่ดีที่สุดของเรา S A * ควรให้ผลตอบแทนแก่เราไม่น้อยกว่า ν สำหรับพฤติกรรมใดๆ ของฝ่ายตรงข้าม และผลตอบแทนเท่ากับ ν สำหรับพฤติกรรมที่เหมาะสมที่สุดของเขา (กลยุทธ์ SB *) ในทำนองเดียวกัน กลยุทธ์ SB * ต้องให้คู่ต่อสู้สูญเสียไม่เกิน ν สำหรับพฤติกรรมใดๆ ของเรา และเท่ากับ ν สำหรับพฤติกรรมที่เหมาะสมที่สุดของเรา (กลยุทธ์ S A *)

มูลค่าของราคาของเกม ν ในกรณีนี้ไม่เป็นที่รู้จักสำหรับเรา เราจะถือว่ามีค่าเท่ากับบางส่วน จำนวนบวก... โดยเชื่อเช่นนั้น เราไม่ละเมิดหลักการทั่วไปของการให้เหตุผล สำหรับ ν> 0 เห็นได้ชัดว่าองค์ประกอบทั้งหมดของเมทริกซ์ ‖a i j ‖ ไม่เป็นค่าลบ สิ่งนี้สามารถทำได้โดยการเพิ่มองค์ประกอบ ‖a i j ‖ ค่าบวกที่มีขนาดใหญ่เพียงพอ หลี่; ในขณะที่ราคาของเกมจะเพิ่มขึ้นโดย หลี่และการตัดสินใจจะไม่เปลี่ยนแปลง

สมมติว่าเราได้เลือกกลยุทธ์ที่เหมาะสมที่สุดของเรา S A * จากนั้นผลตอบแทนเฉลี่ยของเราด้วยกลยุทธ์ของคู่ต่อสู้ B j จะเป็น: a j = p 1 a 1j + p 2 a 2j +… + p m a mj กลยุทธ์ที่ดีที่สุดของเรา SA * มีคุณสมบัติที่สำหรับพฤติกรรมใดๆ ของปฏิปักษ์ จะให้ผลตอบแทนไม่น้อยกว่า ν; ดังนั้น ตัวเลข a j ต้องไม่น้อยกว่า ν เราได้รับเงื่อนไขหลายประการ:

เราหารอสมการ (5.1) ด้วยค่าบวก ν และแสดง

จากนั้นเงื่อนไข (5.1) สามารถเขียนได้ในรูปแบบ

โดยที่ ξ 1, ξ 2,…, ξ m เป็นจำนวนที่ไม่ใช่ค่าลบ ตั้งแต่ р 1 + p 2 +… + p m = 1 ดังนั้นปริมาณ ξ 1, ξ 2,…, ξ m เป็นไปตามเงื่อนไข

(5.3) ξ 1 + ξ 2 +… + ξ m = 1 / ν.

เราต้องการรับประกันการชนะของเราให้ได้มากที่สุด ในเวลาเดียวกัน ส่วนขวาความเท่าเทียมกัน (5.3) ใช้ค่าต่ำสุด ดังนั้นปัญหาในการหาวิธีแก้ปัญหาของเกมจึงลดลงเป็นปัญหาทางคณิตศาสตร์ต่อไปนี้: กำหนดค่าที่ไม่เป็นลบ ξ 1, ξ 2,…, ξ m เงื่อนไขที่น่าพอใจ (5.2) เพื่อให้ผลรวม Φ = ξ 1 + ξ 2 +… + ξ m น้อยที่สุด

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

ในการแก้ปัญหาดังกล่าว ซึ่งพบได้ทั่วไปในทางปฏิบัติ ได้มีการพัฒนาเครื่องมือโปรแกรมเชิงเส้นตรงพิเศษในวิชาคณิตศาสตร์ ปัญหาการเขียนโปรแกรมเชิงเส้นมีดังนี้ ให้ระบบสมการเชิงเส้น:

จำเป็นต้องค้นหาค่าที่ไม่เป็นลบของปริมาณ ξ 1, ξ 2,…, ξ m เงื่อนไขที่น่าพอใจ (5.4) และในขณะเดียวกันก็ลดฟังก์ชันเชิงเส้นที่เป็นเนื้อเดียวกันของปริมาณ ξ 1, ξ 2,…, ξ ม. (รูปแบบเชิงเส้น): Φ = c 1 ξ 1 + c 2 ξ 2 +… + ซม. ξ ม.

เป็นการง่ายที่จะตรวจสอบว่าปัญหาข้างต้นของทฤษฎีเกมเป็นกรณีพิเศษของปัญหาการโปรแกรมเชิงเส้นตรงสำหรับ c 1 = c 2 =… = cm = 1 เมื่อมองแวบแรก อาจดูเหมือนว่าเงื่อนไข (5.2) จะไม่เท่ากับ เงื่อนไข (5.4) เนื่องจากแทนที่จะเป็นเครื่องหมายเท่ากับ พวกเขามีเครื่องหมายอสมการ อย่างไรก็ตาม มันง่ายที่จะกำจัดเครื่องหมายอสมการโดยการแนะนำตัวแปรที่ไม่เป็นลบที่สมมติขึ้นใหม่ z 1, z 2,…, z n และเงื่อนไขการเขียน (5.2) ในรูปแบบ:

รูปแบบ Φ ที่ต้องย่อให้เล็กสุดคือ Φ = ξ 1 + ξ 2 +… + ξ ม. เครื่องมือโปรแกรมเชิงเส้นตรงทำให้สามารถเลือกค่า ξ 1, ξ 2,…, ξ m ที่ตรงตามข้อกำหนดที่ระบุไว้โดยใช้ตัวอย่างตามลำดับจำนวนที่ค่อนข้างน้อย เพื่อความชัดเจนยิ่งขึ้น เราจะสาธิตการใช้อุปกรณ์นี้โดยตรงบนเนื้อหาในการแก้ปัญหาเกมเฉพาะ

ตัวอย่างที่ 1จำเป็นต้องค้นหาวิธีแก้ปัญหาของเกม 3 × 3 ที่ระบุในตัวอย่างที่ 2 § 1 ด้วยเมทริกซ์:

ในการทำให้ ij ไม่เป็นค่าลบ เราเพิ่มองค์ประกอบทั้งหมดของเมทริกซ์ L = 5 เราได้รับเมทริกซ์:

ในกรณีนี้ราคาของเกมจะเพิ่มขึ้น 5 และการตัดสินใจจะไม่เปลี่ยนแปลง

ให้เรากำหนดกลยุทธ์ที่เหมาะสม S A * เงื่อนไข (5.2) มีรูปแบบดังนี้

โดยที่ ξ 1 = p 1 / ν, ξ 2 = p 2 / ν, ξ 3 = p 3 / ν เพื่อกำจัดเครื่องหมายอสมการ เราแนะนำตัวแปรจำลอง z 1, z 2, z 3; เงื่อนไข (5.6) จะถูกเขียนในรูปแบบ:

รูปแบบเชิงเส้น Φ มีรูปแบบ: Φ = ξ 1 + ξ 2 + ξ 3 และควรทำให้เล็กที่สุด หากกลยุทธ์ B ทั้งสาม "มีประโยชน์" ตัวแปรจำลองทั้งสามตัว z 1, z 2, z 3 จะหายไป (นั่นคือ ผลตอบแทนเท่ากับราคาเกม ν สำหรับแต่ละกลยุทธ์ B j) แต่เรายังคงไม่มีเหตุผลที่จะพูดว่าทั้งสามกลยุทธ์ "มีประโยชน์" ในการตรวจสอบนี้ เราจะพยายามแสดงรูปแบบ Φ ในแง่ของตัวแปรจำลอง z 1, z 2, z 3 และดูว่าเราจะบรรลุผลสำเร็จหรือไม่ โดยถือว่ามีค่าเท่ากับศูนย์ ซึ่งเป็นค่าต่ำสุดของแบบฟอร์ม ในการทำเช่นนี้ เราแก้สมการ (5.7) เทียบกับตัวแปร ξ 1, ξ 2, ξ 3 (เช่น เราแสดง ξ 1, ξ 2, ξ 3 ในรูปของตัวแปรจำลอง z 1, z 2, z 3 ):

บวก ξ 1, ξ 2, ξ 3 เราจะได้: Φ = 1/5 + z 1/20 + z 2/10 + z 3/20 ที่นี่สัมประสิทธิ์สำหรับ z ทั้งหมดเป็นบวก ดังนั้น การเพิ่มขึ้นใดๆ ใน z 1, z 2, z 3 ที่สูงกว่าศูนย์จะนำไปสู่การเพิ่มขึ้นในรูปแบบ Φ เท่านั้น และเราต้องการให้ค่าน้อยที่สุด ดังนั้นค่า z 1, z 2, z 3 ที่ทำให้รูปแบบ Φ เป็นค่าต่ำสุดคือ z 1 = z 2 = z 3 = 0 ดังนั้น ค่าต่ำสุดของรูปแบบ Φ คือ: 1 / ν = 1 /5 ดังนั้นราคาของเกม ν = 5. แทนค่าศูนย์ z 1, z 2, z 3 ในสูตร (5.8) เราพบว่า: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20 หรือคูณด้วย ν, p 1 = 1/4, p 2 = 1/2, p 3 = 1/4 ดังนั้นจึงพบกลยุทธ์ที่เหมาะสมที่สุด A: กล่าวคือ เราควรเขียนเลข 1 ในหนึ่งในสี่ของทุกกรณี 2 ในครึ่งของคดี และ 3 ในไตรมาสที่เหลือของคดี

รู้ราคาเกม ν = 5 เป็นไปได้ที่จะหากลยุทธ์ที่ดีที่สุดของคู่ต่อสู้โดยใช้วิธีการที่รู้จักกันแล้ว ... ในการทำเช่นนี้ เราจะใช้สองกลยุทธ์ที่ "มีประโยชน์" ของเรา (เช่น A 2 และ A 3) และเขียนสมการ:

9q 1 + 11 (1-q 2 -q 1) = 5,

โดยที่ q 1 = q3 = 1/4; q 2 = 1/2 กลยุทธ์ที่ดีที่สุดของศัตรูจะเหมือนกับกลยุทธ์ของเรา: ... ตอนนี้ขอกลับไปที่เกมเดิม (ไม่แปลงร่าง) เมื่อต้องการทำเช่นนี้ จำเป็นต้องลบค่า L = 5 ที่เพิ่มไปยังองค์ประกอบเมทริกซ์จากราคาเกม ν = 5 เท่านั้น เราได้รับราคาของเกมดั้งเดิม v 0 = 0 ดังนั้นกลยุทธ์ที่ดีที่สุดของทั้งสองฝ่ายให้ผลตอบแทนเฉลี่ยเท่ากับศูนย์ เกมดังกล่าวมีประโยชน์หรือเสียเปรียบทั้งสองฝ่ายเท่ากัน

ตัวอย่างที่ 2สปอร์ตคลับ A มีสามตัวเลือกสำหรับองค์ประกอบของทีม A 1, A 2 และ A 3 Club B - ในสามรูปแบบ B 1, B 2 และ B 3 เมื่อสมัครเข้าร่วมการแข่งขัน ไม่มีสโมสรใดรู้ว่าคู่ต่อสู้จะเลือกผู้เล่นตัวจริงรายใด ความน่าจะเป็นของสโมสร A ที่ชนะภายใต้รายชื่อผู้เล่นตัวจริงต่างๆ ซึ่งทราบโดยคร่าวจากประสบการณ์การประชุมที่ผ่านมานั้นมาจากเมทริกซ์:

ค้นหาว่าสโมสรควรเล่นแต่ละทีมบ่อยเพียงใดเพื่อให้ได้จำนวนชัยชนะโดยเฉลี่ยสูงสุด

การตัดสินใจ ราคาที่ต่ำกว่าของเกมคือ 0.4; 0.6 อันดับแรก; เรากำลังมองหาวิธีแก้ปัญหาในด้านกลยุทธ์แบบผสม เพื่อไม่ให้จัดการกับเศษส่วน เราคูณองค์ประกอบทั้งหมดของเมทริกซ์ด้วย 10; ในกรณีนี้ราคาของเกมจะเพิ่มขึ้น 10 เท่าและการตัดสินใจจะไม่เปลี่ยนแปลง เราได้รับเมทริกซ์:

เงื่อนไข (5.5) มีรูปแบบดังนี้

และเงื่อนไขขั้นต่ำ Φ = ξ 1 + ξ 2 + ξ 3 = นาที

ตรวจสอบว่าทั้งสามกลยุทธ์ของคู่ต่อสู้ "มีประโยชน์" หรือไม่ ตามสมมติฐาน อันดับแรก เราคิดว่าตัวแปรจำลอง z 1, z 2, z 3 มีค่าเท่ากับศูนย์ และสำหรับการตรวจสอบ เราจะแก้สมการ (5.10) สำหรับ ξ 1, ξ 2, ξ 3:

(5.12) 136Φ = 30 + 13z 1 + 18z 2 - 51z 3

สูตร (5.12) แสดงให้เห็นว่าการเพิ่มขึ้นของตัวแปร z 1 และ z 2 เมื่อเปรียบเทียบกับค่าที่สันนิษฐานว่าเป็นศูนย์ สามารถเพิ่มได้เพียง Φ ในขณะที่การเพิ่ม z 3 สามารถลด Φ ได้ อย่างไรก็ตาม การเพิ่มขึ้นของ z 3 ต้องทำอย่างระมัดระวังเพื่อไม่ให้ค่า ξ 1, ξ 2, ξ 3 ขึ้นอยู่กับ z 3 กลายเป็นค่าลบในกรณีนี้ ดังนั้นทางด้านขวามือของความเท่าเทียมกัน (5.11) เราใส่ค่า z 1 และ z 2 เท่ากับศูนย์ และเราจะเพิ่มค่า z 3 เป็นขีดจำกัดที่ยอมรับได้ (จนกว่าจะมีค่าใด ๆ ξ 1, ξ 2, ξ 3 หายไป) จากความเท่าเทียมกันที่สองใน (5.11) จะเห็นได้ว่าการเพิ่มขึ้นของ z 3 นั้น "ปลอดภัย" สำหรับค่า ξ 2 - เพิ่มขึ้นจากสิ่งนี้เท่านั้น สำหรับปริมาณ ξ 1 และ ξ 3 ในที่นี้ การเพิ่มขึ้นของ z 3 สามารถทำได้จนถึงขีดจำกัดที่แน่นอนเท่านั้น ปริมาณ ξ 1 หายไปที่ z 3 = 10/23; ปริมาณ ξ 3 หายไปก่อนหน้านี้แล้วที่ z 3 = 1/4 ดังนั้น เมื่อให้ z 3 มีค่าสูงสุดที่อนุญาต z 3 = 1/4 เราจะให้ค่า ξ 3 เป็นศูนย์

เพื่อตรวจสอบว่ารูปแบบ Φ กลายเป็นค่าต่ำสุดที่ z 1 = 0, z 2 = 0, ξ 3 = 0 หรือไม่ เราแสดงตัวแปรที่เหลือ (ไม่ใช่ศูนย์) ในรูปของศูนย์ z 1, z 2, ξ 3 ที่คาดคะเน การแก้สมการ (5.10) เทียบกับ ξ 1, ξ 2 และ z 3 เราได้รับ:

(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3

จากสูตร (5.13) จะเห็นได้ว่าการเพิ่มขึ้นใดๆ ใน z 1, z 2, over 3 จากค่าศูนย์ที่สันนิษฐานไว้ จะเพิ่มรูปร่างของ Φ ได้เท่านั้น ดังนั้นจึงพบวิธีแก้ปัญหาของเกม มันถูกกำหนดโดยค่า z 1 = z 2 = ξ 3 = 0, ดังนั้น ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4 แทนสูตร (5.13) เราพบราคาของเกม ν: 32Φ = 7 = 32 / ν; ν = 32/7. กลยุทธ์ที่เหมาะสมที่สุดของเรา: ... ควรใช้กลยุทธ์ "มีประโยชน์" (องค์ประกอบ A 1 และ A 2) ที่ความถี่ 1/7 และ 6/7 องค์ประกอบ A 3 - ไม่เคยใช้

ในการค้นหากลยุทธ์ที่ดีที่สุดของฝ่ายตรงข้าม ในกรณีทั่วไป คุณสามารถทำสิ่งต่อไปนี้: เปลี่ยนเครื่องหมายของผลตอบแทนเป็นตรงกันข้าม เพิ่มค่าคงที่ L ให้กับองค์ประกอบของเมทริกซ์เพื่อทำให้ไม่เป็นลบ และแก้ ปัญหาของปฏิปักษ์ในลักษณะเดียวกับที่เราแก้ไขด้วยตนเอง อย่างไรก็ตาม ความจริงที่ว่าเราทราบราคาของเกม ν อยู่แล้ว ทำให้ปัญหาง่ายขึ้น นอกจากนี้ในเรื่องนี้ เฉพาะกรณีงานนี้ง่ายขึ้นด้วยความจริงที่ว่ามีเพียงสองกลยุทธ์ที่ "มีประโยชน์" ของฝ่ายตรงข้าม B 1 และ B 2 มีส่วนร่วมในการแก้ปัญหาเนื่องจากค่าของ z 3 ไม่เป็นศูนย์และด้วยกลยุทธ์ B 3 ราคาเกมไม่ถึง การเลือกกลยุทธ์ที่ "มีประโยชน์" ของผู้เล่น A เช่น A 1 สามารถค้นหาความถี่ q 1 และ q 2 ในการทำเช่นนี้ เราเขียนสมการ 8q 1 + 2 (1 - q 1) = 32/7 ดังนั้น q 1 = 3/7, q 2 = 4/7; กลยุทธ์ที่ดีที่สุดของศัตรูคือ: กล่าวคือ ศัตรูไม่ควรใช้องค์ประกอบ B 3 และควรใช้องค์ประกอบ B 1 และ B2 ด้วยความถี่ 3/7 และ 4/7

กลับไปที่เมทริกซ์ดั้งเดิม เรากำหนดค่าที่แท้จริงของเกม ν 0 = 32/7: 10 = 0.457 ซึ่งหมายความว่าสำหรับ จำนวนมากการประชุม จำนวนชัยชนะของคลับ A จะเท่ากับ 0.457 ของการประชุมทั้งหมด

§ 6. วิธีการโดยประมาณในการแก้เกม

บ่อยครั้งในปัญหาในทางปฏิบัติ ไม่จำเป็นต้องค้นหาวิธีแก้ปัญหาที่แน่นอนสำหรับเกม การหาวิธีแก้ปัญหาโดยประมาณที่ให้ผลตอบแทนเฉลี่ยใกล้เคียงกับราคาเกมก็เพียงพอแล้ว ความรู้โดยประมาณเกี่ยวกับมูลค่าของเกม ν สามารถให้ได้โดยการวิเคราะห์ง่ายๆ ของเมทริกซ์และการกำหนดราคาที่ต่ำกว่า (α) และบน (β) ของเกม หาก α และ β อยู่ใกล้กัน แทบไม่ต้องค้นหาวิธีแก้ปัญหาที่แน่นอน แต่การเลือกกลยุทธ์ขั้นต่ำสุดเพียงอย่างเดียวก็เพียงพอแล้ว ในกรณีที่ α และ β ไม่อยู่ใกล้กัน เราสามารถหาวิธีแก้ปัญหาที่ใช้งานได้จริงโดยใช้วิธีการเชิงตัวเลขในการแก้เกม ซึ่งเราจะเน้นย้ำถึงวิธีการวนซ้ำโดยสังเขป

แนวคิดเบื้องหลังวิธีการวนซ้ำมีดังนี้ มีการเล่น "การทดลองทางความคิด" โดยที่คู่ต่อสู้ A และ B ใช้กลยุทธ์ของพวกเขากันเอง การทดลองประกอบด้วยลำดับของเกมระดับประถมศึกษา ซึ่งแต่ละเกมมีเมทริกซ์ของเกมที่กำหนด เริ่มต้นด้วยการที่เรา (ผู้เล่น A) เลือกหนึ่งในกลยุทธ์ของเราโดยพลการ เช่น A i ศัตรูตอบสนองต่อสิ่งนี้ด้วยกลยุทธ์ของเขา B j ซึ่งมีประโยชน์น้อยที่สุดสำหรับเรานั่นคือ เปลี่ยนผลตอบแทนสำหรับกลยุทธ์ A i ให้เหลือน้อยที่สุด เราตอบสนองต่อการเคลื่อนไหวนี้ด้วยกลยุทธ์ А k ซึ่งให้ผลตอบแทนเฉลี่ยสูงสุดเมื่อฝ่ายตรงข้ามใช้กลยุทธ์ B j ต่อไป - อีกครั้งของศัตรู เขาตอบสนองต่อการเคลื่อนไหวคู่ A i และ A k ด้วยกลยุทธ์ B j ซึ่งให้ผลตอบแทนเฉลี่ยน้อยที่สุดสำหรับกลยุทธ์ทั้งสองนี้ (A i, A k) และอื่นๆ ในแต่ละขั้นตอนของกระบวนการวนซ้ำ ผู้เล่นแต่ละคนตอบสนองต่อการเคลื่อนไหวใดๆ ของผู้เล่นอื่นด้วยกลยุทธ์ของตัวเองที่เหมาะสมที่สุดเมื่อเทียบกับการเคลื่อนไหวก่อนหน้าทั้งหมดของเขา ซึ่งถือเป็นกลยุทธ์แบบผสมบางประเภท ซึ่งกลยุทธ์ที่แท้จริงจะถูกนำเสนอในสัดส่วนที่สอดคล้องกับ ความถี่ในการสมัคร

วิธีการนี้เป็นแบบอย่างของ "การฝึก" ที่ใช้งานได้จริงของผู้เล่น เมื่อแต่ละคนสำรวจผ่านประสบการณ์วิธีที่คู่ต่อสู้ประพฤติตนและพยายามตอบสนองในลักษณะที่เป็นประโยชน์ต่อตัวเอง หากการเลียนแบบกระบวนการเรียนรู้นี้ดำเนินต่อไปนานพอ ผลตอบแทนเฉลี่ยต่อการเคลื่อนไหวหนึ่งคู่ (เกมระดับประถมศึกษา) จะมีแนวโน้มตามราคาของเกมและความถี่ p 1 ... p m; q 1 ... q n ซึ่งกลยุทธ์ของผู้เล่นพบในการชุมนุมนี้จะเข้าใกล้ความถี่ที่กำหนดกลยุทธ์ที่เหมาะสมที่สุด การคำนวณแสดงให้เห็นว่าการบรรจบกันของวิธีการนั้นช้ามาก แต่นี่ไม่ใช่อุปสรรคสำหรับเครื่องคำนวณความเร็วสูง

ให้เราอธิบายการใช้วิธีการวนซ้ำโดยใช้ตัวอย่างของเกม 3 × 3 ที่แก้ไขในตัวอย่างที่ 2 ของส่วนก่อนหน้า เกมดังกล่าวได้รับจากเมทริกซ์:

ตารางที่ 6.1 แสดง 18 ขั้นตอนแรกของกระบวนการวนซ้ำ คอลัมน์แรกมีจำนวนของเกมระดับประถมศึกษา (คู่ของการเคลื่อนไหว) น; ในวินาที - หมายเลข ผมกลยุทธ์ที่เลือกของผู้เล่น A; ในสามถัดไป - "เงินรางวัลสะสม" สำหรับคนแรก นเกมที่มีกลยุทธ์ของศัตรู B 1, B 2, B 3 ขีดเส้นใต้ค่าที่น้อยที่สุดเหล่านี้ ถัดมาเป็นเลข เจกลยุทธ์ที่ศัตรูเลือก และดังนั้น กำไรสะสมสำหรับ นเกมสำหรับกลยุทธ์ A 1, A 2, A 3 ของค่าเหล่านี้ ขีดเส้นใต้สูงสุดจากด้านบน ค่าที่ขีดเส้นใต้กำหนดทางเลือกของกลยุทธ์การตอบสนองของผู้เล่นคนอื่น กราฟต่อไปนี้แสดงตามลำดับ: ผลตอบแทนเฉลี่ยขั้นต่ำ ν เท่ากับผลตอบแทนสะสมขั้นต่ำหารด้วยจำนวนเกม น; เงินรางวัลเฉลี่ยสูงสุดเท่ากับเงินรางวัลสะสมสูงสุดหารด้วย นและค่าเฉลี่ยเลขคณิต ν * = (ν +) / 2 เมื่อเพิ่มขึ้น นปริมาณทั้งสาม ν และ ν * จะเข้าใกล้ราคาของเกม ν แต่ค่า ν * จะเข้าใกล้ราคาเร็วกว่าโดยธรรมชาติ

ตารางที่ 6.1.

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

§ 7. วิธีการแก้เกมที่ไม่มีที่สิ้นสุด

เกมที่ไม่มีที่สิ้นสุดเป็นเกมที่อย่างน้อยฝ่ายหนึ่งมีกลยุทธ์มากมาย วิธีการทั่วไปในการแก้เกมดังกล่าวยังไม่ได้รับการพัฒนาอย่างเพียงพอ อย่างไรก็ตาม ในทางปฏิบัติ บางกรณีพิเศษอาจเป็นเรื่องที่น่าสนใจ ซึ่งยอมรับวิธีแก้ปัญหาที่ค่อนข้างง่าย พิจารณาเกมของคู่ต่อสู้ A และ B สองคนซึ่งแต่ละเกมมีกลยุทธ์ที่ไม่มีที่สิ้นสุด (นับไม่ได้) กลยุทธ์เหล่านี้สำหรับผู้เล่น A สอดคล้องกับ ความหมายต่างกันพารามิเตอร์ที่เปลี่ยนแปลงอย่างต่อเนื่อง xและสำหรับ В - พารามิเตอร์ ที่... ในกรณีนี้ แทนที่จะเป็นเมทริกซ์ ‖a ij เกมถูกกำหนดโดยฟังก์ชันบางอย่างของสองอาร์กิวเมนต์ที่แตกต่างกันอย่างต่อเนื่อง ก (x, y)ซึ่งเราจะเรียกฟังก์ชัน payoff (โปรดทราบว่าฟังก์ชันนั้นเอง ก (x, y)ไม่ต้องต่อเนื่อง) ฟังก์ชันวิน ก (x, y)สามารถแสดงทางเรขาคณิตด้วยพื้นผิวบางส่วนได้ ก (x, y)เหนือขอบเขตของการเปลี่ยนแปลงข้อโต้แย้ง (x, y)(รูปที่ 7.1)

การวิเคราะห์ฟังก์ชันผลตอบแทน ก (x, y)ดำเนินการในลักษณะเดียวกับการวิเคราะห์เมทริกซ์การชำระเงิน ขั้นแรกพบราคาที่ต่ำกว่าของเกม α; สำหรับสิ่งนี้มันถูกกำหนดไว้สำหรับแต่ละคน xฟังก์ชั่นขั้นต่ำ minimum ก (x, y)สำหรับทุกอย่าง ที่: จากนั้นค่าสูงสุดของค่าเหล่านี้จะถูกค้นหาทั้งหมด x(สูงสุด):

ราคาสูงสุดของเกม (minimax) ถูกกำหนดในลักษณะเดียวกัน:

พิจารณากรณีที่ α = β เนื่องจากมูลค่าของเกม ν อยู่ระหว่าง α และ β เสมอ มูลค่ารวมของมันคือ ν ความเท่าเทียมกัน α = β หมายความว่าพื้นผิว ก (x, y)มีจุดอาน คือ จุดที่มีพิกัด x 0, y 0 ที่ ก (x, y)ในเวลาเดียวกันน้อยที่สุดใน ที่และสูงสุด x(รูปที่ 7.2)

ความคุ้มค่า ก (x, y)ณ จุดนี้เป็นราคาของเกม ν: ν = ก (x 0, y 0)การปรากฏตัวของจุดอานหมายความว่าเกมที่ไม่มีที่สิ้นสุดนี้มีโซลูชันกลยุทธ์ที่บริสุทธิ์ x 0, y 0แสดงถึงกลยุทธ์ที่บริสุทธิ์ที่สุด A และ B ในกรณีทั่วไป เมื่อ α ≠ β เกมมีวิธีแก้ปัญหาเฉพาะในด้านกลยุทธ์แบบผสม (อาจไม่ใช่กลยุทธ์เดียว) กลยุทธ์ผสมสำหรับเกมที่ไม่มีที่สิ้นสุด มีการแจกแจงความน่าจะเป็นสำหรับกลยุทธ์ต่างๆ xและ ที่ถือเป็นตัวแปรสุ่ม การกระจายนี้สามารถต่อเนื่องและกำหนดโดยความหนาแน่น ฉ 1 (x)และ ฉ 2 (ญ); แยกกันได้ จากนั้นกลยุทธ์ที่เหมาะสมจะประกอบด้วยชุดของกลยุทธ์ที่แยกจากกันซึ่งเลือกด้วยความน่าจะเป็นที่ไม่ใช่ศูนย์

ในกรณีที่เกมไม่มีที่สิ้นสุดไม่มีจุดอาน สามารถให้การตีความทางเรขาคณิตของราคาที่ต่ำกว่าและด้านบนของเกมได้ พิจารณาเกมที่ไม่มีที่สิ้นสุดด้วยฟังก์ชั่นการจ่ายเงิน ก (x, y)และกลยุทธิ์ x, yเติมส่วนของเส้นอย่างต่อเนื่อง (x 1, x 2)และ (ปี 1, ปี 2)... ในการกำหนดราคาที่ต่ำกว่าของเกม α คุณต้อง "ดู" ที่พื้นผิว ก (x, y)จากแกน ที่กล่าวคือ ฉายลงบนเครื่องบิน xOa(รูปที่ 7.3) เราได้ตัวเลขที่ล้อมรอบจากด้านข้างด้วยเส้นตรง x = x 1 และ x = x 2 และจากด้านบนและด้านล่างโดยเส้นโค้ง KB และ K N ราคาที่ต่ำกว่าของเกม α แน่นอนไม่มีอะไรมากไปกว่า พิกัดสูงสุดของเส้นโค้ง K N

ในทำนองเดียวกัน เพื่อหาราคาที่สูงกว่าของเกม β เราต้อง "ดู" ที่พื้นผิว ก (x, y)จากแกน x(พื้นผิวโครงการถึงระนาบ โย่) และหาพิกัดต่ำสุดของขอบบน K ในการฉายภาพ (รูปที่ 7.4)

พิจารณาสองตัวอย่างเบื้องต้นของเกมที่ไม่มีที่สิ้นสุด

ตัวอย่างที่ 1ผู้เล่น A และ B แต่ละคนมีชุดกลยุทธ์ที่เป็นไปได้ที่นับไม่ถ้วน xและ ที่และ 0 ≤ x ≤ 1; 0 ≤ y ≤ 1 ฟังก์ชันการจ่ายเงินสำหรับ a ถูกกำหนดโดยนิพจน์ a (x, y) - (x - y) 2 หาทางออกให้กับเกม

สารละลาย พื้นผิว a (x, y) เป็นทรงกระบอกพาราโบลา (รูปที่ 7.5) และไม่มีจุดอาน กำหนดราคาที่ต่ำกว่าของเกม ชัดเจนสำหรับทุกคน x; ดังนั้น = 0 ให้เรากำหนดราคาที่สูงกว่าของเกม ในการทำเช่นนี้เราพบว่ามีการแก้ไข ที่

ในกรณีนี้ จะบรรลุค่าสูงสุดที่ขอบเขตของช่วงเวลาเสมอ (ที่ x = 0 หรือ x = 1) เช่น เท่ากับค่าของ y 2; (1 - y) 2 ซึ่งใหญ่กว่า มาวาดกราฟของฟังก์ชันเหล่านี้กัน (รูปที่ 7.6) เช่น การฉายพื้นผิว ก (x, y)บนเครื่องบิน โย่... เส้นหนาตามรูป 7.6 แสดงฟังก์ชัน เห็นได้ชัดว่าค่าต่ำสุดอยู่ที่ y = 1/2 และเท่ากับ 1/4 ดังนั้นราคาสูงสุดของเกมคือ β = 1/4 ในกรณีนี้ ราคาสูงสุดของเกมจะตรงกับราคาของเกม ν อันที่จริง ผู้เล่น A สามารถใช้กลยุทธ์ผสม S A = ซึ่งค่าสุดขั้ว x = 0 และ x = 1 รวมอยู่ในความถี่เดียวกัน สำหรับกลยุทธ์ใดๆ ของผู้เล่น B ผลตอบแทนเฉลี่ยของผู้เล่น A จะเท่ากับ: ½y 2 + ½ (1 - y) 2 ง่ายต่อการตรวจสอบว่าปริมาณนี้สำหรับค่าใด ๆ ที่ระหว่าง 0 ถึง 1 มีค่าไม่น้อยกว่า ¼: ½y 2 + ½ (1 - y) 2 ≥ ¼

ดังนั้นผู้เล่น A โดยใช้กลยุทธ์แบบผสมนี้สามารถรับประกันได้ว่าตนเองจะได้รับผลตอบแทนเท่ากับราคาเกมบน เนื่องจากราคาของเกมไม่สามารถเกินราคาบนได้ดังนั้น กลยุทธ์นี้ S A เหมาะสมที่สุด: S A = S A *

มันยังคงต้องหากลยุทธ์ที่ดีที่สุดของผู้เล่น B เห็นได้ชัดว่าถ้าราคาของเกม ν เท่ากับราคาสูงสุดของเกม β กลยุทธ์ที่ดีที่สุดของผู้เล่น B จะเป็นกลยุทธ์ขั้นต่ำสุดที่แท้จริงของเขาเสมอ ซึ่งรับประกันได้ว่าเขาจะ ราคาสูงสุดของเกม ในกรณีนี้ กลยุทธ์ดังกล่าวคือ y 0 = ½ ด้วยกลยุทธ์นี้ ไม่ว่าผู้เล่น A จะทำอะไร ผลตอบแทนของเขาจะไม่เกิน ¼ สิ่งนี้ตามมาจากความไม่เท่าเทียมกันที่เห็นได้ชัด (x - ½) 2 = x (x –1) + ¼ ≤ ¼

ตัวอย่างที่ 2ฝ่าย A ("เรา") กำลังยิงเครื่องบินข้าศึก B เพื่อหลบเลี่ยงกระสุนปืน ศัตรูสามารถหลบหลีกด้วยการโอเวอร์โหลดบางส่วน ที่ซึ่งเขาสามารถแนบค่าจาก .ได้ตามดุลยพินิจของเขา ที่= 0 (เคลื่อนที่ตรง) ถึง ที่ = ที่max(บินเป็นวงกลมที่มีความโค้งสูงสุด) เราถือว่า ที่maxหน่วยวัด กล่าวคือ ใส่ ที่max= 1 ในการต่อสู้กับศัตรู เราสามารถใช้อุปกรณ์การเล็งโดยอิงจากสมมติฐานอย่างใดอย่างหนึ่งเกี่ยวกับการเคลื่อนที่ของเป้าหมายในระหว่างการบินของกระสุนปืน โอเวอร์โหลด xในการซ้อมรบสมมุติฐานนี้ สามารถสันนิษฐานได้ว่ามีค่าเท่ากับ 0 ถึง 1 ใดๆ หน้าที่ของเราคือโจมตีศัตรู หน้าที่ของศัตรูคือการไม่ได้รับผลกระทบ ความน่าจะเป็นของความเสียหายของข้อมูล xและ ที่ประมาณแสดงโดยสูตร: a (x, y) = , ที่ไหน ที่- โอเวอร์โหลดที่ศัตรูใช้ x - เกินพิกัดในสายตา จำเป็นต้องกำหนดกลยุทธ์ที่เหมาะสมของทั้งสองฝ่าย

การตัดสินใจ เห็นได้ชัดว่าการแก้ปัญหาของเกมไม่เปลี่ยนแปลงหากเราตั้งค่า p = 1 ฟังก์ชั่นการจ่ายเงิน ก (x, y)แสดงโดยพื้นผิวที่แสดงในรูปที่ 7.7.

นี่คือพื้นผิวทรงกระบอกที่มีเจเนอเรเตอร์ขนานกับเส้นแบ่งครึ่งของมุมพิกัด เฮ้และส่วนโดยระนาบตั้งฉากกับ generatrix เป็นเส้นโค้งประเภทเส้นโค้งการกระจายแบบปกติ โดยใช้การตีความทางเรขาคณิตของราคาที่ต่ำกว่าและด้านบนของเกมที่เสนอข้างต้น เราพบ β = 1 (รูปที่ 7.8) และ (รูปที่ 7.9) เกมดังกล่าวไม่มีจุดอาน จะต้องค้นหาวิธีแก้ปัญหาในพื้นที่ของกลยุทธ์แบบผสม ปัญหาค่อนข้างคล้ายกับปัญหาในตัวอย่างก่อนหน้านี้ แท้จริงแล้วสำหรับค่าเล็กน้อย kฟังก์ชั่นทำงานเหมือนฟังก์ชั่น - (x - y) 2และการแก้ปัญหาของเกมจะได้รับหากบทบาทของผู้เล่น A และ B เปลี่ยนไปในการแก้ปัญหาของตัวอย่างก่อนหน้านี้ เหล่านั้น กลยุทธ์ที่ดีที่สุดของเราคือกลยุทธ์ที่แท้จริง x = 1/2 และกลยุทธ์ที่ดีที่สุดของฝ่ายตรงข้าม SB = จะใช้กลยุทธ์ที่รุนแรงที่สุด y = 0 และ y = 1 ที่มีความถี่เท่ากัน ซึ่งหมายความว่าในทุกกรณีเราต้อง ใช้เป้าเล็งที่ออกแบบมาสำหรับโอเวอร์โหลด x = 1/2 และศัตรูไม่ควรใช้การหลบหลีกเลยในครึ่งของทุกกรณี และในครึ่งหลัง - เป็นการซ้อมรบสูงสุดที่เป็นไปได้

รูปที่. 7.8 รูปที่ 7.9.

เป็นเรื่องง่ายที่จะพิสูจน์ว่าโซลูชันนี้จะใช้ได้กับค่า k ≤ 2 อันที่จริงผลตอบแทนเฉลี่ยสำหรับกลยุทธ์ของฝ่ายตรงข้าม SB = และสำหรับกลยุทธ์ของเรา xแสดงโดยฟังก์ชัน , ซึ่งสำหรับค่า k ≤ 2 จะมีค่าสูงสุดที่ x = 1/2 ซึ่งเท่ากับราคาที่ต่ำกว่าของเกม α ดังนั้นการใช้กลยุทธ์ SB รับประกันความสูญเสียที่ไม่เกิน α ของคู่ต่อสู้ ซึ่งชัดเจนว่า α - ราคาที่ต่ำกว่าของเกม - คือราคาของเกม ν

สำหรับ k> 2 ฟังก์ชัน a (x) มีค่าสูงสุดสองค่า (รูปที่ 7.10) ซึ่งวางอย่างสมมาตรเทียบกับ x = 1/2 ที่จุด x 0 และ 1 - x 0 และค่าของ x 0 ขึ้นอยู่กับ k .

แน่นอนสำหรับ k= 2 x 0 = 1 - x 0 = ½; เมื่อเพิ่มขึ้น kจุด x 0 และ 1 - x 0 เคลื่อนออกจากกัน เข้าใกล้จุดสุดขั้ว (0 และ 1) มากขึ้น ดังนั้นการตัดสินใจของเกมจะขึ้นอยู่กับเค มาตั้งค่าเฉพาะสำหรับ k เช่น k = 3 และหาวิธีแก้ปัญหาของเกม สำหรับสิ่งนี้ เรากำหนด abscissa x 0 ของค่าสูงสุดของเส้นโค้ง a (x) เท่ากับศูนย์อนุพันธ์ของฟังก์ชัน a (x) เราเขียนสมการเพื่อหา x 0:

สมการนี้มีสามราก: x = 1/2 (เมื่อถึงค่าต่ำสุด) และ x 0, 1 - x 0 เมื่อถึงค่าสูงสุด การแก้สมการเชิงตัวเลข เราพบประมาณ x 0 ≈ 0.07; 1 - x 0 ≈ 0.93.

ให้เราพิสูจน์ว่าวิธีแก้ปัญหาของเกมในกรณีนี้คือกลยุทธ์คู่ต่อไปนี้:

ด้วยกลยุทธ์ของเราและกลยุทธ์ของศัตรู ที่ผลตอบแทนเฉลี่ยคือ

ค้นหาขั้นต่ำ 1 (y) ที่ 0< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

การตั้งค่า y = 1/2 เราได้

ซึ่งมากกว่า 1 (0); ดังนั้นราคาของเกมจึงไม่ต่ำกว่า 1 (0):

สมมุติว่าฝ่ายตรงข้ามใช้กลยุทธ์ SB * และเราใช้กลยุทธ์ x จากนั้นผลตอบแทนเฉลี่ยจะเป็น

แต่เราได้เลือก x 0 อย่างแน่นอนเพื่อให้ที่ x = x 0 ถึงสูงสุดของนิพจน์ (7.2) ดังนั้น

เหล่านั้น ฝ่ายตรงข้ามโดยใช้กลยุทธ์ SB * สามารถป้องกันการสูญเสียมากกว่า 0.530; ดังนั้น ν = 0.530 คือราคาของเกม และกลยุทธ์ S A * และ S B * ให้คำตอบ ซึ่งหมายความว่าเราต้องใช้สายตาที่มี x = 0.07 และ x = 0.93 ที่มีความถี่เท่ากัน และศัตรูจะต้องไม่เคลื่อนที่ด้วยความถี่เดียวกันและการหลบหลีกที่เกินพิกัดสูงสุด

โปรดทราบว่าผลตอบแทน ν = 0.530 นั้นสูงกว่าราคาที่ต่ำกว่าของเกมอย่างเห็นได้ชัด ซึ่งเราสามารถจัดหาเองได้โดยใช้กลยุทธ์ maximin ของเรา x 0 = 1/2

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

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

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

SA กลยุทธ์แบบผสมของผู้เล่น A คือการประยุกต์ใช้กลยุทธ์บริสุทธิ์ A1, A2, ..., Am ที่มีความน่าจะเป็น p1, p2, ..., pi, ..., pm และผลรวมของความน่าจะเป็นเท่ากับ 1: กลยุทธ์ผสมของผู้เล่น A เขียนในรูปแบบของเมทริกซ์หรือเป็นสตริง SA = (p1, p2, ..., pi, ..., pm) ในทำนองเดียวกันกลยุทธ์แบบผสมของผู้เล่น B จะแสดงโดย: หรือ , SB = (q1, q2, ..., qi, ..., qn ) โดยที่ผลรวมของความน่าจะเป็นของการปรากฏตัวของกลยุทธ์เท่ากับ 1: กลยุทธ์บริสุทธิ์ถือได้ว่าเป็นกรณีพิเศษของการผสมผสานและให้ โดยสตริงที่ 1 สอดคล้องกับกลยุทธ์ที่บริสุทธิ์ ตามหลักการ minimax วิธีแก้ปัญหาที่ดีที่สุด (หรือวิธีแก้ปัญหา) ของเกมถูกกำหนด: นี่คือกลยุทธ์ที่เหมาะสมที่สุดคู่ S * A, S * B ในกรณีทั่วไปแบบผสมมี กำลังติดตามทรัพย์สิน: หากผู้เล่นคนใดคนหนึ่งปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุดของเขา อีกคนก็จะไม่สามารถหากำไรจากการเบี่ยงเบนไปจากเขาเองได้ ผลตอบแทนที่สอดคล้องกับวิธีแก้ปัญหาที่ดีที่สุดเรียกว่าต้นทุนของเกม v. ราคาของเกมตอบสนองความไม่เท่าเทียมกัน:? ? วี? ? (3.5) ที่ไหน? และ? - ด้านล่างและ ราคาสูงสุดเกม. ทฤษฎีบทหลักของทฤษฎีเกมต่อไปนี้เป็นจริง - ทฤษฎีบทของนอยมันน์ ท้ายเกมแต่ละเกมมีทางออกที่ดีที่สุดอย่างน้อยหนึ่งทาง อาจเป็นกลยุทธ์แบบผสม ให้ S * A = (p * 1, p * 2, ..., p * i, ..., p * m) และ S * B = (q * 1, q * 2, ..., q * i, ..., q * n) คือคู่กลยุทธ์ที่เหมาะสมที่สุด หากกลยุทธ์ล้วนรวมอยู่ในกลยุทธ์แบบผสมที่เหมาะสมที่สุดโดยมีความน่าจะเป็นที่ไม่ใช่ศูนย์ กลยุทธ์นั้นจะเรียกว่าใช้งานอยู่ ทฤษฎีบทเกี่ยวกับกลยุทธ์เชิงรุกนั้นใช้ได้: หากผู้เล่นคนใดคนหนึ่งปฏิบัติตามกลยุทธ์แบบผสมที่เหมาะสมที่สุดของเขา ผลตอบแทนจะยังคงไม่เปลี่ยนแปลงและเท่ากับราคาของเกม v หากผู้เล่นคนที่สองไม่เกินขีดจำกัดของกลยุทธ์ที่ใช้งานอยู่ ทฤษฎีบทนี้มีความสำคัญในทางปฏิบัติอย่างยิ่ง โดยให้แบบจำลองเฉพาะสำหรับการค้นหากลยุทธ์ที่เหมาะสมที่สุดในกรณีที่ไม่มีจุดอาน พิจารณาเกม 2 × 2 ซึ่งเป็นกรณีที่ง่ายที่สุดของเกมที่มีขอบเขตจำกัด หากเกมดังกล่าวมีจุดอาน ทางออกที่ดีที่สุดคือคู่ของกลยุทธ์บริสุทธิ์ที่สอดคล้องกับจุดนี้ เกมที่ไม่มีจุดอานตามทฤษฎีบทหลักของทฤษฎีเกมมีวิธีแก้ปัญหาที่ดีที่สุดและถูกกำหนดโดยกลยุทธ์แบบผสม S * A = (p * 1, p * 2) และ S * B = (q * 1, คิว * 2) ... เราจะใช้ทฤษฎีบทกับกลยุทธ์เชิงรุกเพื่อค้นหาสิ่งเหล่านี้ หากผู้เล่น A ปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุดของเขา S "A ผลตอบแทนเฉลี่ยของเขาจะเท่ากับราคาของเกม v ไม่ว่าผู้เล่น B จะใช้กลยุทธ์แบบแอคทีฟใดก็ตาม สำหรับเกม 2 × 2 กลยุทธ์ที่บริสุทธิ์ของคู่ต่อสู้คือ ใช้งานได้หากไม่มีจุดอาน ผลตอบแทนของผู้เล่น A (การสูญเสียผู้เล่น B) - ค่าสุ่มความคาดหวังทางคณิตศาสตร์ (ค่าเฉลี่ย) ซึ่งเป็นราคาของเกม ดังนั้นผลตอบแทนเฉลี่ยของผู้เล่น A (กลยุทธ์ที่เหมาะสมที่สุด) จะเท่ากับ v สำหรับกลยุทธ์ที่ 1 และ 2 ของคู่ต่อสู้ ให้เกมถูกระบุโดยเมทริกซ์การจ่ายผลตอบแทน ผลตอบแทนเฉลี่ยของผู้เล่น A หากเขาใช้กลยุทธ์ผสมที่เหมาะสมที่สุด และผู้เล่น B ใช้กลยุทธ์บริสุทธิ์ B1 (ซึ่งสอดคล้องกับคอลัมน์ที่ 1 ของเมทริกซ์ผลตอบแทน P) เท่ากับ ราคาของเกม v: a11 p * 1 + a21 p * 2 = v. ผู้เล่น A จะได้รับผลตอบแทนเฉลี่ยเท่ากัน หากผู้เล่นคนที่ 2 ใช้กลยุทธ์ B2 กล่าวคือ a12 p * 1 + a22 p * 2 = v. โดยคำนึงถึงว่า p * 1 + p * 2 = 1 เราได้รับระบบสมการเพื่อกำหนดกลยุทธ์ที่เหมาะสม S "A และราคาของเกม v: (3.6) การแก้ระบบนี้ เราได้รับกลยุทธ์ที่เหมาะสมที่สุด (3.7 ) และราคาของเกม (3.8) กลยุทธ์ที่ใช้งานเมื่อค้นหา SB * - กลยุทธ์ที่ดีที่สุดของผู้เล่น B เราพบว่าสำหรับกลยุทธ์ที่บริสุทธิ์ของผู้เล่น A (A1 หรือ A2) การสูญเสียผู้เล่น B โดยเฉลี่ยจะเท่ากับ ราคาเกม v เช่น (3.9) จากนั้นกลยุทธ์ที่เหมาะสมจะถูกกำหนดโดยสูตร: (3.10 )

กลยุทธ์ "สะอาด"

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

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

แนวคิดของกลยุทธ์ล้วนๆ ก็เป็นหนึ่งในแนวคิดหลักในเนื้อหาเหล่านี้เช่นกัน ดังนั้นฉันจะยกตัวอย่าง:

ตอนเย็น. คุณกำลังรีบกลับบ้านในพื้นที่บ้านของคุณ นมวิ่งหนีไป เมื่อบินผ่าน "ประเภทน่าสงสัย" คุณได้ยินในที่อยู่ของคุณ "เฮ้คุณ [ตัดโดยการเซ็นเซอร์] อย่าไปที่นี่หัวจะหิมะตก!”

คุณจะทำอะไร? มีตัวเลือกมากมาย ใครบางคนจะออกไปจัดการกับบางสิ่ง บางคนจะกลัวและเร่งฝีเท้าของเขา ใครบางคนจะตะโกนตอบกลับมา อย่างไรก็ตาม ลองคิดดู กลยุทธ์ที่แท้จริงของพฤติกรรมในกรณีนี้คืออะไร?

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

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

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

คุณสามารถอ่านเล็กน้อยเกี่ยวกับกลยุทธ์ที่บริสุทธิ์ได้ในหมายเหตุว่า "ทำไมต้องใช้กลยุทธ์ที่บริสุทธิ์" และบ้าน ฮอปกินส์ ฯลฯ..

กลยุทธ์ 1. คำจำกัดความของคำว่า "กลยุทธ์": ก) มาจากคำภาษากรีก "ยุทธศาสตร์" หมายถึง: "ผู้นำทางทหาร", "วิทยาศาสตร์, ศิลปะแห่งสงคราม", "ศิลปะแห่งความเป็นผู้นำทางสังคม, การต่อสู้ทางการเมือง" B) แผนรายละเอียดสำหรับการบรรลุเป้าหมายหรือผลกำไร

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