Իքս-նոլիկ

Իքս-նոլիկ
Տեսակ	strategy game? և paper-and-pencil game?
Ենթատեսակ	խաղ վանդակավոր դաշտում
Խաղացողների քանակ մինիմալ	2
Խաղացողների քանակ մաքսիմալ	2

Իքս-նոլիկ, երկու խաղացողների համար նախատեսված տրամաբանական խաղ, որը խաղում են 3×3 կամ ավելի մեծ թվով վանդակների բաժանված քառակուսի դաշտում (ընդհուպ մինչև «անսահման դաշտում»)։ Խաղացողներից մեկը խաղում է «խաչերով» (իքսերով), երկրորդը՝ «նոլիկներով» (զրոներ)։ Չինական ավանդական խաղում (Գոմոկու) օգտագործվում են սև և սպիտակ քարեր։

Դասական տարբերակ[խմբագրել | խմբագրել կոդը]

Խաղի կանոններ[խմբագրել | խմբագրել կոդը]

Խաղացողները հերթով 3х3 դաշտի ազատ վանդակներում դնում են նշաններ (մեկը միշտ իքսեր, մյուսը՝ զրոներ)։ Հաղթում է այն մասնակիցը, որն առաջինն է իր նշաններից երեքով հորիզոնական, ուղղահայաց ուղղություններով կամ անկյունագծով շարք կառուցում։ Առաջին քայլն անում է իքս դնող մասնակիցը։

Սովորաբար խաղի վերջում հաղթող կողմը գծով հատում է իր երեք նիշերը (զրո կամ իքսեր), որոնք շարք են կազմում։

Վերլուծություն[խմբագրել | խմբագրել կոդը]

Կողմերից յուրաքանչյուրին հայտնի են ալգորիթմներ, որոնք հակառակորդի ցանկացած խաղի դեպքում երաշխավորում են ոչ-ոքի, իսկ նրա սխալի դեպքում հնարավորություն են տալիս հաղթել։ Այդպիսով՝ խաղը գտնվում է «ոչ մեկին չպատկանող մահվան» վիճակում։

Ստորև բերված են այդպիսի ռազմավարություններից մի քանիսը։ Համարվում է, որ խաղացողը միշտ պահպանում է երկու կանոն, որոնք գերակա են բոլոր մյուսներից.

Կանոն 1։ Եթե խաղացողը կարող է անմիջապես հաղթել, նա դա անում է։
Կանոն 2։ Եթե խաղացողը չի կարող անհապաղ հաղթել, բայց մրցակիցը կարող է անմիջապես հաղթել՝ քայլ կատարելով ինչ-որ վանդակում, ապա խաղացողն ինքն է այդ վանդակում քայլ կատարում՝ կանխելով արագ պարտվելը։

Իքսերի համար[խմբագրել | խմբագրել կոդը]

Առաջին քայլը կատարել կենտրոնում։ Մնացած քայլերը, եթե 1-2 կանոններն անկիրառելի են, կատարվում են այն ազատ անկյունից, որն ամենահեռուն է զրոյի նախորդ քայլից, իսկ եթե դա ևս անհնար է, ապա ցանկացած վանդակից։


	Х

Ստորև ցույց է տրվում, որ այս ռազմավարությունը հանգեցնում է հաղթանակի կամ ոչ-ոքիի։ Եթե զրոն դրվում է կողքին, ապա դրությունը կլինի այսպիսին.

	О
	Х
Х

Դրանից հետո 1-ին և 2-րդ կանոնները կհանգեցնեն հետևյալ դիրքի.

Х	О	О
	Х
Х

Հաղթանակ։

Եթե զրոն դրվում է անկյունում, դրությունը կլինի այսպիսին.

О
	Х
		Х

Կախված զրոյի հաջորդ քայլից՝ կստեղծվի 3 դիրքերից մեկը.

О	О	Х
	Х
		Х

О	Х	О
	Х
		Х

О
	Х	О
Х		Х

Առաջին և երրորդ դիրքերում հաղթանակ է, երկրորդ դիրքում՝ ոչ-ոքի։

Զրոների համար[խմբագրել | խմբագրել կոդը]

Եթե 1-2-րդ կանոնները կիրառելի են, ապա դրանք առաջնություն են տալիս ստորև բոլոր նշվածներին։

Եթե իքսերն առաջին քայլը կատարում են կենտրոնում, ապա մինչև խաղի վերջը քայլ են կատարում ցանկացած անկյունում, իսկ եթե դա անհնար է, ապա ցանկացած վանդակում։

		О
	Х

Եթե իքսերն առաջին քայլը կատարել են անկյունում, դրան պատասխանել կենտրոնում կատարած քայլով։

		Х
	О

