თამაშის მოდელების კონცეფცია.

ორპირიანი ნულოვანი ჯამის თამაში ეწოდება, რომელშიც თითოეულ მათგანს აქვს სტრატეგიების სასრული ნაკრები. მატრიცული თამაშის წესები განისაზღვრება ანაზღაურების მატრიცით, რომლის ელემენტებია პირველი მოთამაშის ანაზღაურება, რაც ასევე არის მეორე მოთამაშის ზარალი.

მატრიცის თამაში ანტაგონისტური თამაშია. პირველი მოთამაშე იღებს მაქსიმალურ გარანტირებულ (არ არის დამოკიდებული მეორე მოთამაშის ქცევაზე) ანაზღაურებას თამაშის ფასის ტოლფასი, ანალოგიურად, მეორე მოთამაშე აღწევს მინიმალურ გარანტირებულ წაგებას.

ქვეშ სტრატეგია გაგებულია, როგორც წესების (პრინციპების) ერთობლიობა, რომელიც განსაზღვრავს მოქმედებების ვარიანტს მოთამაშის თითოეული პირადი ნაბიჯისთვის, არსებული სიტუაციიდან გამომდინარე.

ახლა ყველაფერი წესრიგში და დეტალურად.

ანაზღაურების მატრიცა, სუფთა სტრატეგიები, თამაშის ფასი

AT მატრიცის თამაში მისი წესები განისაზღვრება ანაზღაურების მატრიცა .

განვიხილოთ თამაში, რომელშიც ორი მონაწილეა: პირველი და მეორე მოთამაშე. დაე, პირველ მოთამაშეს ჰქონდეს მ სუფთა სტრატეგიებიდა მეორე მოთამაშის განკარგულებაშია - ნსუფთა სტრატეგიები. ვინაიდან თამაში განიხილება, ბუნებრივია, რომ ამ თამაშში არის მოგება და წაგება.

AT გადახდის მატრიცა ელემენტები არის რიცხვები, რომლებიც გამოხატავენ მოთამაშეთა მოგებას და ზარალს. მოგება და წაგება შეიძლება გამოიხატოს ქულებით, ფულით ან სხვა ერთეულებით.

მოდით შევქმნათ ანაზღაურების მატრიცა:

თუ პირველი მოთამაშე აირჩევს მე-ე სუფთა სტრატეგია და მეორე მოთამაშე ჯ-ე სუფთა სტრატეგია, მაშინ პირველი მოთამაშის ანაზღაურება არის აიჯერთეულები და მეორე მოთამაშის დაკარგვაც აიჯერთეულები.

იმიტომ რომ აij + (- ა ij ) = 0, მაშინ აღწერილი თამაში არის ნულოვანი ჯამის მატრიცული თამაში.

მატრიცული თამაშის უმარტივესი მაგალითია მონეტის სროლა. თამაშის წესები ასეთია. პირველი და მეორე მოთამაშეები აგდებენ მონეტას და შედეგი არის თავები ან კუდები. თუ თავები და თავები ან კუდები ან კუდები ერთდროულად დაიძვრება, მაშინ პირველი მოთამაშე მოიგებს ერთ ერთეულს, ხოლო სხვა შემთხვევაში ის წააგებს ერთ ერთეულს (მეორე მოთამაშე მოიგებს ერთ ერთეულს). იგივე ორი სტრატეგია მეორე მოთამაშის განკარგულებაშია. შესაბამისი ანაზღაურების მატრიცა იქნება:

თამაშის თეორიის ამოცანაა დაადგინოს პირველი მოთამაშის სტრატეგიის არჩევანი, რომელიც უზრუნველყოფს მას მაქსიმალური საშუალო მოგების გარანტიას, ისევე როგორც მეორე მოთამაშის სტრატეგიის არჩევას, რომელიც უზრუნველყოფს მას მაქსიმალური საშუალო ზარალის გარანტიას.

როგორ არჩევენ სტრატეგიას მატრიცულ თამაშში?

მოდით კიდევ ერთხელ გადავხედოთ ანაზღაურების მატრიცას:

