Իքս-նոլիկ

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

Իքս-նոլիկ, երկու խաղացողների համար նախատեսված տրամաբանական խաղ, որը խաղում են 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. крестиков-ноликов Силвермэна

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

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