Հաջորդ քայլով զբաղեցնել իքսերի առաջին քայլով զբաղեցրած անկյան հանդիպակաց անկյունը, իսկ եթե դա անհնար է, քայլը կատարել կողքի վանդակում։

		Х
	О
	Х	О

Եթե իքսերն առաջին քայլը կատարել են կողմնային վանդակում, զրոն դնել անկյունում։
Եթե հաջորդ քայլով իքսը դրվում է անկյունում, զբաղեցնել հանդիպակաց անկյունը.

	Х	О
	О
Х

Եթե իքսերի հաջորդ քայլը հանդիպակաց կողմում է, քայլը կատարել ցանկացած անկյունում.

О	Х
	О
	Х

Եթե իքսերի հաջորդ քայլը նրանց առաջին քայլի կողքին է, ապա զրոն դնել երկու իքսերին մոտ անկյունում.

О	Х
Х	О

Խաղային իրավիճակների ծառ[խմբագրել | խմբագրել կոդը]

Խաղային իրավիճակների մասնակի ծառ իքս-նոլիկ խաղի համար

Իքս-նոլիկ խաղի խաղային իրավիճակների ծառը, որտեղ իքսերով խաղացողը անում է առաջին քայլն ու խաղում ըստ վերոբերյալ ալգորիթմի, իսկ զրոներով խաղացողը կարող է կատարել ցանկացած քայլ (ընդ որում ներկայացված է մեկական դեպք ռացիոնալ ու ոչ ռացիոնալ քայլի համար, այսինքն՝ ցանկացած ուրիշ), կազմված է 50 հանգույցներից։

Համակարգչային լուծում[խմբագրել | խմբագրել կոդը]

Համակարգչով այդ տիպի խաղերի լուծման համար կառուցվում է խաղային իրավիճակների ծառ մինի-մաքս մեթոդի համաձայն։ Այդ ծառի հանգույցների թիվը կազմում է 255168^[1], որն ստացվում է որպես բոլոր հնարավոր քայլերի գումարային քանակ՝ 9 տարբերակ առաջին քայլում, 8՝ 9-ից յուրաքանչյուրի երկրորդ քայլի համար, 7՝ 72 տարբերակների երրորդ քայլի համար և այլն՝ հանած խաղը ժամանակից շուտ ավարտելու (պարտություն) դեպքերը։

Ընդհանրացումներ[խմբագրել | խմբագրել կոդը]

Ավելի երկար տողեր[խմբագրել | խմբագրել կոդը]

Կարելի է քննարկել մի խաղ, որում հաղթող է համարվում այն խաղացողը, որը բավականին մեծ ուղղանկյուն դաշտում առաջինն է կառուցում $n\geqslant 3$ նույն նշաններից կազմված շարք։ Միևնույն ժամանակ, կարող ենք դաշտը սահմանափակել որոշակի չափերով (սկսած $n\times n$ չափերից) կամ էլ ընդհանրապես չսահմանափակել (այս դեպքում խոսքը գնում է «անսահման» դաշտի մասին)։

Անսահան դաշտում մինչև 4 նույնական նշանով խաղալն անհետաքրքիր է, քանի որ սկսնակները բավականին արագ են ճանկառք (պատառաքաղ) կառուցում և հաղթում։ $n\geqslant 6$ դեպքում խաղը նույնպես անհետաքրքիր է «ոչ մեկին չպատկանող մահվան» պատճառով։ Կան ռազմավարություններ, որոնք մրցակցին երբևէ թույլ չեն տալիս անհրաժեշտ շարքը կառուցել։ Այնուամենայնիվ, $n=5$ դեպքում խաղը շատ ավելի իմաստալից է դառնում։ Այդպիսի տարբերակն ունի հատուկ անվանում՝ գոմոկու։ Սկզբում գոմոկուն խաղացել են 19×19 չափերով խաղատախտակի վրա, ավելի ուշ այն փոքրացվել է մինչև 15×15 չափերի։

Անսահման դաշտում խաղալիս հաղթելու հիմնական մարտավարությունը խաչավորումների («ճանկառքերի») ստեղծումն է, որոնք հակառակորդին հնարավորություն չեն տալիս արգելափակել հնգյակի կառուցման բոլոր հնարավոր եղանակները։ Չպարտվելու համար անհրաժեշտ է ժամանակին ընդհատել հակառակորդի՝ 3 և ավելի նշաններից կազմված շարքերը։

