О выборе стратегии в недетерминированных антагонистических играх

Î âûáîðå ñòðàòåãèè â íåäåòåðìèíèðîâàííûõ àíòàãîíèñòè÷åñêèõ èãðàõ c 1997 ã. Á. Ô. Ìåëüíèêîâ , À. Í. Ðàäèîíîâ ° ÓÄÊ 519.6

Àííîòàöèÿ Èçâåñòíî ìíîæåñòâî èãð, â êîòîðûõ ïðèñóòñòâóþò ñëó÷àéíûå ôàêòîðû, ñóùåñòâåííî âëèÿþùèå íà ïðîöåññ ïðèíÿòèÿ ðåøåíèÿ. Êàê îòûñêàòü õîðîøóþ ñòðàòåãèþ â òàêèõ èãðàõ?  ñëó÷àå äåòåðìèíèðîâàííûõ èãð èçâåñòåí ïåðåáîðíûé ìåòîä íàõîæäåíèÿ õîðîøåé ñòðàòåãèè  ìåòîä ìèíèìàêñà. Îïðåäåëÿåìàÿ ýòèì ìåòîäîì ñòðàòåãèÿ ìîæåò áûòü áëèçêîé ê îïòèìàëüíîé  ïðè óäà÷íîì âûáîðå ôóíêöèè ñòàòè÷åñêîé îöåíêè ïîçèöèè.  íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ ìåòîä äëÿ íàõîæäåíèÿ ñòðàòåãèè, áëèçêîé ê îïòèìàëüíîé è â íåäåòåðìèíèðîâàííîì ñëó÷àå. Äàííûé ìåòîä ÿâëÿåòñÿ íåêîòîðûì îáîáùåíèåì ìåòîäà ìèíèìàêñà. Îí, êàê è ìåòîä ìèíèìàêñà, ïðîèçâîäèò ïîèñê íóæíîé ñòðàòåãèè ïóòåì ïåðåáîðà âàðèàíòîâ ðàçâèòèÿ èãðû, âûáèðàÿ ïðè ýòîì õîä, êîòîðûé èìååò íàèëó÷øóþ, ñïåöèàëüíûì îáðàçîì ïîñòðîåííóþ îöåíêó.

1 Ââåäåíèå 1.1

Ïðîáëåìû è óñïåõè â ïðîãðàììèðîâàíèè èãð

Âîïðîñ î âîçìîæíîñòè ìîäåëèðîâàíèÿ ðàçëè÷íûõ èãð èíòåðåñåí äîâîëüíî øèðîêîìó êðóãó ëþäåé. Èíòåðåñû êîëåáëþòñÿ îò "áûòîâîãî" ëþáîïûòñòâà äî âîçìîæíîñòè ïðàêòè÷åñêîãî ïðèìåíåíèÿ àëãîðèòìîâ ïîèñêà èãðîâûõ ñòðàòåãèé â ìîäåëèðîâàíèè ñëîæíûõ ñèòóàöèé. Êðîìå òîãî, èãðîâîå ïðîãðàììèðîâàíèå ïîðîæäàåò âîêðóã ñåáÿ ìíîæåñòâî äðóãèõ ñïîðîâ. Íàïðèìåð, ïîïûòêè ñîçäàòü ñèëüíóþ øàõìàòíóþ ïðîãðàììó âûçâàëè äèñêóññèþ î òîì, ìîæåò ëè êîìïüþòåð â ïðèíöèïå õîðîøî èãðàòü â øàõìàòû. Äîñòàòî÷íî ëè äëÿ ýòîãî òîëüêî âû÷èñëèòåëüíûõ ðåñóðñîâ? 1

Êàê óñïåøíî ìîãóò ïðèìåíÿòüñÿ "æàäíûå", ñ ìèíèìóìîì ýâðèñòèê, àëãîðèòìû ïîèñêà ñòðàòåãèé (äðóãèìè ñëîâàìè, ïðàâîìåðåí ëè çäåñü ïðèíöèï "ñèëà åñòü  óìà íå íàäî"?). Ïîïðîáóåì ïîêàçàòü, ÷òî ïðîãðàììèðîâàíèå èãð  ýòî ïåðñïåêòèâíîå è âàæíîå íàïðàâëåíèå â êèáåðíåòèêå. Ñäåëàåì ýòî íà êëàññè÷åñêîì ïðèìåðå  øàõìàòàõ. Ñåãîäíÿ ñóùåñòâóåò ìíîæåñòâî êîìïüþòåðíûõ ïðîãðàìì, èãðàþùèõ â øàõìàòû. Ñðåäè íèõ èìåþòñÿ è î÷åíü ñèëüíûå ïðîãðàììû. 1 Ìíîãèå èç íèõ êðàñî÷íî è ñî âêóñîì îôîðìëåíû. Òàê, â íåêîòîðûõ âî âðåìÿ âçÿòèÿ ôèãóð ðàçûãðûâàþòñÿ öåëûå ñïåêòàêëè, íå ëèøåííûå èçâåñòíîãî äðàìàòèçìà. 2 À î ìíîæåñòâå øàõìàòíûõ ïðîãðàìì, íàïèñàííûõ äëÿ Windows 95 èëè Windows NT ãîâîðèòü ìîæíî î÷åíü äîëãî. Âûðàçèòåëüíûå ñðåäñòâà ýòèõ îïåðàöèîííûõ ñèñòåì ïîçâîëÿþò î÷åíü áûñòðî è ëåãêî ïðîèçâåñòè âïå÷àòëåíèå íà ïîòðåáèòåëÿ. À âûñîêàÿ ïðîèçâîäèòåëüíîñòü êîìïüþòåðîâ, áîãàòûé îïûò øàõìàòíîãî ïðîãðàììèðîâàíèÿ è âîçìîæíîñòü ïîèãðàòü ñ óäàëåííûì ïàðòíåðîì ïî ñåòè äåëàåò èãðó íå òîëüêî çðåëèùíîé, íî è óâëåêàòåëüíîé. 3 Âî ìíîãèõ øàõìàòíûõ ïðîãðàììàõ ïðåäóñìîòðåíû âîçìîæíîñòè îáó÷åíèÿ èãðîêà, ïîäñ÷åòà ðåéòèíãà, âîñïðîèçâåäåíèå èíòåðåñíûõ èñòîðè÷åñêèõ ìàò÷åé. 4 Îôîðìëåíèå èãðû, êîíå÷íî, ïðèâëåêàåò ïîòåíöèàëüíîãî ïîêóïàòåëÿ. Íî äëÿ ïðîôåññèîíàëîâ óâëå÷åíèå íå áóäåò äîëãèì, åñëè ïðîãðàììà "ïëîõî èãðàåò". Ïîýòîìó îñòàâèì âîïðîñ äèçàéíà øàõìàòíûõ ïðîãðàìì â ñòîðîíå, à îáðàòèì âíèìàíèå èìåííî íà ñðåäñòâà, êîòîðûìè äîñòèãàåòñÿ ïðèåìëåìîå êà÷åñòâî èãðû. Ìîæíî ñ óâåðåííîñòüþ ñêàçàòü, ÷òî, íåñìîòðÿ íà ìðà÷íûå ïðîãíîçû, ïðîãðàììèðîâàíèå øàõìàò îïðàâäûâàåò ñåáÿ: ïàëüìà ïåðâåíñòâà â ýòîé èãðå, òðàäèöèîííî òðåáóþùåé îò èãðîêà íàëè÷èÿ îïðåäåëåííîãî èíòåëëåêòà, òåïåðü ïðèíàäëåæèò êîìïüþòåðó. 5 Ïðîòèâíèêè êîìïüþòåðíûõ ãðîññìåéñòåðîâ ãîâîðÿò, ÷òî â øàõìàòàõ åñòü ÷òî-òî òàêîå, äëÿ "ïîíèìàíèÿ" ÷åãî íà ìàøèíå íåîáõîäèìî ïðîìîäåëèðîâàòü íåêîòîðûå ñóãóáî ÷åëîâå÷åñêèå êà÷åñòâà, êîòîðûå íåâîçìîæíî ôîðìàëèçîâàòü. Òîãäà ñòîèò ëè âîîáùå çàíèìàòüñÿ èãðîâûì ïðîãðàììè1 2