პირველ რიგში, ჩვენ განვსაზღვრავთ პირველი მოთამაშის ანაზღაურებას, თუ ის იყენებს მეწმინდა სტრატეგია. თუ პირველი მოთამაშე იყენებს მე- სუფთა სტრატეგია, მაშინ ლოგიკურია ვივარაუდოთ, რომ მეორე მოთამაშე გამოიყენებს ისეთ სუფთა სტრატეგიას, რის გამოც პირველი მოთამაშის ანაზღაურება მინიმალური იქნება. თავის მხრივ, პირველი მოთამაშე გამოიყენებს ისეთ სუფთა სტრატეგიას, რომელიც მას უზრუნველყოფს მაქსიმალური მოგება. ამ პირობებიდან გამომდინარე, პირველი მოთამაშის ანაზღაურება, რომელსაც ჩვენ აღვნიშნავთ, როგორც ვ1 , ეწოდება მაქსიმალური გამარჯვება ან ქვედა თამაშის ფასად .

ზე ამ მნიშვნელობებისთვის, პირველი მოთამაშე უნდა იმოქმედოს შემდეგნაირად. თითოეული სტრიქონიდან ჩაწერეთ მინიმალური ელემენტის მნიშვნელობა და აირჩიეთ მათგან მაქსიმუმი. ამრიგად, პირველი მოთამაშის ანაზღაურება იქნება მინიმუმის მაქსიმუმი. აქედან მომდინარეობს სახელი - maximin win. ამ ელემენტის ხაზის ნომერი იქნება პირველი მოთამაშის მიერ არჩეული სუფთა სტრატეგიის რაოდენობა.

ახლა განვსაზღვროთ მეორე მოთამაშის წაგება თუ ის იყენებს ჯ- სტრატეგია. ამ შემთხვევაში, პირველი მოთამაშე იყენებს საკუთარ სუფთა სტრატეგიას, რომელშიც მეორე მოთამაშის წაგება იქნება მაქსიმალური. მეორე მოთამაშემ უნდა აირჩიოს ისეთი სუფთა სტრატეგია, რომელშიც მისი დანაკარგი მინიმალური იქნება. მეორე მოთამაშის დაკარგვა, რომელსაც ჩვენ აღვნიშნავთ, როგორც ვ2 , ეწოდება მინიმალური დანაკარგი ან თამაშის ყველაზე მაღალი ფასი .

ზე თამაშის ფასზე პრობლემების გადაჭრა და სტრატეგიის განსაზღვრა მეორე მოთამაშისთვის ამ მნიშვნელობების დასადგენად, გააგრძელეთ შემდეგნაირად. თითოეული სვეტიდან ჩაწერეთ მაქსიმალური ელემენტის მნიშვნელობა და აირჩიეთ მათგან მინიმალური. ამრიგად, მეორე მოთამაშის წაგება იქნება მაქსიმუმის მინიმუმი. აქედან მოდის სახელწოდება - მინიმალური მომატება. ამ ელემენტის სვეტის ნომერი იქნება მეორე მოთამაშის მიერ არჩეული სუფთა სტრატეგიის რაოდენობა. თუ მეორე მოთამაშე იყენებს „მინიმქსს“, მაშინ, მიუხედავად პირველი მოთამაშის მიერ სტრატეგიის არჩევისა, ის მაქსიმუმ წააგებს. ვ2 ერთეულები.

მაგალითი 1

.

რიგების უმცირესი ელემენტებიდან ყველაზე დიდი არის 2, ეს არის თამაშის დაბალი ფასი, პირველი რიგი შეესაბამება მას, შესაბამისად, პირველი მოთამაშის მაქსიმალური სტრატეგია პირველია. სვეტების უდიდესი ელემენტებიდან ყველაზე პატარა არის 5, ეს არის თამაშის ზედა ფასი, მეორე სვეტი შეესაბამება მას, შესაბამისად, მეორე მოთამაშის მინიმალური სტრატეგია არის მეორე.

ახლა, როდესაც ჩვენ ვისწავლეთ თამაშის ქვედა და ზედა ფასის პოვნა, მაქსიმალური და მინიმალური სტრატეგიები, დროა ვისწავლოთ, როგორ გამოვყოთ ეს ცნებები ფორმალურად.

ასე რომ, პირველი მოთამაშის გარანტირებული ანაზღაურებაა:

