Իքս-նոլիկ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Իքս-նոլիկ
Tic tac toe.svg
Տեսակgame on cell board?

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

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

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

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

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

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

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

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

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

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

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

     
  Х  
     

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

  О  
  Х  
Х    

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

Х О О
  Х  
Х    

Հաղթանակ։

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

О    
  Х  
    Х

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

О О Х
  Х  
    Х
О Х О
  Х  
    Х
О    
  Х О
Х   Х

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. «How many Tic-Tac-Toe (noughts and crosses) games?»։ www.se16.info։ Վերցված է 2019-08-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. крестиков-ноликов Силвермэна

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

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