c Softwaretoolworks, 1986 ã. Íàïðèìåð, Chess Master 2000 ° c Interplay, Íàïðèìåð, îäíà èç ïîïóëÿðíûõ øàõìàòíûõ ïðîãðàìì - Battle Chess, ° 1988 ã.  ïðè âçÿòèè ôèãóðû ðàçûãðûâàåò ïåðåä çðèòåëåì äîâîëüíî êðîâàâóþ ñöåíó áîÿ. 3 c IntraCorp Inc., 1995 ã. Íàïðèìåð, ïðîãðàììà Grand Master Champion Chess, ° 4 c Expert Software Inc., Õîðîøèé ïðèìåð òîìó  ïðîãðàììà Championship Chess, ° 1995 ã. Ïðîãðàììà î÷åíü çðåëèùíà, óìíà è óìååò "÷åëîâå÷åñêèì ãîëîñîì" ñîîáùàòü î õîäå ïàðòèè. 5 Êàê èçâåñòíî, "Deep thought" îáûãðàë(à) Ã. Êàñïàðîâà. È â ýòîì íåò íè÷åãî ñòðàøíîãî, ïðîñòî èíæåíåðû "íàó÷èëèñü" ëó÷øå âñåõ "èãðàòü â øàõìàòû".

2

ðîâàíèåì? Íåêîòîðûå ìíåíèÿ ïî ýòèì âîïðîñàì êðàòêî îñâåùåíû â [1]. Ñî äíÿ âûõîäà ýòîé êíèãè ïðîøëî îêîëî ñåìè ëåò, è ñ ñåãîäíÿøíèõ ïîçèöèé äîâîëüíî õîðîøî ïðîñëåæèâàåòñÿ ýâîëþöèÿ âçãëÿäîâ íà ýòè ïðîáëåìû. Òàê, ñîïîñòàâëåíèå ïðèâåäåííûõ â êíèãå ôàêòîâ è âûñêàçûâàíèé ñ ñåãîäíÿøíèì ïîëîæåíèåì âåùåé ïîçâîëÿåò ñäåëàòü îïðåäåëåííûé âûâîä  î òîì, ÷òî, ñêîðåå âñåãî, øàíñîâ íà óñïåõ áîëüøå ó "îïòèìèñòè÷åñêîãî" âçãëÿäà íà øàõìàòíîå ïðîãðàììèðîâàíèå. Òî åñòü âçãëÿäà, ñîãëàñíî êîòîðîìó âîçìîæíî ñîçäàíèå èñêóññòâåííîãî øàõìàòíîãî ãåíèÿ  òàêîãî, ÷òî îáûãðàòü åãî ïðîñòîìó ñìåðòíîìó óæå íå ïîä ñèëó.  âûøåíàçâàííîé êíèãå Â. Ïåêåëèñ ñòàâèò äåñÿòü âîïðîñîâ, êàñàþùèõñÿ øàõìàò è èõ ïðîãðàììèðîâàíèÿ 6 :

• ÷òî òàêîå øàõìàòû? • êàêèì äîëæåí áûòü ãðîññìåéñòåð ñåãîäíÿ? • ÷òî íîâîãî â øàõìàòàõ? • ìîæíî ëè àâòîìàòèçèðîâàòü øàõìàòíóþ èãðó? • êàê ìàøèíà èãðàåò â øàõìàòû? • êàê ìàøèíà ñûãðàëà ñ ÷åëîâåêîì? • ÷òî ãîâîðÿò î ìàøèííîé èãðå øàõìàòèñòû? • à êàê ìàøèíà èãðàåò ñ ìàøèíîé? • íå ïåðåèãðàþò ëè ìàøèíû âñå øàõìàòíûå ïàðòèè? • êàêîå áóäóùåå æäåò øàõìàòû? Âûÿñíèì, ñ ÷åì æå èìåþò äåëî ðàçðàáîò÷èêè øàõìàòíûõ ïðîãðàìì è øàõìàòíûõ êîìïüþòåðîâ. Âîò îòâåòû íà âîïðîñ "÷òî òàêîå øàõìàòû?" ÷åìïèîíîâ ìèðà ðàçíûõ ëåò:

• "èñêóññòâî" (Ì. Áîòâèííèê); • "áîðüáà ÷åëîâå÷åñêèõ õàðàêòåðîâ" (Â. Ñìûñëîâ); • "ñïîðò" (À. Êàðïîâ); • "ãîðàçäî áîëüøå, ÷åì ñïîðò" (Ã. Êàñïàðîâ). 6

Ñì. [1], ñòð. 160169.

3