პირველმა მოთამაშემ უნდა აირჩიოს სუფთა სტრატეგია, რომელიც უზრუნველყოფს მას მინიმალური ანაზღაურების მაქსიმუმს. ეს მოგება (მაქსიმინი) აღინიშნება შემდეგნაირად:

.

პირველი მოთამაშე იყენებს თავის სუფთა სტრატეგიას, რათა მეორე მოთამაშის წაგება იყოს მაქსიმალური. ეს დანაკარგი განისაზღვრება შემდეგნაირად:

მეორე მოთამაშემ უნდა აირჩიოს თავისი სუფთა სტრატეგია ისე, რომ მისი დანაკარგი იყოს მინიმალური. ეს დანაკარგი (მინიმუმი) აღინიშნება შემდეგნაირად:

.

კიდევ ერთი მაგალითი იმავე სერიიდან.

მაგალითი 2მოცემულია მატრიცული თამაში ანაზღაურების მატრიცით

.

განსაზღვრეთ პირველი მოთამაშის მაქსიმალური სტრატეგია, მეორე მოთამაშის მინიმალური სტრატეგია, თამაშის ქვედა და ზედა ფასი.

გადაწყვეტილება. ანაზღაურების მატრიცის მარჯვნივ, ჩვენ ვწერთ მის რიგებში ყველაზე პატარა ელემენტებს და აღვნიშნავთ მათ მაქსიმუმს, ხოლო მატრიცის ქვემოდან - ყველაზე დიდი ელემენტებისვეტებში და აირჩიეთ მათგან ყველაზე პატარა:

მწკრივების უმცირესი ელემენტებიდან ყველაზე დიდი არის 3, ეს არის თამაშის დაბალი ფასი, მეორე რიგი შეესაბამება მას, შესაბამისად, პირველი მოთამაშის მაქსიმალური სტრატეგია მეორეა. სვეტების უდიდესი ელემენტებიდან ყველაზე პატარა არის 5, ეს არის თამაშის ზედა ფასი, მას შეესაბამება პირველი სვეტი, შესაბამისად, მეორე მოთამაშის მინიმალური სტრატეგია პირველია.

უნაგირის წერტილი მატრიცულ თამაშებში

თუ თამაშის ზედა და ქვედა ფასი ერთნაირია, მაშინ მატრიცულ თამაშს ჩაითვლება უნაგირის წერტილი. პირიქითაც მართალია: თუ მატრიცულ თამაშს აქვს უნაგირის წერტილი, მაშინ მატრიცის თამაშის ზედა და ქვედა ფასები ერთნაირია. შესაბამისი ელემენტი არის როგორც ყველაზე პატარა მწკრივში, ასევე ყველაზე დიდი სვეტში და ფასის ტოლითამაშები.

ამრიგად, თუ , მაშინ არის პირველი მოთამაშის ოპტიმალური სუფთა სტრატეგია და არის მეორე მოთამაშის ოპტიმალური სუფთა სტრატეგია. ანუ, თამაშის თანაბარი ქვედა და ზედა ფასები მიიღწევა იმავე წყვილ სტრატეგიაზე.

Ამ შემთხვევაში მატრიცულ თამაშს აქვს გამოსავალი სუფთა სტრატეგიებში .

მაგალითი 3მოცემულია მატრიცული თამაში ანაზღაურების მატრიცით

.

გადაწყვეტილება. ანაზღაურების მატრიცის მარჯვნივ, ჩვენ ვწერთ მის რიგებში ყველაზე პატარა ელემენტებს და აღვნიშნავთ მათ მაქსიმუმს, ხოლო მატრიცის ქვემოდან - ყველაზე დიდ ელემენტებს სვეტებში და ვირჩევთ მათ მინიმუმს:

თამაშის დაბალი ფასი იგივეა, რაც თამაშის ზედა ფასი. ამრიგად, თამაშის ფასი არის 5. ანუ . თამაშის ფასი უდრის უნაგირის წერტილის მნიშვნელობას. პირველი მოთამაშის მაქსიმალური სტრატეგია არის მეორე სუფთა სტრატეგია, ხოლო მეორე მოთამაშის მინიმალური სტრატეგია არის მესამე სუფთა სტრატეგია. ამ მატრიცულ თამაშს აქვს გამოსავალი სუფთა სტრატეგიებში.

თავად მოაგვარეთ მატრიცული თამაშის პრობლემა და შემდეგ იხილეთ გამოსავალი

