Poset game
સંયુક્ત રમત સિદ્ધાંતમાં, પોસેટ રમતો વ્યૂહરચનાની ગાણિતિક રમતો છે, જે નિમ અને ચોમ્પ જેવી ઘણી જાણીતી રમતોનું સામાન્યીકરણ કરે છે. આવી રમતોમાં, બે ખેલાડીઓ પોસેટ (આંશિક રીતે ક્રમબદ્ધ સમૂહ) થી શરૂઆત કરે છે, અને વારાફરતી પોસેટમાં એક બિંદુ પસંદ કરે છે, તેને દૂર કરે છે અને બધા પોઇન્ટ્સ કે જે વધારે હોય છે. જે ખેલાડી પાસે પસંદ કરવાનો કોઈ મુદ્દો બચતો નથી, તે હારી જાય છે. રમતને આંશિક રીતે ક્રમબદ્ધ સમૂહ (P, <) આપવામાં આવે તો, ચાલો P માંથી x ને દૂર કરીને રચાયેલી સ્થિતિને સૂચવીએ. P પરની સ્થિતિ રમત, જે પરંપરાગત રીતે એલિસ અને બોબ નામના બે ખેલાડીઓ વચ્ચે રમાય છે, તે નીચે મુજબ છેઃ એલિસ એક બિંદુ x bul P પસંદ કરે છે; આમ P ને Px સાથે બદલે છે, અને પછી બોબ તરફ વળાંક આપે છે જે Px પર રમે છે, અને વળાંક એલિસને આપે છે. જો તેનો વારો હોય અને પસંદ કરવા માટે કોઈ પોઈન્ટ ન હોય તો ખેલાડી હારી જાય છે. ઉદાહરણો જો પી એ મર્યાદિત સંપૂર્ણપણે ક્રમબદ્ધ સમૂહ છે, તો પી માં રમત રમવી એ બરાબર |P | કદના ઢગલા સાથે નિમની રમતમાં રમવા જેવી જ છે. કારણ કે, બંને રમતોમાં, એવી ચાલ પસંદ કરવી શક્ય છે જે સમાન પ્રકારની રમત તરફ દોરી જાય છે જેનું કદ |P | કરતા નાની કોઈપણ સંખ્યા હોય. એ જ રીતે, કુલ ઓર્ડરના અસંબદ્ધ જોડાણ સાથેની પોસેટ રમત પોસેટમાં સાંકળોની સમાન કદના બહુવિધ ઢગલાઓ સાથેની નિમની રમતની સમકક્ષ હોય છે. હેકેનબુશનો એક ખાસ કિસ્સો, જેમાં તમામ ધાર લીલા રંગની હોય છે (કોઈપણ ખેલાડી દ્વારા કાપી શકાય છે) અને દરેક રૂપરેખાંકન જંગલનું સ્વરૂપ લે છે, તે જ રીતે વ્યક્ત કરી શકાય છે, જેમાં દરેક તત્વ x માટે, મહત્તમ એક તત્વ y હોય છે, જેના માટે x એ y ને આવરી લે છે. જો x એ y ને આવરી લે છે, તો y એ જંગલમાં x નો પેરેન્ટ છે જેના પર રમત રમાય છે. ચોમ્પને એ જ રીતે વ્યક્ત કરી શકાય છે, કુલ ઓર્ડરના ઉત્પાદન પર પોસેટ રમત તરીકે જેમાંથી અનંત દૂર કરવામાં આવ્યું છે. ગ્રાન્ડી વેલ્યુ પોસેટ રમતો નિષ્પક્ષ રમતો છે, જેનો અર્થ છે કે જો એલિસને પાસ કરવાની મંજૂરી આપવામાં આવે તો એલિસ માટે ઉપલબ્ધ દરેક ચાલ બોબ માટે પણ ઉપલબ્ધ હશે, અને તેનાથી ઊલટું. તેથી, સ્પ્રેગ-ગ્રાન્ડી પ્રમેય અનુસાર, પોસેટ રમતમાં દરેક સ્થાનનું ગ્રાન્ડી મૂલ્ય હોય છે, જે નિમની રમતમાં સમકક્ષ સ્થાનનું વર્ણન કરતી સંખ્યા છે. પોસેટના ગ્રાન્ડી મૂલ્યની ગણતરી ઓછામાં ઓછી કુદરતી સંખ્યા તરીકે થઈ શકે છે જે કોઈપણ Px, x Π નું ગ્રાન્ડી મૂલ્ય નથી. એટલે કે, આ સંખ્યાનો ઉપયોગ પોસેટ રમતમાં શ્રેષ્ઠ રમતનું વર્ણન કરવા માટે થઈ શકે છે. ખાસ કરીને, જ્યારે જે ખેલાડીનો વારો હોય તેની જીતવાની વ્યૂહરચના હોય ત્યારે ગ્રાન્ડી મૂલ્ય બિન-શૂન્ય હોય છે, અને જ્યારે વર્તમાન ખેલાડી તેના અથવા તેણીના પ્રતિસ્પર્ધીની શ્રેષ્ઠ રમત સામે જીતી શકતો નથી ત્યારે શૂન્ય હોય છે. રમતમાં જીતવાની વ્યૂહરચનામાં જ્યારે પણ શક્ય હોય ત્યારે એવી સ્થિતિ તરફ આગળ વધવાનો સમાવેશ થાય છે કે જેનું ગ્રાન્ડી મૂલ્ય શૂન્ય હોય. વ્યૂહરચના ચોરી કરવાની વ્યૂહરચના-ચોરીની દલીલ દર્શાવે છે કે સર્વોચ્ચતા ધરાવતી દરેક સ્થિતિ માટે ગ્રાન્ડી મૂલ્ય બિન-શૂન્ય છે. કારણ કે, x એ આંશિક રીતે ક્રમાંકિત સમૂહ P નો સર્વોચ્ચ ભાગ હોવો જોઈએ. જો Px પાસે ગ્રાન્ડી મૂલ્ય શૂન્ય હોય, તો P પોતે જ ઉપરના સૂત્ર દ્વારા બિન-શૂન્ય મૂલ્ય ધરાવે છે; આ કિસ્સામાં, P માં x એ વિજેતા ચાલ છે. જો, બીજી બાજુ, Px પાસે બિન-શૂન્ય ગ્રાન્ડી મૂલ્ય હોય, તો પછી Px માં વિજેતા ચાલ y હોવી આવશ્યક છે, જેમ કે (Px) y નું ગ્રાન્ડી મૂલ્ય શૂન્ય છે. પરંતુ એવી ધારણા દ્વારા કે x એ સર્વોચ્ચ છે, x> y અને (Px) y = Py, તેથી વિજેતા ચાલ y પણ P માં ઉપલબ્ધ છે અને ફરીથી P નું બિન-શૂન્ય ગ્રાન્ડી મૂલ્ય હોવું આવશ્યક છે. વધુ તુચ્છ કારણોસર અનંત સાથેના પોસેટમાં બિન-શૂન્ય ગ્રાન્ડી મૂલ્ય પણ હોય છેઃ અનંત તરફ આગળ વધવું એ હંમેશા એક વિજયી ચાલ હોય છે. જટિલતા મનસ્વી મર્યાદિત પોઝિટ રમતના વિજેતાને નક્કી કરવું એ PSPACE-પૂર્ણ છે. આનો અર્થ એ છે કે જ્યાં સુધી પી = પી. એસ. પી. એ. સી. ઈ. ન હોય ત્યાં સુધી મનસ્વી સ્થિતિવાળી રમતના ગ્રાન્ડી મૂલ્યની ગણતરી કરવી ગણતરીત્મક રીતે મુશ્કેલ છે. સંદર્ભો સંયુક્ત રમત સિદ્ધાંત ગાણિતિક રમતો