Çàìåòèì, ÷òî øàõìàòàì, ñîãëàñíî ìíåíèþ ìàñòåðîâ, ïðèñóùè ÷åðòû, âî ìíîãîì õàðàêòåðíûå ñóãóáî èíòåëëåêòóàëüíîé ñôåðå äåÿòåëüíîñòè ÷åëîâåêà. Åñëè ýòî äåéñòâèòåëüíî òàê, òî, ïîêà íå ðàçãàäàíà ïðèðîäà ÷åëîâå÷åñêîãî ìûøëåíèÿ, â ìîäåëèðîâàíèè øàõìàò è ìíîãèõ äðóãèõ èãð ïðèäåòñÿ äâèãàòüñÿ "íàïðîëîì", èñïîëüçóÿ äëÿ ïîâûøåíèÿ êà÷åñòâà èãðû, â îñíîâíîì, âñå ðàñòóùèå âû÷èñëèòåëüíûå ìîùíîñòè ñîâðåìåííûõ êîìïüþòåðîâ. Äåéñòâèòåëüíî, ïðîñëåæèâàÿ èñòîðèþ ìîäåëèðîâàíèÿ èãð, ìîæíî çàìåòèòü, ÷òî ìåíÿåòñÿ, â îñíîâíîì, íå îáùèé ïðèíöèï ìåòîäîâ ïîèñêà ðåøåíèé, à, ñêîðåå, ìîùíîñòü âû÷èñëèòåëüíûõ ñðåäñòâ è ñêîðîñòü àëãîðèòìîâ, êîòîðûìè îñóùåñòâëÿåòñÿ ýòîò ïîèñê. È ïðèâîäèìûé â íàñòîÿùåé ñòàòüå ìåòîä òàêæå íå ïðåòåíäóåò íà ïåðåâîðîò â èãðîâîì ïðîãðàììèðîâàíèè. Íàèáîëåå èíòåðåñíû îòâåòû íà âîïðîñ "ìîæíî ëè àâòîìàòèçèðîâàòü øàõìàòíóþ èãðó?" À. Ïóàíêàðå êàòåãîðè÷åí: "Ìàòåìàòè÷åñêîé øàõìàòíîé òåîðèè íå ñóùåñòâóåò è íå ìîæåò áûòü ñîçäàíî". Ì. Òàëü òîæå íå ïðèâåòñòâóåò "ýëåêòðîííûõ øàõìàòèñòîâ". Îí àêöåíòèðóåò âíèìàíèå íà ïðèñóòñòâèè â øàõìàòíîé èãðå ýëåìåíòà òâîð÷åñòâà, êîòîðîå íå ìîæåò áûòü óíèôèöèðîâàíî. Òàêæå îí ãîâîðèò î íåïðàâîìåðíîñòè ñîèçìåðåíèÿ øàõìàòíîé èãðû è øàõìàòíîé êèáåðíåòèêè. Ì. Áîòâèííèê, íàïðîòèâ, ãîâîðèò î âîçìîæíîñòè àâòîìàòèçàöèè èãðû, íî ïðè î÷åíü ñèëüíîì óñëîâèè  ìàøèíó äîëæíû íàó÷èòü "÷åëîâå÷åñêîìó ñïîñîáó" èãðû. 7  íàñòîÿùèé ìîìåíò äî ýòîãî åùå äàëåêî. Ïðîãðàììèðîâàíèå øàõìàò ìíîãèå øàõìàòèñòû è ñåé÷àñ âîñïðèíèìàþò êàê òóïèêîâîå íàïðàâëåíèå. Öåëüþ ïðèâåäåííîãî âûøå êðàòêîãî îáçîðà "øàõìàòíîãî ôðîíòà" ÿâëÿåòñÿ ïîïûòêà ïîêàçàòü ñóùåñòâîâàíèå îñìûñëåííîñòè ïðîãðàììèðîâàíèÿ èíòåëëåêòóàëüíûõ èãð è äàòü ñàìîå îáùåå ïðåäñòàâëåíèå î ïðîáëåìàõ, âîçíèêàþùèõ íà ïóòè ñîçäàíèÿ ñèëüíûõ èãðàþùèõ ïðîãðàìì. Òåì áîëåå, â ïðîãðàììèðîâàíèè øàõìàò óæå èìåþòñÿ îïðåäåëåííûå óñïåõè. Êàê óæå îòìå÷àëîñü, øàõìàòíûé ñóïåðêîìïüþòåð "Deep thought" âûèãðàë ìèíè-ìàò÷ ó ÷åìïèîíà ìèðà Ã. Êàñïàðîâà. Ïðîãðàììèñòû è èíæåíåðû îáðàùàþò âíèìàíèå íà òî, ÷òî íåñìîòðÿ íà çàÿâëåíèå ïðîèãðàâøåé ñòîðîíû, â ïðîãðàììå íå ó÷èòûâàëèñü èíäèâèäóàëüíûå õàðàêòåðèñòèêè Êàñïàðîâà è òàêòè÷åñêèå îñîáåííîñòè åãî èãðû. Êîìïüþòåð "âçÿë" ñâîåé âû÷èñëèòåëüíîé ìîùüþ, îïèðàÿñü íà ìèíèìàêñíóþ ñòðàòåãèþ âûáîðà õîäà, íåêîòîðûå ýâðèñòè÷åñêèå ïðàâèëà, ïðèìåíÿåìûõ â èãðå ñ ëþáûì ïðîòèâíèêîì è íà öåëûé ñîíì ïðîöåññîðîâ è 7 Ñì. ðàáîòó Ì. Áîòâèííèêà "Ëþäè è ìàøèíû çà øàõìàòíîé äîñêîé" â ñáîðíèêå [2] (ñòð. 226).

4

øàõìàòíûõ àêñåëåðàòîðîâ. Îñòàíîâèìñÿ òåïåðü íà òðàäèöèîííûõ ìåòîäàõ ïîèñêà ñòðàòåãèè â äåòåðìèíèðîâàííûõ àíòàãîíèñòè÷åñêèõ èãðàõ.

1.2

Îñíîâíûå ïîíÿòèÿ â ïðîãðàììèðîâàíèè èãð

Èòàê, â äåòåðìèíèðîâàííûõ èãðàõ èçâåñòåí ïåðåáîðíûé ìåòîä íàõîæäåíèÿ õîðîøåé ñòðàòåãèè. Îïðåäåëÿåìàÿ äàííûì ìåòîäîì ñòðàòåãèÿ ìîæåò áûòü áëèçêîé ê îïòèìàëüíîé. Ïîäðîáíîå îïèñàíèå ìåòîäà ìîæíî óâèäåòü â [3]. Ìåòîä, ïðåäëîæåííûé â ýòîé êíèãå, èçâåñòåí êàê ìåòîä ìèíèìàêñà è îñíîâàí íà ìèíèìàêñíîé ñòðàòåãèè îïðåäåëåíèÿ íàèëó÷øåãî õîäà â äåòåðìèíèðîâàííîé àíòàãîíèñòè÷åñêîé èãðå. Ìåòîä ìèíèìàêñà îñíîâàí íà ìîäåëèðîâàíèè ïîâåäåíèÿ èãðàþùèõ ñòîðîí ïóòåì ïåðåáîðà âàðèàíòîâ ðàçâèòèÿ èãðû.  áîëüøèíñòâå ñëó÷àåâ íåâîçìîæíî ïðîèçâåñòè ïîëíûé ïåðåáîð. ×òîáû îãðàíè÷èòü êîëè÷åñòâî âàðèàíòîâ, äåðåâî èãðû ïðîñìàòðèâàþò íå ïîëíîñòüþ, à òîëüêî íà îïðåäåëåííîå ÷èñëî õîäîâ âïåðåä, òî åñòü íà íåêîòîðóþ ôèêñèðîâàííóþ ãëóáèíó, íàçûâàåìóþ ãëóáèíîé ïåðåáîðà. Ïðè ýòîì âûáèðàþò òàêîé õîä (îïòèìàëüíóþ, ñ òî÷êè çðåíèÿ ìèíèìàêñà, ñòðàòåãèþ), ïðè êîòîðîì âîçìîæíûå ïîòåðè (åñòåñòâåííî, â ïðåäåëàõ óñòàíîâëåííîé ãëóáèíû ïåðåáîðà) áóäóò ìèíèìàëüíûìè, ïîëàãàÿ, ÷òî ñîïåðíèê ïðåñëåäóåò ïðÿìî ïðîòèâîïîëîæíóþ öåëü  ñäåëàòü ïîòåðè ñâîåãî ïðîòèâíèêà ìàêñèìàëüíûìè (îòñþäà è íàçâàíèå  ìåòîä "ìèíèìàêñà"). Ïîäîáíàÿ ýâðèñòèêà äàåò òåì ëó÷øèé ðåçóëüòàò, ÷åì áîëüøå ãëóáèíà ïåðåáîðà. ×òîáû èçáåæàòü èñïîëüçîâàíèÿ î÷åíü áîëüøîé ãëóáèíû ïåðåáîðà, íî ñîõðàíèòü êà÷åñòâî èãðû, â îöåíî÷íóþ ôóíêöèþ ââîäÿòñÿ äîïîëíèòåëüíûå óñëîâèÿ. Íàïðèìåð, â øàøêàõ ïðè ïîñëåäîâàòåëüíîì âçÿòèè íåîáõîäèìî ïðîñìàòðèâàòü òàêîå "îïàñíîå" ïîääåðåâî íà á
îëüøóþ ãëóáèíó èëè ïðîäîëæàòü "ïîãðóæåíèå" â íåãî, ïîêà îöåíî÷íàÿ ôóíêöèÿ íå ñòàáèëèçèðóåòñÿ. Ðàññìîòðèì îáùèå ïðèíöèïû ïîñòðîåíèÿ îöåíî÷íûõ ôóíêöèé áîëåå ïîäðîáíî.  ìåòîäå ìèíèìàêñà êàæäûé èãðîê èìååò ñâîþ îöåíî÷íóþ ôóíêöèþ.  ïðîñòåéøåì ñëó÷àå îíà ïðîñòî óêàçûâàåò êîëè÷åñòâåííûé ïåðåâåñ êàêîãî-òî èãðîêà.  àíòàãîíèñòè÷åñêèõ èãðàõ ñóììà îöåíî÷íûõ ôóíêöèé âñåõ èãðîêîâ äîëæíà áûòü ðàâíîé íóëþ. Âìåñòî èíäèâèäóàëüíûõ îöåíî÷íûõ ôóíêöèé ìîæíî èñïîëüçîâàòü îäíó îöåíî÷íóþ ôóíêöèþ íà âñåõ.  ñëó÷àå äâóõ èãðàþùèõ  îäèí èç èãðîêîâ äîëæåí åå ìàêñèìèçèðîâàòü, à äðóãîé  ìèíèìèçèðîâàòü. Ýòîãî ïðèíöèïà è ïðèäåðæèâàåòñÿ àëãîðèòì ìèíèìàêñà â ñâîåé ðàáîòå. ( Ïîäîáíûé ïîäõîä ïðèìåíèì òàêæå è äëÿ àíòàãîíèñòè÷åñêîé èãðû íåñêîëüêèõ ëèö.) 5