მაგალითი 4მოცემულია მატრიცული თამაში ანაზღაურების მატრიცით

.

იპოვნეთ თამაშის ქვედა და ზედა ფასი. აქვს თუ არა ამ მატრიცის თამაშს უნაგირის წერტილი?

მატრიცული თამაშები ოპტიმალური შერეული სტრატეგიით

უმეტეს შემთხვევაში, მატრიცულ თამაშს არ აქვს უნაგირის წერტილი, ამიტომ შესაბამის მატრიცულ თამაშს არ აქვს სუფთა სტრატეგიული გადაწყვეტილებები.

მაგრამ მას აქვს გამოსავალი ოპტიმალურ შერეულ სტრატეგიებში. მათ საპოვნელად უნდა ვივარაუდოთ, რომ თამაში საკმარისად მეორდება, რომ გამოცდილებიდან გამომდინარე, გამოიცნოს რომელი სტრატეგია არის სასურველი. აქედან გამომდინარე, გადაწყვეტილება ასოცირდება ალბათობის და საშუალო (მოლოდინის) კონცეფციასთან. საბოლოო გადაწყვეტაში არის როგორც უნაგირების წერტილის ანალოგი (ანუ თამაშის ქვედა და ზედა ფასების თანასწორობა), ასევე მათ შესაბამისი სტრატეგიების ანალოგი.

ასე რომ, იმისათვის, რომ პირველმა მოთამაშემ მიიღოს მაქსიმალური საშუალო მოგება და მეორე მოთამაშეს ჰქონდეს მინიმალური საშუალო დანაკარგი, სუფთა სტრატეგიები უნდა იქნას გამოყენებული გარკვეული ალბათობით.

თუ პირველი მოთამაშე იყენებს სუფთა სტრატეგიებს ალბათობით , შემდეგ ვექტორი ეწოდება პირველი მოთამაშის შერეულ სტრატეგიას. სხვა სიტყვებით რომ ვთქვათ, ეს არის სუფთა სტრატეგიების „ნარევი“. ამ ალბათობების ჯამი უდრის ერთს:

.

თუ მეორე მოთამაშე იყენებს სუფთა სტრატეგიებს ალბათობით , შემდეგ ვექტორი მეორე მოთამაშის შერეულ სტრატეგიას უწოდებენ. ამ ალბათობების ჯამი უდრის ერთს:

.

თუ პირველი მოთამაშე იყენებს შერეულ სტრატეგიას გვ, ხოლო მეორე მოთამაშე - შერეული სტრატეგია ქ, მაშინ აზრი აქვს მოსალოდნელი ღირებულება პირველი მოთამაშე იგებს (მეორე მოთამაშე აგებს). მის საპოვნელად, თქვენ უნდა გაამრავლოთ პირველი მოთამაშის შერეული სტრატეგიის ვექტორი (რომელიც იქნება ერთი რიგის მატრიცა), ანაზღაურების მატრიცა და მეორე მოთამაშის შერეული სტრატეგიის ვექტორი (რომელიც იქნება ერთსვეტიანი მატრიცა):

.

მაგალითი 5მოცემულია მატრიცული თამაში ანაზღაურების მატრიცით

.

დაადგინეთ პირველი მოთამაშის მოგების მათემატიკური მოლოდინი (მეორე მოთამაშის წაგება), თუ პირველი მოთამაშის შერეული სტრატეგია არის , ხოლო მეორე მოთამაშის შერეული სტრატეგია არის .

გადაწყვეტილება. პირველი მოთამაშის მოგების მათემატიკური მოლოდინის ფორმულის მიხედვით (მეორე მოთამაშის ზარალი), ის უდრის პირველი მოთამაშის შერეული სტრატეგიის ვექტორის, ანაზღაურების მატრიცის და მეორე მოთამაშის შერეული სტრატეგიის ვექტორის ნამრავლს:

პირველ მოთამაშეს უწოდებენ ისეთ შერეულ სტრატეგიას, რომელიც უზრუნველყოფს მას მაქსიმალურ საშუალო ანაზღაურებას, თუ თამაში განმეორდება საკმარისი რაოდენობით.