Փորձը ցույց է տվել, որ հավասար կանոնների դեպքում այն խաղացողը, որն անում է առաջին քայլը, ունի բավարար որակյալ խաղում հաղթելու առավելություն, ինչը հետագայում ճշգրիտ ապացուցվել է^[2]^[3]։ Խաղի նկատմամբ հետաքրքրությունը պահպանելու նպատակով առաջարկվել են խաղի կանոնները վերափոփոխելու զանազան տարբերակներ։ Այսպես, խաղն առաջինն սկսած խաղացողի համար ներմուծվում են ֆոլեր (արգելված քայլեր). նրան արգելվում է կառուցել 3×3, 4×4 ճանկառք, ինչպես նաև իր նշանից ստանալ «երկար շարք», ստացվել է ռենձյու անունով նոր խաղ, որին բնորոշ են խաղային լայն ռազմավարություններ և խաղացողների համար հավասար հնարավորություններ։

Դաշտի փոփոխում[խմբագրել | խմբագրել կոդը]

Դաշտի չափերի փոփոխումն արդեն վերև քննարկվել է։ Ամենապարզ, բայց խաղի մարտավարական բազմազանության մեծացման ձևը 3х3 չափերով դաշտի կողմերից մեկի երկայնքով մեկ վանդակի ավելացումն է։

Մեկ այլ տարբերակ է դաշտի տոպոլոգիան փոխելը։ Օրինակ՝ կարելի է համարել, որ դաշտի հանդիպակաց կողմերը սոսնձված են և կազմում են գլանային կամ տորի մակերևույթ, կամ էլ պրոյեկտիվ հարթություն։ Կարելի է նաև մեծացնել դաշտի չափականությունը, օրինակ՝ խաղալ 4x4x4 խորանարդի, հիպերխորանարդի վրա։

Նշանների փոխանակում[խմբագրել | խմբագրել կոդը]

Կարելի է փոխել կանոնը՝ ըստ որի խաղացողները դնում են միայն իրենց նշանը։

Օրինակ՝ խաղի տարբերակ է կարող է լինել հետևյալը. խաղացողները դնում են իքս կամ զրո (որը ցանկանում են), հաղթում է առաջինը, եթե կառուցում է նույն նշանից կազմված անհրաժեշտ երկարությամբ շարք, հաղթում է երկրորդը, եթե դաշտը լրացնելուց հետո դա տեղի չի ունենում։

Մեկ այլ տարբերակ՝ խաղացողն «իր» նշանը փոխում է յուրաքանչյուր քայլում։

Հաղթելու պայմանի փոփոխում[խմբագրել | խմբագրել կոդը]

Ցանկալի երկարությամբ առաջին շարքը կառուցելուց հետո խաղն ավարտելու փոխարեն կարելի է այն շարունակել մինչև դաշտն ամբողջությամբ լրացնելը։ Օրինակ՝ ցանկացած դաշտում կարելի է խաղալ այն պայմանով, որ կհաղթի իր նշանով ավելի շատ «քառյակներ» կառուցած մասնակիցը։

Գոյություն ունի նաև իքս-նոլիկ խաղի Սիլվերմենի տարբերակը^[4], որում օգտագործվում է 4х4 վանդակներով խաղադաշտ։ Իքսերը հաղթում են, եթե առկա է 4 նույն նշաններից (իքսերի կամ զրոների) կազմված շարք, այլապես հաղթում են զրոները։

Քայլի երկարացում[խմբագրել | խմբագրել կոդը]

Խաղի վերափոխված մեկ այլ տարբերակ է, երբ յուրաքանչյուր քայլում խաղացողն իր նշանից դնում է ոչ թե մեկը, այլ երկուսը կամ ավելին։ Այդպիսին է Connect6 խաղը, որի ժամանակ սևերն անում են առաջին քայլը՝ դնելով մեկ նշան, որից հետո խաղացողները հերթով դնում են 2 նշան։ Հաղթում է այն խաղացողը, որն առաջինն է գծանշում է իր 6 կամ ավելի նշանների շարքը։

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

↑ «How many Tic-Tac-Toe (noughts and crosses) games?». www.se16.info. Վերցված է 2019 թ․ օգոստոսի 16-ին.
↑ Allis, L. V. (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.
↑ Allis, L. V., Herik, H. J. van den, and Huntjens, M. P. H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12.
↑ крестиков-ноликов Силвермэна

Գրականություն[խմբագրել | խմբագրել կոդը]

Гарднер М. Крестики-нолики. —М.: Мир, 1988. ISBN 5-03-001234-6.

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]

[1] «How many Tic-Tac-Toe (noughts and crosses) games?». www.se16.info. Վերցված է 2019 թ․ օգոստոսի 16-ին.

[2] Allis, L. V. (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.

[3] Allis, L. V., Herik, H. J. van den, and Huntjens, M. P. H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12.

[4] крестиков-ноликов Силвермэна

[1]

[2]

[3]

[4]