Êàê óæå îòìå÷àëîñü, îöåíî÷íàÿ ôóíêöèÿ ïîêàçûâàåò ñòåïåíü ïðèâëåêàòåëüíîñòè òîé èëè èíîé ïîçèöèè. Ïîýòîìó â íåå äîëæíà âõîäèòü íå òîëüêî ìåðà êîëè÷åñòâåííîãî ïåðåâåñà êîíêðåòíîãî èãðîêà. Òàê, âî ìíîãèõ èãðàõ â îöåíî÷íóþ ôóíêöèþ âõîäèò ðÿä ïàðàìåòðîâ, îöåíèâàþùèõ ïîçèöèþ â ñòðàòåãè÷åñêîì ïëàíå. Íàïðèìåð, â øàøêàõ â íåå ìîæåò âõîäèòü ïàðàìåòð, îòðàæàþùèé ñòåïåíü êîíòðîëÿ íàä öåíòðîì, çàíÿòîñòü ãëàâíîé äèàãîíàëè è ìíîãîå äðóãîå.  øàõìàòàõ â îöåíî÷íóþ ôóíêöèþ âõîäèò åùå áîëüøå ðàçëè÷íûõ ïàðàìåòðîâ, áîëüøèíñòâî èç êîòîðûõ îáîñíîâûâàþòñÿ ÷èñòî ýâðèñòè÷åñêè. Âñå ýòî äåëàåòñÿ äëÿ áîëåå òî÷íîé îöåíêè ïîçèöèè. Åñëè áû îöåíî÷íàÿ ôóíêöèÿ íå îòðàæàëà âñå ýòè íþàíñû, äëÿ ïîëó÷åíèÿ ñèëüíîé èãðû ïðèõîäèëîñü áû èññëåäîâàòü äåðåâî èãðû íà á
îëüøóþ ãëóáèíó, ÷òî ÷àñòî ñòîèò î÷åíü äîðîãî. Äëÿ èçó÷åíèÿ âèäà îöåíî÷íîé ôóíêöèè òàêæå èñïîëüçóþò íåêîòîðûå âñïîìîãàòåëüíûå, òàê íàçûâàåìûå ñàìîîáó÷àþùèåñÿ ïðîãðàììû.  íèõ îöåíî÷íàÿ ôóíêöèÿ ÷àñòî çàäàåòñÿ â äîâîëüíî îáùåì âèäå. Òàê, â îöåíî÷íóþ ôóíêöèþ ââîäÿòñÿ íåêîòîðûå ïàðàìåòðû, çàâèñÿùèå, íàïðèìåð, îò ðàñïîëîæåíèÿ ôèãóð è îò êîíôèãóðàöèè äåðåâà èãðû. Êàæäûé ïàðàìåòð âõîäèò â îöåíî÷íóþ ôóíêöèþ ñî ñâîèì âåñîì. Ñàìîîáó÷åíèå çàêëþ÷àåòñÿ â ýêñïåðèìåíòàëüíîì "óëó÷øåíèè" îöåíî÷íîé ôóíêöèè ïóòåì ïîäáîðà âåñîâ. Îäíèì èç ïðèìåðîâ ñàìîîáó÷àþùåéñÿ ïðîãðàììû ÿâëÿåòñÿ ïðîãðàììà äëÿ èãðû â àìåðèêàíñêèå øàøêè (àâòîð  èçâåñòíûé àìåðèêàíñêèé èíæåíåð, À. Ñàìóýëü).  ïðîöåññå èãðû ïðîãðàììà ôèêñèðóåò äîïóùåííûå îøèáêè è áîëüøå èõ íå ïîâòîðÿåò. Òàêæå â ïðîöåññå ñàìîîáó÷åíèÿ èçìåíÿþòñÿ êîýôôèöèåíòû îöåíî÷íîé ôóíêöèè è áàçà äàííûõ ïî ïðîøëûì èãðàì.  ðåçóëüòàòå ïîïîëíåíèÿ áàçû äàííûõ, êîððåêöèè è ââîäà íîâûõ êîýôôèöèåíòîâ â îöåíî÷íóþ ôóíêöèþ, äðóãèìè ñëîâàìè  ñàìîîáó÷åíèÿ, ýòà ïðîãðàììà ñòàëà îáûãðûâàòü äàæå ïðèçíàííûõ ÷åìïèîíîâ íà âû÷èñëèòåëüíûõ ìàøèíàõ, äîñòóïíûõ â 1960-õ ãîäàõ. Ïîäîáíûå ïðèåìû âñòðå÷àþòñÿ è ñðåäè ìíîãèõ äðóãèõ èãðîâûõ ïðîãðàìì. ×àñòî ñàìîîáó÷àþùåéñÿ ñèñòåìå äëÿ îáó÷åíèÿ äîñòàòî÷íî ëèøü ñàìîé ñåáÿ. Ïðîãðàììà ìîæåò "ñîâåðøåíñòâîâàòüñÿ", èãðàÿ ñàìà ñ ñîáîþ îäíó ïàðòèþ çà äðóãîé â òå÷åíèå äëèòåëüíîãî âðåìåíè. Ïðèìåðû, êàñàþùèåñÿ ýâðèñòè÷åñêèõ ìîìåíòîâ ïîñòðîåíèÿ îöåíî÷íûõ ôóíêöèé, ñíîâà ìîæíî íàéòè â [1, 2]. Òàê, óïîìèíàåòñÿ ñòðàòåãèÿ øàõìàòíîé ïðîãðàììû "Ïèîíåð". Ñóòü åå â òîì, ÷òîáû èñêëþ÷èòü èç àíàëèçà çàâåäîìî ñëàáûå õîäû îñòàâëÿÿ, òåì ñàìûì, ðàçóìíûå âàðèàíòû. Ó "Ïèîíåðà", çàìå÷àåò Ì.Áîòâèííèê, â äåðåâå ïåðåáîðà, êàê è ó øàõìàòîãî ìàñòåðà, íåñêîëüêî äåñÿòêîâ õîäîâ. Òàì æå íàõîäèì åùå îäèí ïðèìåð ýâðèñòèêè, ïðåäîñòàâëåííîé àêàäå6