ოპტიმალური შერეული სტრატეგია მეორე მოთამაშეს ეძახიან ისეთ შერეულ სტრატეგიას, რომელიც უზრუნველყოფს მას მინიმალური საშუალო წაგებით, თუ თამაში განმეორდება საკმარისი რაოდენობით.

წმინდა სტრატეგიების შემთხვევაში მაქსიმინისა და მინიმქსის აღნიშვნის ანალოგიით, ოპტიმალური შერეული სტრატეგიები აღინიშნება შემდეგნაირად (და ასოცირდება მათემატიკური მოლოდინი, ანუ პირველი მოთამაშის მოგების და მეორე მოთამაშის წაგების საშუალო მაჩვენებელი):

,

.

ამ შემთხვევაში, ფუნქციისთვის ე არის უნაგირის წერტილი , რაც თანასწორობას ნიშნავს.

იმისათვის, რომ ვიპოვოთ ოპტიმალური შერეული სტრატეგიები და უნაგირის წერტილი, ე.ი. მატრიცული თამაშის გადაჭრა შერეული სტრატეგიებით , თქვენ უნდა შეამციროთ მატრიცული თამაში ხაზოვანი პროგრამირების პრობლემამდე, ანუ ოპტიმიზაციის პრობლემამდე და გადაჭრათ შესაბამისი ხაზოვანი პროგრამირების პრობლემა.

მატრიცული თამაშის დაყვანა ხაზოვანი პროგრამირების პრობლემამდე

მატრიცული თამაშის შერეული სტრატეგიების გადასაჭრელად, თქვენ უნდა შეადგინოთ სწორი ხაზი ხაზოვანი პროგრამირების პრობლემადა მისი ორმაგი ამოცანა. ორმაგ პრობლემაში, გაძლიერებული მატრიცა, რომელიც ინახავს ცვლადების კოეფიციენტებს შეზღუდვის სისტემაში, მუდმივ წევრებს და ცვლადების კოეფიციენტებს მიზნის ფუნქციაში, ტრანსპონირებულია. ამ შემთხვევაში, ორიგინალური ამოცანის მიზნობრივი ფუნქციის მინიმუმი ასოცირდება მაქსიმუმთან ორმაგ პრობლემაში.

მიზნის ფუნქცია პირდაპირი ხაზოვანი პროგრამირების ამოცანაში:

.

შეზღუდვების სისტემა ხაზოვანი პროგრამირების უშუალო პრობლემაში:

მიზნის ფუნქცია ორმაგ პრობლემაში:

.

შეზღუდვების სისტემა ორმაგ პრობლემაში:

მიუთითეთ პირდაპირი წრფივი პროგრამირების ამოცანის ოპტიმალური გეგმა

,

ხოლო ორმაგი ამოცანის ოპტიმალური გეგმა აღინიშნება

ხაზოვანი ფორმები შესაბამისი ოპტიმალური გეგმებიაღვნიშნო და,

და თქვენ უნდა იპოვოთ ისინი, როგორც ოპტიმალური გეგმების შესაბამისი კოორდინატების ჯამი.

წინა ნაწილის განმარტებებისა და ოპტიმალური გეგმების კოორდინატების შესაბამისად, მოქმედებს პირველი და მეორე მოთამაშის შემდეგი შერეული სტრატეგიები:

.

მათემატიკოსებმა ეს დაამტკიცეს თამაშის ფასი გამოიხატება ოპტიმალური გეგმების წრფივი ფორმებით შემდეგნაირად:

,

ანუ ეს არის ოპტიმალური გეგმების კოორდინატების ჯამების ორმხრივი.

ჩვენ, პრაქტიკოსებს, შეგვიძლია გამოვიყენოთ ეს ფორმულა მხოლოდ შერეული სტრატეგიების მატრიცული თამაშების გადასაჭრელად. მოსწონს ფორმულები ოპტიმალური შერეული სტრატეგიების მოსაძებნად შესაბამისად პირველი და მეორე მოთამაშე:

რომელშიც მეორე ფაქტორები არის ვექტორები. ოპტიმალური შერეული სტრატეგიები ასევე არის ვექტორები, როგორც უკვე განვსაზღვრეთ წინა აბზაცში. მაშასადამე, რიცხვის (თამაშის ფასის) ვექტორზე (ოპტიმალური გეგმების კოორდინატებით) გამრავლებით ვექტორსაც ვიღებთ.

მაგალითი 6მოცემულია მატრიცული თამაში ანაზღაურების მატრიცით

.

იპოვნეთ თამაშის ფასი ვდა ოპტიმალური შერეული სტრატეგიები და .

გადაწყვეტილება. ჩვენ ვადგენთ ხაზოვანი პროგრამირების ამოცანას, რომელიც შეესაბამება ამ მატრიცის თამაშს:

ჩვენ ვიღებთ პირდაპირი პრობლემის გადაწყვეტას:

.

ოპტიმალური გეგმების წრფივ ფორმას ვპოულობთ ნაპოვნი კოორდინატების ჯამის სახით.

განვიხილოთ დაწყვილებული სასრული თამაში. მიეცით მოთამაშეს დააქვს ტპირადი სტრატეგიები, რომელსაც ჩვენ აღვნიშნავთ

მიეცით მოთამაშეს ATხელმისაწვდომი პპირადი სტრატეგიები, მოდით აღვნიშნოთ ისინი. ისინი ამბობენ, რომ თამაშს აქვს განზომილება ტ X პ.

ნებისმიერი წყვილი სტრატეგიის მოთამაშეების მიერ არჩევის შედეგად ცალსახად განისაზღვრება თამაშის შედეგი, ე.ი. გამარჯვება ა;. მოთამაშე და(დადებითი ან უარყოფითი) და დამარცხებული (-აი)მოთამაშე AT.დავუშვათ, რომ ღირებულებები ა..ცნობილია ნებისმიერი წყვილი სტრატეგიით (A:, B;.). მატრიცა P =(ა..), მე == 1, 2, ..., მჯ = 1, 2, ..., P,რომლის ელემენტებია სტრატეგიების შესაბამისი ანაზღაურება და.და bj,დაურეკა გადახდის მატრიცა,ან თამაშის მატრიცა. ზოგადი ფორმაასეთი მატრიცა წარმოდგენილია ცხრილში. 12.1. ამ ცხრილის რიგები შეესაბამება მოთამაშის სტრატეგიებს და,და სვეტები არის მოთამაშის სტრატეგიები AT.

ცხრილი 12.1

მოდით გავაკეთოთ ანაზღაურებადი მატრიცა შემდეგი თამაშისთვის.

12.1. თამაშის ძებნა.

მოთამაშე დაშეუძლია დაიმალოს ორიდან ერთ-ერთ თავშესაფარში (I და II); მოთამაშე ATეძებს მოთამაშეს და,და თუ აღმოაჩენს, 1 დენს ჯარიმდება. ერთეულები საწყისი და,წინააღმდეგ შემთხვევაში იხდის მოთამაშეს და 1 დღე ერთეულები აუცილებელია თამაშის ანაზღაურების მატრიცის აგება.