ìèêîì Í. ßíåíêî: " íàøåì àëãîðèòìå çàëîæåíà èäåÿ ïîäñòàíîâêè äèíàìè÷åñêîãî áàðüåðà. È äâèæåíèÿ ýòîãî áàðüåðà â òàêîì íàïðàâëåíèè, ÷òîáû ìàêñèìàëüíî îãðàíè÷èòü ñâîáîäó íåïðèÿòåëüñêîãî êîðîëÿ. . . Ìû èñïîëüçîâàëè òàêîå ìàòåìàòè÷åñêîå ïîíÿòèå, êàê ðåëüåô øàõìàòíîé äîñêè, îçíà÷àþùåå íåêóþ ìåðó ïîäâèæíîñòè íåïðèÿòåëüñêîãî êîðîëÿ. Öåíòð äîñêè ñîîòâåòñòâóåò âåðøèíå ðåëüåôà, à êðàÿ  îñíîâàíèÿì. . . Ñ ïîìîùüþ äèíàìè÷åñêîãî áàðüåðà ìû ïîíèæàåì óðîâåíü êîðîëÿ, ñãîíÿÿ ñ âåðøèíû ê îñíîâàíèþ."

2 Ñïåöèàëüíîå îïèñàíèå ìåòîäà ìèíèìàêñà Ïðèâåäåì ñïåöèàëüíîå êðàòêîå îïèñàíèå ìåòîäà ìèíèìàêñà, îáîáùàåìîãî â ñëåäóþùåì ðàçäåëå. Äëÿ ýòîãî ðàññìîòðèì áîëåå ïîäðîáíî ïðîöåññ âûáîðà õîäà. Äëÿ íåêîòîðîé äåòåðìèíèðîâàííîé àíòàãîíèñòè÷åñêîé èãðû äâóõ èãðîêîâ î÷åðåäíîñòü õîäîâ è ïðîöåññ âûáîðà îïòèìàëüíîãî õîäà ìîæíî íàãëÿäíî ïðåäñòàâèòü â âèäå áèíàðíîãî äåðåâà èãðû. Êîðåíü ýòîãî äåðåâà ñîîòâåòñòâóåò ñòàðòîâîé ïîçèöèè, ñ êîòîðîé íà÷èíàåòñÿ èãðà. Ðåáðà, ñîåäèíÿþùèå êîðíåâóþ âåðøèíó äåðåâà ñ âåðøèíàìè ñëåäóþùåãî óðîâíÿ, ñîîòâåòñòâóþò âîçìîæíûì õîäàì èç ñòàðòîâîé ïîçèöèè. Âåðøèíû äåðåâà îòâå÷àþò ïîçèöèÿì, ïîëó÷àþùèìñÿ ïîñëå ñîâåðøåíèÿ ñîîòâåòñòâóþùåãî õîäà. Íà êîíêðåòíîì óðîâíå äåðåâà õîä ïðèíàäëåæèò êîíêðåòíîìó èãðîêó. Íàïðèìåð, ïðè èãðå â øàõìàòû íà íóëåâîì óðîâíå (óðîâåíü, êîòîðîìó ïðèíàäëåæèò êîðåíü äåðåâà) õîä äîëæíû äåëàòü áåëûå, íà ïåðâîì (ñëåäóþùåì) óðîâíå õîä ïðèíàäëåæèò ÷åðíûì è òàê äàëåå. ( Ïîäîáíîå ïðîèñõîäèò è ïðè èãðå íåñêîëüêèõ ëèö.) Ãîâîðÿò, ÷òî âåðøèíà äåðåâà èãðû ÿâëÿåòñÿ âåðøèíîé ñ õîäîì áåëûõ (÷åðíûõ), åñëè î÷åðåäü õîäà íà óðîâíå, ñîîòâåòñòâóþùåì ýòîé âåðøèíå, ïðèíàäëåæèò áåëûì (÷åðíûì). Ìåðó âûãîäíîñòè èãðîâîé ïîçèöèè îòíîñèòåëüíî îäíîé èç ñòîðîí è, çàîäíî, ïîìåòêó êàæäîãî ëèñòà â äåðåâå èãðû çàäàåò îöåíî÷íàÿ ôóíêöèÿ, êîòîðóþ îäíà ñòîðîíà ìèíèìèçèðóåò, à äðóãàÿ ìàêñèìèçèðóåò. Ïðè ýòîì äîëæíî âûïîëíÿòüñÿ òðåáîâàíèå àíòàãîíèñòè÷íîñòè: äëÿ îäíîé è òîé æå èãðîâîé ïîçèöèè ñóììà îöåíî÷íûõ ôóíêöèé ñòîðîí äîëæíà ðàâíÿòüñÿ íóëþ. Òî åñòü, ñêîëüêî âûèãðàëà îäíà ñòîðîíà, ñòîëüêî ïðîèãðàëà äðóãàÿ. Åñëè òàêîå ñâîéñòâî èìååò ìåñòî, òî ñîîòâåòñòâóþùàÿ èãðà íàçûâàåòñÿ èãðîé ñ íóëåâîé ñóììîé èëè àíòàãîíèñòè÷åñêîé èãðîé. À åñëè íà õîä èãðû íå îêàçûâàþò âëèÿíèå íåêîòîðûå ñëó÷àéíûå ôàêòîðû, òî òàêàÿ èãðà ÿâëÿåòñÿ äåòåðìèíèðîâàííîé.  ìåòîäå ìèíèìàêñà äëÿ îöåíêè ïîçèöèé, íå ÿâëÿþùèõñÿ ëèñòüÿìè 7

~ Πk  íåêîòîðàÿ ïîçèöèÿ ,l l gk,2 gk,1 , , l , l âàðèàíòû õîäîâ , l ïîçèöèè ïîñëå õîäà l~Πk,2 , ~Πk,1 ¢A ¢A ¢ A âàðèàíòû õîäîâ ¢ A A gk,2,2 A gk,1,2 gk,1,1 ¢ gk,2,1 ¢ ¢ A ¢ A A~ A~ ¢ ¢ ~ ~ £B £B £B £B £ B £ B £ B £ B âàðèàíòû õîäîâ £ B £ B £ B £ B £ B £ B £ £ B B £} B} £} B} £} B} £} B} ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦v Ev ¦v Ev ¦v Ev ¦v Ev ¦v Ev ¦v Ev ¦v Ev ¦v Ev

Ðèñ. 1: Îáîçíà÷åíèÿ â äåòåðìèíèðîâàííîì äåðåâå ïåðåáîðà

äåðåâà èãðû, èñïîëüçóåòñÿ "äèíàìè÷åñêàÿ" îöåíêà. Ýòó îöåíêó îïèøåì ñëåäóþùèì îáðàçîì: äèíàìè÷åñêàÿ îöåíêà êîíêðåòíîé âåðøèíû A ñ õîäîì ÷åðíûõ (áåëûõ) ïîëó÷àåòñÿ ìèíèìèçàöèåé (ìàêñèìèçàöèåé) äèíàìè÷åñêèõ îöåíîê âåðøèí ïåðâîãî óðîâíÿ èç ïîääåðåâà äåðåâà èãðû, ó êîòîðîãî â êà÷åñòâå êîðíåâîé âåðøèíû âûñòóïàåò âåðøèíà A. Ïðîöåññ âûáîðà ñòðàòåãèè ìåòîäîì ìèíèìàêñà ìîæíî îïèñàòü áîëåå ñòðîãî. Ïóñòü ω(Πk )  çíà÷åíèå îöåíî÷íîé ôóíêöèè íà ïîçèöèè Πk , à Πki  ïîçèöèÿ, ïîëó÷àþùàÿñÿ èç Πk ïîñëå õîäà gki . 8 Äàëåå,