დ ე ს ჰ ე ნ ი ს. შედგენისთვის გადახდის მატრიცაუნდა გააანალიზოს თითოეული მოთამაშის ქცევა. მოთამაშე დაშეუძლია I თავშესაფარში დამალვა – ამ სტრატეგიას აღვნიშნავთ ა v ან II თავშესაფარში - სტრატეგია და.გ მოთამაშე ATშეუძლია მოძებნოს პირველი მოთამაშე თავშესაფარში I - სტრატეგია AT(ან თავშესაფარში II - სტრატეგია AT.,.თუ მოთამაშე დაარის I სამალავში და იქ აღმოაჩინა მოთამაშემ AT,იმათ. რამდენიმე სტრატეგია ხორციელდება (Α ν AT{), შემდეგ მოთამაშე დაიხდის ჯარიმას, ე.ი. ა n = -1. ანალოგიურად, ჩვენ ვიღებთ ა. n = -1 (და 2, AT.,).ცხადია, სტრატეგიები (A, AT.,)და (R2, /1,) მიეცით მოთამაშეს დამოიგე 1, ასე რომ აპ = ა. n = I. ამრიგად, 2x2 ზომის თამაშისთვის "ძებნა" მივიღებთ ანაზღაურების მატრიცას:

განიხილეთ თამაში ტ X პმატრიცით P = aკ) , მე = 1,2, ..., თქვენ; ჯ= 1, 2, ... და და განსაზღვრეთ საუკეთესო სტრატეგიებს შორის დაზე ავ..., დამ.სტრატეგიის არჩევა აჯი მოთამაშე დამოთამაშეს უნდა ველოდოთ ATუპასუხებს მას ერთ-ერთი სტრატეგიით AT.,რისთვისაც ანაზღაურება მოთამაშისთვის დამინიმალური (მოთამაშე ATცდილობს მოთამაშის "დაზიანებას". და).

აღნიშნეთ a-ით; მოთამაშის ყველაზე დაბალი ანაზღაურება დაროდესაც ის ირჩევს სტრატეგიას L; ყველა შესაძლო მოთამაშის სტრატეგიისთვის AT(ყველაზე მცირე რაოდენობა მე-ე ხაზიანაზღაურების მატრიცა), ე.ი.

ყველა რიცხვს შორის a (r = 1,2,..., უ)აირჩიეთ ყველაზე დიდი: . დავურეკოთ და თამაშის დაბალი ფასი,ან მაქსიმალური ანაზღაურება (მაქსიმინი).ეს A მოთამაშის გარანტირებული ანაზღაურება B მოთამაშის ნებისმიერი სტრატეგიისთვის.შესაბამისად,

(12.2)

მაქსიმინის შესაბამისი სტრატეგია ე.წ მაქსიმალური სტრატეგია.მოთამაშე ATდაინტერესებულია მოთამაშის ანაზღაურების შემცირებით და;სტრატეგიის არჩევა AT.,იგი ითვალისწინებს მაქსიმალურ შესაძლო ანაზღაურებას და.აღნიშნეთ

ყველა რიცხვს შორის β. აირჩიეთ ყველაზე პატარა

და მოვუწოდებთ β თამაშის ყველაზე მაღალი ფასი, ან მინიმალური ანაზღაურება (მინიმქსი).ეს B მოთამაშის გარანტირებული დაკარგვა.შესაბამისად,

(12.4)

მინიმალური სტრატეგია ე.წ მინიმალური სტრატეგია.

პრინციპს, რომელიც კარნახობს მოთამაშეებს ყველაზე "ფრთხილი" მინიმაქსის და მაქსიმინის სტრატეგიების არჩევას, ეწოდება პრინციპი. მინიმაქსი.ეს პრინციპი გამომდინარეობს გონივრული დაშვებიდან, რომ თითოეული მოთამაშე ცდილობს მიაღწიოს მოწინააღმდეგის საპირისპირო მიზნებს. მოდით განვსაზღვროთ თამაშის ქვედა და ზედა ფასები და შესაბამისი სტრატეგიები პრობლემა 12.1-ში. განვიხილოთ ანაზღაურების მატრიცა

12.1 პრობლემისგან. A სტრატეგიის არჩევისას (მატრიცის პირველი რიგი) მინიმალური მოგებაუდრის a, =min(-l; 1) = -1 და შეესაბამება მოთამაშის β1 სტრატეგიას AT.სტრატეგიის არჩევისას ლ 2 (მატრიცის მეორე რიგი) მინიმალური ანაზღაურებაა ა 2 = min(l; -1) = -1, ეს მიიღწევა სტრატეგიით AT.,.

მაქსიმალური მოგების გარანტია მოთამაშის ნებისმიერი სტრატეგიისთვის AT, ე.ი. თამაშის დაბალი ფასი a = max(a, a2) = max(-l; -1) = -1, მოთამაშე დაშეუძლია აირჩიოს ნებისმიერი სტრატეგია: Aj ან და 2, ე.ი. მისი ნებისმიერი სტრატეგია არის მაქსიმუმი.

სტრატეგიის არჩევა B, (სვეტი 1), მოთამაშე ATესმის, რომ მოთამაშე დაუპასუხებს სტრატეგიით და 2 თქვენი მოგების მაქსიმალური გასაზრდელად (ზარალი AT).შესაბამისად, მოთამაშის მაქსიმალური დანაკარგი ATროდესაც ის ირჩევს B სტრატეგიას, უდრის β, = max(-1; 1) = 1.

ანალოგიურად, B მოთამაშის მაქსიმალური დანაკარგი (მოგება და) როდესაც ის ირჩევს სტრატეგიას B2 (სვეტი 2) უდრის β2 = max(l; -1) = 1.

ამრიგად, მოთამაშის ნებისმიერი სტრატეგიისთვის და B მოთამაშის გარანტირებული მინიმალური წაგება უდრის β = πιίη(β1, β2) = min(l; 1) = 1- თამაშის მთავარი ფასი.

B მოთამაშის ნებისმიერი სტრატეგია არის მინიმალური. ცხრილის დამატებით. 12.1 ხაზი β; და სვეტი a;, ვიღებთ ცხრილს. 12.2. დამატებითი სტრიქონებისა და სვეტების კვეთაზე ჩვენ ჩავწერთ თამაშების ზედა და ქვედა ფასებს.

ცხრილი 12.2

ზემოთ მოცემულ პრობლემა 12.1-ში, თამაშის ზედა და ქვედა ხარჯები განსხვავებულია: ა ვ β.

თუ თამაშის ზედა და ქვედა ფასები ერთნაირია, მაშინ ზოგადი მნიშვნელობათამაშის ზედა და ქვედა ფასები α = β = υ ეწოდება თამაშის წმინდა ფასი,ან თამაშის ფასი.თამაშის ფასის შესაბამისი მინიმალური სტრატეგიებია ოპტიმალური სტრატეგიებიდა მათი მთლიანობა ოპტიმალური გადაწყვეტაან გადაწყვეტილებათამაშები. ამ შემთხვევაში მოთამაშე დაიღებს მაქსიმალურ გარანტიას (მოთამაშის ქცევისგან დამოუკიდებლად) AT)ანაზღაურება არის υ, და მოთამაშე ATაღწევს მინიმალურ გარანტირებულ (მიუხედავად მოთამაშის L ქცევისა) წაგებას υ. როგორც ამბობენ, თამაშის გამოსავალი აქვს სტაბილურობა,იმათ. თუ ერთ-ერთი მოთამაშე იცავს მას ოპტიმალური სტრატეგია, მაშინ სხვისთვის არ შეიძლება იყოს მომგებიანი მისი ოპტიმალური სტრატეგიიდან გადახვევა.