Gk =

[ {Πki }.  ìíîæåñòâî âñåõ "äî÷åðíèõ" ïîçèöèé Πk i

Gkl =

[ {Πkli }. i

Ñòðîèì îöåíî÷íóþ ôóíêöèþ äëÿ ïîçèöèè Πk1 ...kn , îïèðàÿñü íà Gk1 ...kn : 8 Ñì. ðèñ. 1, íà íåì ïðåäñòàâëåí ôðàãìåíò äåðåâà, â êîòîðîì èç êàæäîé âåðøèíû âîçìîæíû òîëüêî 2 õîäà.

8

    W (Gk1 ...kn ) =

  

min

V (Π)

ïðè níå÷åòíîì

max

V (Π)

ïðè n÷åòíîì

Π∈Gk1 ...kn Π∈Gk1 ...kn

ω(Πk1 ,...,kn ),

ïðè Gk1 ,...,kn = ∅

Ñàìà îöåíî÷íàÿ ôóíêöèÿ

V (Πk1 ...kn ) = W (Gk1 ...kn ) . Òåïåðü â êà÷åñòâå îïòèìàëüíîãî õîäà ìîæíî èçáðàòü õîä gi , êîòîðûé âåäåò îò ïîçèöèè Πk ê ïîçèöèè Πki , ïðè÷åì V (Πki ) = V (Πk ).  äåðåâå èãðû âåðøèíàì n-ãî óðîâíÿ ñîîòâåòñòâóþò ïîçèöèè Πk1 ...kn−1 , à ðåáðàì, âåäóùèì ê ýòèì âåðøèíàì  õîäû.

3 Îáîáùåíèå ìåòîäà ìèíèìàêñà â íåäåòåðìèíèðîâàííîì ñëó÷àå  ýòîì ðàçäåëå ïðåäëàãàåòñÿ ìåòîä äëÿ íàõîæäåíèÿ ñòðàòåãèè, áëèçêîé ê îïòèìàëüíîé, â íåäåòåðìèíèðîâàííîì ñëó÷àå. Äàííûé ìåòîä ÿâëÿåòñÿ íåêîòîðûì îáîáùåíèåì ìåòîäà ìèíèìàêñà. Îí, êàê è ìåòîä ìèíèìàêñà, ïðîèçâîäèò ïîèñê íóæíîé ñòðàòåãèè ïóòåì ïåðåáîðà âàðèàíòîâ ðàçâèòèÿ èãðû, âûáèðàÿ ïðè ýòîì õîä, êîòîðûé èìååò íàèëó÷øóþ, ñïåöèàëüíûì îáðàçîì ïîñòðîåííóþ îöåíêó. Î÷åíü êðàòêîå îïèñàíèå ýòîãî ìåòîäà ñì. â [5]. Ñëó÷àéíûå ôàêòîðû, ñóùåñòâåííî âëèÿþùèå íà èãðó  ýòî øóì. Èìèòàòîð øóìà  ýòî àëãîðèòì, ãåíåðèðóþùèé ñåðèè ïñåâäîñëó÷àéíûõ ÷èñåë ñ çàäàííûìè õàðàêòåðèñòèêàìè. Äëÿ äîñòàòî÷íî ïîëíîãî ïîñòðîåíèÿ èìèòàòîðà øóìà íåîáõîäèìî çàäàòü íåêîòîðûå åãî ñóùåñòâåííûå õàðàêòåðèñòèêè. Èõ ìîæíî ïîëó÷èòü èç ýêñïåðèìåíòàëüíûõ íàáëþäåíèé. Õàðàêòåðèñòèêè ïîñòðîåííîãî äëÿ èãðû èìèòàòîðà äîëæíû ñîîòâåòñòâîâàòü õàðàêòåðèñòèêàì èìèòèðóåìûõ ñëó÷àéíûõ ïðîöåññîâ. Ðàññìîòðèì ðàáîòó íîâîãî àëãîðèòìà íà ïðèìåðå èãðû, â êîòîðîé ÷åðåäóþòñÿ: êîíêðåòíàÿ ðåàëèçàöèÿ íåêîòîðîãî ñëó÷àéíîãî ñîáûòèÿ, õîä îäíîé èç ñòîðîí, ñíîâà ðåàëèçàöèÿ ñëó÷àéíîãî ñîáûòèÿ, õîä äðóãîé ñòîðîíû. Êîëè÷åñòâî âñåâîçìîæíûõ èñõîäîâ ñëó÷àéíîãî ñîáûòèÿ äîëæíî áûòü êîíå÷íûì. Ïðèìåðîì òàêîé èãðû ìîãóò ñëóæèòü êîðîòêèå íàðäû, â êîòîðûõ õîä êàæäîé èç ñòîðîí îñóùåñòâëÿåòñÿ â çàâèñèìîñòè îò çíà÷åíèé, âûïàâøèõ íà äâóõ êóáèêàõ.  ðåçóëüòàòå, â äåðåâå èãðû ïîÿâëÿþòñÿ óðîâíè, çàêëþ÷åííûå ìåæäó óðîâíÿìè î÷åðåäíîñòè õîäîâ ñî9

ïåðíèêîâ. Ýòè íîâûå óðîâíè îòðàæàþò òå ìîìåíòû èãðû, â êîòîðûå ðåàëèçóåòñÿ èñõîä ñëó÷àéíîãî ñîáûòèÿ. Ïðåäëàãàåìîå â íàñòîÿùåé ðàáîòå îáîáùåíèå ìåòîäà ìèíèìàêñà ðàáîòàåò èìåííî ñ òàêèì äåðåâîì. Ïðåäâàðèòåëüíûå îöåíêè ïîçèöèé äåðåâà èãðû ïîëó÷àþòñÿ, åñëè ìîæíî òàê âûðàçèòüñÿ, âðåìåííûì "óäàëåíèåì" íåäåòåðìèíèðîâàííîñòè. Äëÿ ýòîãî ìû ñíà÷àëà ïðåäïîëàãàåì, ÷òî óæå ðåàëèçîâàëñÿ êîíêðåòíûé èñõîä ñëó÷àéíîãî ñîáûòèÿ è âû÷èñëÿåì äèíàìè÷åñêóþ îöåíêó äëÿ îöåíèâàåìîé ïîçèöèè òàê æå, êàê è â ìåòîäå ìèíèìàêñà. Çàòåì âû÷èñëÿåì äèíàìè÷åñêóþ îöåíêó ïîçèöèè äëÿ ñëåäóþùåãî èñõîäà ñëó÷àéíîãî ñîáûòèÿ è òàê äàëåå äëÿ âñåõ èñõîäîâ. Îêîí÷àòåëüíàÿ äèíàìè÷åñêàÿ îöåíêà ïîçèöèè îïðåäåëÿåòñÿ íà îñíîâå âñåõ äåòåðìèíèðîâàííûõ îöåíîê, ïîëó÷åííûõ äëÿ âñåõ âîçìîæíûõ çíà÷åíèé ñëó÷àéíîãî ñîáûòèÿ. Ïîëó÷åííûå çíà÷åíèÿ äåòåðìèíèðîâàííûõ îöåíîê ñïåöèàëüíûì îáðàçîì óñðåäíÿþòñÿ . Ýòî è åñòü ïîñòðîåííàÿ îñîáûì îáðàçîì îöåíêà. Ñ ôèçè÷åñêîé òî÷êè çðåíèÿ òàêîå óñðåäíåíèå äàåò ïîëîæåíèå öåíòðà òÿæåñòè îäíîìåðíîé ñèñòåìû òåë ñ ìàññàìè, îïðåäåëÿåìûìè ñïåöèàëüíî ïîäîáðàííîé ôóíêöèåé (ôóíêöèåé ðèñêà) . Êîîðäèíàòû òåë ñèñòåìû  çíà÷åíèÿ ñîîòâåòñòâóþùåé "äåòåðìèíèðîâàííîé" îöåíêè, êîòîðàÿ îïðåäåëÿåòñÿ òîëüêî äåòåðìèíèðîâàííûìè ôàêòîðàìè èãðû êàê, íàïðèìåð, â ìèíèìàêñå: 

n  P φ1 φk f (φk )  ..  k=1 . Z . = n P f (φk ) φn k=1

Çäåñü φk ñîîòâåòñòâóþò çäåñü îöåíêàì âñåâîçìîæíûõ ñëó÷àéíûõ èñõîäîâ. Îöåíêà Z  îêîí÷àòåëüíàÿ (äèíàìè÷åñêàÿ) îöåíêà ïîçèöèè. Ôóíêöèÿ ðèñêà f (x) çäåñü ÿâëÿåòñÿ èíäèâèäóàëüíîé äëÿ êàæäîãî èç ñîïåðíèêîâ è â çíà÷èòåëüíîé ìåðå îïðåäåëÿåò òàêòèêó ñîîòâåòñòâóþùåãî èãðîêà. Êàê óæå îòìå÷àëîñü, íåîáõîäèìî ïðîñìàòðèâàòü òàêæå âñåâîçìîæíûå èñõîäû ñëó÷àéíîãî ñîáûòèÿ, âëèÿþùåãî íà âûáîð õîäà.  ðåçóëüòàòå äåðåâî èãðû ñèëüíî ðàçâåòâëÿåòñÿ çà ñ÷åò ðåáåð, ñîîòâåòñòâóþùèõ âñåâîçìîæíûì èñõîäàì ñëó÷àéíîãî ñîáûòèÿ. Ïîêàæåì, êàê ìîæíî ïðèìåíèòü íàøå îáîáùåíèå ìåòîäà ìèíèìàêñà. Ïóñòü ξ1 . . . ξn  âñåâîçìîæíûå èñõîäû ñëó÷àéíîãî ñîáûòèÿ. Πξkji 

ξi ïîçèöèÿ, ïîëó÷àåìàÿ èç Πk ïðè èñõîäå ξi , ïîñëå õîäà gkj . 9

9

Ïóñòü f (x) 

Ñì. ðèñ. 2, íà íåì ïðåäñòàâëåí ôðàãìåíò äåðåâà, â êîòîðîì èç êàæäîé âåðøèíû

10

z %e e %

e % e % e (Πξi ) ïîçèöèÿ ïîñëå % î÷åðåäíîãî õîäà ¨ ¥ ¥ ¨e k % z ez % § ­£BJ ¦ § ­£BJ ¦ ðàçâåòâëåíèå íà âîçìîæíûå ñëó÷àéíûå èñõîäû ­£ BJ ­£ BJ ­£ BJ ­£ BJ ξ1­ξ2£ ξ3 ξB4 ξJ5 ­ £ B J ­ £ ­ £ B J B J z ­­ z ££ z BB zJJ z z ­­ z ££ z BB zJJ z ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ¦E ξ4 ξ4 ¦ E gk,2 ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E gk,1 ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦ E ¦¦ u uEE ¦¦ u uEE ¦¦ u uEE ¦¦ u uEE ¦¦ u uEE ¦¦ u uEE ¦¦ u uEE

Ðèñ. 2: Îáîçíà÷åíèÿ â íåäåòåðìèíèðîâàííîì äåðåâå ïåðåáîðà

ëþáàÿ, îïðåäåëåííàÿ íà R ôóíêöèÿ, êîòîðóþ íàçîâåì ôóíêöèåé ðèñêà èëè âåñîâîé ôóíêöèåé. Îöåíêó ïîçèöèè Πk1 ,...,kn âû÷èñëÿåì ïî ôîðìóëå:



 n P f (W (Gξk11 ,...,kn )) {W (Gξkl1 ,...,kn ) · f (W (Gξkl1 ,...,kn ))}   ..  = l=1 W (Gk1 ,...,kn ) = Z  , . n   P ξl ξn f (W (G )) k1 ,...,kn f (W (Gk1 ,...,kn )) l=1



   x1 x1     ãäå Z  ...   öåíòð òÿæåñòè âåêòîðà  ...  . xn xn Êàê è ðàíåå, îöåíî÷íàÿ ôóíêöèÿ

V (Πk1 ,...,kn ) = W (Gk1 ,...,kn ) . âîçìîæíû òîëüêî 2 õîäà. À êîëè÷åñòâî âîçìîæíûõ ðåàëèçàöèé ñëó÷àéíîãî ñîáûòèÿ ðàâíî 5. Îáâåäåííûì â îâàë âåðøèíàì ñîîòâåòñòâóþò ìîìåíòû èãðû, â êîòîðûå ïðîèñõîäèò ðåàëèçàöèÿ ñëó÷àéíîãî ñîáûòèÿ. Äëÿ ðàáîòû íîâîãî àëãîðèòìà íåîáõîäèìî ïðîñìîòðåòü âñå ýòè ðåàëèçàöèè. Ýòî íóæíî äëÿ ïîëó÷åíèÿ çíà÷åíèÿ ôóíêöèè ðèñêà.

11

Ïóñòü "áåëàÿ" ñòîðîíà ìåòîäîì ìèíèìàêñà â êà÷åñòâå íàèëó÷øåãî õîäà âûáèðàåò õîä, âåäóùèé â ïîçèöèþ ñ ìàêñèìàëüíîé äèíàìè÷åñêîé îöåíêîé. Òîãäà ìîíîòîííî óáûâàþùàÿ ôóíêöèÿ ðèñêà áóäåò "çàñòàâëÿòü" "áåëûõ" óäåëÿòü íàèáîëüøåå âíèìàíèå íåáëàãîïðèÿòíûì èñõîäàì ñëó÷àéíîãî ñîáûòèÿ. Ïîäðîáíåå: ïðåäïîëîæèì, ÷òî èç òåêóùåé ïîçèöèè åñòü âåñüìà ïðèâëåêàòåëüíûé õîä (òî åñòü õîä ñ áîëüøîé "äåòåðìèíèðîâàííîé" îöåíêîé). Òàêæå ïðåäïîëîæèì, ÷òî èìèòàòîð øóìà ìîæåò äàòü ìàëîâåðîÿòíûé ñëó÷àéíûé èñõîä, êîòîðûé ïðè âûïîëíåíèè âûøåóïîìÿíóòîãî "ïðèâëåêàòåëüíîãî" õîäà ìíîãîå èñïîðòèò â ïðîöåññå äàëüíåéøåé èãðû. Òîãäà èãðîê ñ óáûâàþùåé ôóíêöèåé ðèñêà âûáåðåò õîä ñ ìåíüøåé, ÷åì ó "ïðèâëåêàòåëüíîãî", äåòåðìèíèðîâàííîé îöåíêîé, íî êîòîðûé õîòÿ áû ãàðàíòèðóåò îòñóòñòâèå áîëüøèõ ïîòåðü â äàëüíåéøåì. Òàêîé âûáîð ìîæåò ñîñòîÿòüñÿ äàæå ïðè ìàëîé âåðîÿòíîñòè ïëîõîãî ñëó÷àéíîãî èñõîäà. "Èãðîêà" ñ òàêîé ôóíêöèåé ðèñêà íàçûâàåì ïåññèìèñòîì. Èòàê, ïåññèìèñò "ñ÷èòàåò", ÷òî åìó, â îñíîâíîì, íå âåçåò. Ñ äðóãîé ñòîðîíû, ïðè âîçðàñòàþùåé ôóíêöèè ðèñêà åå îáëàäàòåëü íàñòðîåí "ñâåðõîïòèìèñòè÷íî", òàê êàê ýòà ôóíêöèÿ çàñòàâëÿåò åãî âûáèðàòü õîä, êîòîðûé ìîæåò (äàæå åñëè ýòî ìàëîâåðîÿòíî) ïðèíåñòè îùóòèìóþ ïîëüçó ïðè íåêîòîðîé ðåàëèçàöèè ñëó÷àéíîãî èñõîäà. Òàêèå ôóíêöèè ðèñêà èñïîëüçîâàòü áåññìûñëåííî. "Âëàäåëüöà" ôóíêöèè ðèñêà, òîæäåñòâåííî ðàâíîé êîíñòàíòå, òàêæå ìîæíî íàçâàòü "îïòèìèñòîì", òàê êàê îí ïðåäïîëàãàåò, ÷òî íåáëàãîïðèÿòíûé èñõîä ðàâíîâåðîÿòåí áëàãîïðèÿòíîìó. Äëÿ ïðîâåðêè àëãîðèòìà áûëà ðàçðàáîòàíà ïðîãðàììà (èñïîëüçîâàëñÿ êîìïèëÿòîð Borland Pascal 7.0), â êîòîðîé íà ïðèìåðå èãðû "êîðîòêèå íàðäû" ïðîâåðÿëàñü ðàáîòà îïèñàííîãî âûøå ìåòîäà. Ñîñòÿçàëîñü íåñêîëüêî "èãðîêîâ", èìåþùèõ ðàçëè÷íûå ôóíêöèè ðèñêà ñ "èãðîêîì  îïòèìèñòîì", ó êîòîðîãî â êà÷åñòâå ôóíêöèè ðèñêà áûëà âçÿòà ôóíêöèÿ f (x) = 1. Ðåçóëüòàòû ýòèõ "ñîðåâíîâàíèé" ïðèâåäåíû â òàáëèöå:

12

Ôóíêöèÿ ðèñêà ïåðâîãî èãðîêà ½ 0 x ∈ (0, 1] f (x) = 1 x=0 f (x) = 1 − x f (x) = 1 − 1/3 ∗ x f (x) = 1 − 1/2 ∗ x2 f (x) = 1 − 1/3 ∗ x2

Êîëè÷åñòâî ñûãðàííûõ ïàðòèé

Êîëè÷åñòâî ïîáåä "îïòèìèñòà"

Ïðîöåíò âûèãðûøåé "îïòèìèñòà"

150

51

34%

87 90 123 105

23 32 62 74

26% 36% 50.4% 70%

Ýêñïåðèìåíò ïîêàçàë, ÷òî âûáîð ôóíêöèè f (x) äåéñòâèòåëüíî îïðåäåëÿåò ñòðàòåãèþ èãðîêà. Òàê, ïðè ½ 1 ïðè x = 0 f (x) = ãäå x ∈ [0, 1] 0 ïðè x > 0 ïîëó÷àåì ñòðàòåãèþ "ïåññèìèñòà", à ïðè f (x) ≡ const  ñòðàòåãèþ "îïòèìèñòà". Äëÿ äàííûõ êðèòåðèåâ ýêñïåðèìåíòàëüíî ïîëó÷åíî, ÷òî ïåðâûé èç íèõ ïðàêòè÷åñêè âñåãäà ïðîèãðûâàåò âòîðîìó.  èìèòàòîðå øóìà èñïîëüçîâàëñÿ ãåíåðàòîð ïñåâäîñëó÷àéíûõ ÷èñåë èç ìîäóëÿ CRT (Borland Pascal 7.0). Ïîëó÷àåìûå ïñåâäîñëó÷àéíûå ÷èñëà ðàâíîìåðíî ðàñïðåäåëåíû íà èíòåðâàëå (0, 1). Áûëà äîêàçàíà ñòàòèñòè÷åñêàÿ ãèïîòåçà î ðàâíîìåðíîì ðàñïðåäåëåíèè èñïîëüçóåìûõ ïñåâäîñëó÷àéíûõ ÷èñåë. Ïîñëå íåáîëüøîãî ïðåîáðàçîâàíèÿ âõîäíîé ïîñëåäîâàòåëüíîñòè ïñåâäîñëó÷àéíûõ ÷èñåë èìèòàòîð âûäàâàë ðàâíîìåðíî ðàñïðåäåëåííûå íà îòðåçêå [1, 6] öåëûå ÷èñëà, êîòîðûå è èìèòèðîâàëè âûïàäåíèå î÷êîâ íà èãðàëüíûõ êîñòÿõ.

Ñïèñîê ëèòåðàòóðû [1] Â. Í. Ïåêåëèñ : Êèáåðíåòè÷åñêàÿ ñìåñü , Ì., Çíàíèå, 1991. [2] Êèáåðíåòèêà îæèäàåìàÿ è êèáåðíåòèêà íåîæèäàííàÿ , Ì., Íàóêà, 1968. [3] Ã. Ì. Àäåëüñîí-Âåëüñêèé, Â. Ë. Àðëàçàðîâ, Ì. Â. Äîíñêîé : ãðàììèðîâàíèå èãð , Ì., Íàóêà, 1978.

Ïðî-

[4] Ì. Ì. Áîòâèíèê : Àëãîðèòì èãðû â øàõìàòû , Ì., Íàóêà, 1968. 13

[5] À. Í. Ðàäèîíîâ : Íåêîòîðûå êðèòåðèè ðèñêà â èãðàõ ñ íåïîëíîé èíôîðìàöèåé.   êí.: Òåçèñû äîêëàäîâ XI ìåæäóíàðîäíîé íàó÷íîé êîíôåðåíöèè ïî ïðîáëåìàì òåîðåòè÷åñêîé êèáåðíåòèêè , Ì., Èçäâî ÐÃÃÓ, 1996, 168169.

14

On the decision of strategy in non-deterministic antagonistic games B. F. Melnikov , A. N. Radionov There are a lot of games which contain some accidental factors aecting on the process of the decision of the solution. How to choose successful strategy in such games? In deterministic games, there exists sorting algorithm of choosing successful strategy; that is minimax method. The strategy choosed by that algorithm can be like the optimal one (if we also successfully choosed the function of the static estimate of the position, of course). In this paper, we consider nondeterministic games. For this case, the sorting algorithm of choosing successful strategy is also considered. This algorithm may be considered as some generalization of minimax algorithm. Like the last one, the considered algorithm makes search of the strategy by sorting alternatives of the continuation of the game, and choose the alternative having the best estimate making by special way.

15