რამდენიმე სუფთა სტრატეგია და.და V. იძლევა ოპტიმალური გადაწყვეტათამაში, თუ და მხოლოდ იმ შემთხვევაში, თუ შესაბამისი ელემენტი r არის ყველაზე დიდი მის სვეტში და ყველაზე პატარა მწკრივში. ასეთ სიტუაციას, თუ ის არსებობს, ე.წ უნაგირის წერტილი(მსგავსი უნაგირის ზედაპირისა, რომელიც ერთი მიმართულებით იხრება მაღლა და მეორე მიმართულებით ქვემოთ).

აღნიშნეთ და *და AT*არის სუფთა სტრატეგიების წყვილი, რომლებზედაც მიიღწევა თამაშის გადაწყვეტა უნაგირის წერტილით პრობლემაში. მოდით წარმოგიდგინოთ პირველი მოთამაშის ანაზღაურების ფუნქცია სტრატეგიების თითოეულ წყვილზე: P(A:, AT-) = და ზე. მაშინ ოპტიმალური პირობა უნაგირის წერტილში აკმაყოფილებს ორმაგ უტოლობას: P(Aj, B*)<Р(А*, В*)<Р(А", В ), რაც ყველასთვის მართალია მე = 1, 2, ..., m;j = 1, 2, ..., პ.მართლაც, სტრატეგიის არჩევანი და* პირველი მოთამაშე ოპტიმალური სტრატეგიით AT"მეორე მოთამაშე მაქსიმალურად ანაზღაურებს მინიმალურ შესაძლო ანაზღაურებას: P(A*, ბ")> P(Aგ AT"),და სტრატეგიის არჩევა B"მეორე მოთამაშე, პირველის ოპტიმალური სტრატეგიით, ამცირებს მაქსიმალურ დანაკარგს: P(D, AT*)<Р(А", В).

12.2. განსაზღვრეთ თამაშის ქვედა და ზედა ფასი, რომელიც მოცემულია ანაზღაურების მატრიცით

აქვს თუ არა თამაშს უნაგირის წერტილი?

ცხრილი 12 3

გადაწყვეტილება.ყველა გამოთვლა მოხერხებულად ხორციელდება ცხრილში, რომელშიც, გარდა მატრიცისა R,შევიდა სვეტი a; და ხაზი)