Poset game
ಸಂಯೋಜಿತ ಆಟದ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಪೊಸೆಟ್ ಆಟಗಳು ತಂತ್ರದ ಗಣಿತದ ಆಟಗಳಾಗಿವೆ, ಇದು ನಿಮ್ ಮತ್ತು ಚಾಂಪ್ನಂತಹ ಅನೇಕ ಪ್ರಸಿದ್ಧ ಆಟಗಳನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸುತ್ತದೆ. ಅಂತಹ ಆಟಗಳಲ್ಲಿ, ಇಬ್ಬರು ಆಟಗಾರರು ಪೊಸೆಟ್ನಿಂದ (ಭಾಗಶಃ ಕ್ರಮಬದ್ಧವಾದ ಸೆಟ್) ಪ್ರಾರಂಭಿಸುತ್ತಾರೆ ಮತ್ತು ಪೊಸೆಟ್ನಲ್ಲಿ ಒಂದು ಅಂಕವನ್ನು ಆಯ್ಕೆ ಮಾಡಿಕೊಳ್ಳುತ್ತಾರೆ, ಅದನ್ನು ಮತ್ತು ಹೆಚ್ಚಿನ ಎಲ್ಲಾ ಅಂಕಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತಾರೆ. ಆಯ್ಕೆ ಮಾಡಲು ಯಾವುದೇ ಪಾಯಿಂಟ್ ಇಲ್ಲದ ಆಟಗಾರನು ಸೋಲುತ್ತಾನೆ. ಸಾಂಪ್ರದಾಯಿಕವಾಗಿ ಆಲಿಸ್ ಮತ್ತು ಬಾಬ್ ಎಂದು ಹೆಸರಿಸಲಾದ ಇಬ್ಬರು ಆಟಗಾರರ ನಡುವೆ ಆಡಲಾಗುವ ಪಿ ಮೇಲಿನ ಒಂದು ಭಂಗಿ ಆಟವು ಈ ಕೆಳಗಿನಂತಿರುತ್ತದೆಃ ಆಲಿಸ್ ಒಂದು ಬಿಂದು x ω ಪಿ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿಕೊಳ್ಳುತ್ತಾಳೆ; ಹೀಗೆ ಪಿ ಅನ್ನು ಪಿಎಕ್ಸ್ನೊಂದಿಗೆ ಬದಲಾಯಿಸುತ್ತಾಳೆ, ಮತ್ತು ನಂತರ ಪಿಎಕ್ಸ್ನಲ್ಲಿ ಆಡುವ ಬಾಬ್ಗೆ ತಿರುವು ನೀಡುತ್ತಾಳೆ, ಮತ್ತು ಆಲಿಸ್ಗೆ ತಿರುವು ನೀಡುತ್ತಾಳೆ. ಒಬ್ಬ ಆಟಗಾರನು ಅವನ/ಅವಳ ಸರದಿ ಬಂದಾಗ ಸೋಲುತ್ತಾನೆ ಮತ್ತು ಆಯ್ಕೆ ಮಾಡಲು ಯಾವುದೇ ಅಂಕಗಳಿಲ್ಲ. ಉದಾಹರಣೆಗಳು ಪಿ ಒಂದು ಸೀಮಿತವಾದ ಸಂಪೂರ್ಣವಾಗಿ ಕ್ರಮಬದ್ಧವಾದ ಸೆಟ್ ಆಗಿದ್ದರೆ, ಪಿ ನಲ್ಲಿನ ಆಟವು ನಿಖರವಾಗಿ |P | ಗಾತ್ರದ ರಾಶಿಯನ್ನು ಹೊಂದಿರುವ ನಿಮ್ ಆಟದಲ್ಲಿ ಆಡುವ ಆಟದಂತೆಯೇ ಇರುತ್ತದೆ. ಏಕೆಂದರೆ, ಎರಡೂ ಆಟಗಳಲ್ಲಿ, ಒಂದೇ ರೀತಿಯ ಆಟಕ್ಕೆ ಕಾರಣವಾಗುವ ಚಲನೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ, ಅದರ ಗಾತ್ರವು |P | ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ. ಅದೇ ರೀತಿಯಲ್ಲಿ, ಒಟ್ಟು ಆರ್ಡರ್ಗಳ ಬೇರ್ಪಡುವ ಒಕ್ಕೂಟವನ್ನು ಹೊಂದಿರುವ ಪೊಸೆಟ್ ಆಟವು ಪೊಸೆಟ್ನಲ್ಲಿನ ಸರಪಳಿಗಳಿಗೆ ಸಮಾನವಾದ ಗಾತ್ರಗಳೊಂದಿಗೆ ಅನೇಕ ರಾಶಿಗಳನ್ನು ಹೊಂದಿರುವ ನಿಮ್ ಆಟಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಹ್ಯಾಕೆನ್ಬುಷ್ನ ಒಂದು ವಿಶೇಷ ಪ್ರಕರಣ, ಇದರಲ್ಲಿ ಎಲ್ಲಾ ಅಂಚುಗಳು ಹಸಿರು ಬಣ್ಣದಲ್ಲಿರುತ್ತವೆ (ಎರಡೂ ಆಟಗಾರರಿಂದ ಕತ್ತರಿಸಬಹುದಾಗಿದೆ) ಮತ್ತು ಪ್ರತಿ ಸಂರಚನೆಯು ಕಾಡಿನ ರೂಪವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಇದನ್ನು ಅದೇ ರೀತಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದು, ಒಂದು ಭಂಗಿ ಮೇಲಿನ ಭಂಗಿ ಆಟವಾಗಿ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಅಂಶ x ಗೆ, ಗರಿಷ್ಠ ಒಂದು ಅಂಶ y ಇರುತ್ತದೆ, ಇದಕ್ಕಾಗಿ x y ಅನ್ನು ಆವರಿಸುತ್ತದೆ. x ಯು y ಅನ್ನು ಆವರಿಸಿದರೆ, ಆಟವನ್ನು ಆಡುವ ಕಾಡಿನಲ್ಲಿ x ನ ಮೂಲ y ಆಗಿದೆ. ಚಾಂಪ್ ಅನ್ನು ಅದೇ ರೀತಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದು, ಒಟ್ಟು ಆದೇಶಗಳ ಉತ್ಪನ್ನದ ಮೇಲೆ ಪೊಸೆಟ್ ಆಟವಾಗಿ, ಇದರಿಂದ ಅನಂತವನ್ನು ತೆಗೆದುಹಾಕಲಾಗಿದೆ. ಗ್ರಂಡಿ ಮೌಲ್ಯದ ಪೊಸೆಟ್ ಆಟಗಳು ನಿಷ್ಪಕ್ಷಪಾತ ಆಟಗಳಾಗಿವೆ, ಅಂದರೆ ಆಲಿಸ್ಗೆ ಪಾಸ್ ಮಾಡಲು ಅನುಮತಿಸಿದರೆ ಆಲಿಸ್ಗೆ ಲಭ್ಯವಿರುವ ಪ್ರತಿಯೊಂದು ಚಲನೆಯೂ ಬಾಬ್ಗೆ ಲಭ್ಯವಿರುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿಯಾಗಿ. ಆದ್ದರಿಂದ, ಸ್ಪ್ರಾಗ್-ಗ್ರುಂಡಿ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪೊಸೆಟ್ ಆಟದಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸ್ಥಾನವೂ ಗ್ರುಂಡಿ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಇದು ನಿಮ್ ಆಟದಲ್ಲಿ ಸಮಾನ ಸ್ಥಾನವನ್ನು ವಿವರಿಸುವ ಒಂದು ಸಂಖ್ಯೆಯಾಗಿದೆ. ಪೊಸೆಟ್ನ ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಕನಿಷ್ಠ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆ ಎಂದು ಲೆಕ್ಕ ಹಾಕಬಹುದು, ಅದು ಯಾವುದೇ ಪಿಎಕ್ಸ್ನ ಗ್ರಂಡಿ ಮೌಲ್ಯವಲ್ಲ, ಅಂದರೆ, ಈ ಸಂಖ್ಯೆಯನ್ನು ಪೊಸೆಟ್ ಆಟದಲ್ಲಿ ಅತ್ಯುತ್ತಮ ಆಟವನ್ನು ವಿವರಿಸಲು ಬಳಸಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಗೆಲ್ಲುವ ತಂತ್ರವನ್ನು ಹೊಂದಿರುವ ಆಟಗಾರನ ಸರದಿ ಬಂದಾಗ ಗ್ರಂಡಿ ಮೌಲ್ಯವು ಶೂನ್ಯವಲ್ಲ, ಮತ್ತು ಪ್ರಸ್ತುತ ಆಟಗಾರನು ಅವನ ಅಥವಾ ಅವಳ ಎದುರಾಳಿಯ ಅತ್ಯುತ್ತಮ ಆಟದ ವಿರುದ್ಧ ಗೆಲ್ಲಲು ಸಾಧ್ಯವಾಗದಿದ್ದಾಗ ಶೂನ್ಯವಾಗಿರುತ್ತದೆ. ಆಟದಲ್ಲಿ ಗೆಲ್ಲುವ ತಂತ್ರವು ಸಾಧ್ಯವಾದಾಗಲೆಲ್ಲಾ ಗ್ರಂಡಿ ಮೌಲ್ಯವು ಶೂನ್ಯವಾಗಿರುವ ಸ್ಥಾನಕ್ಕೆ ಹೋಗುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಸ್ಟ್ರಾಟಜಿ ಸ್ಟಿಲಿಂಗ್ ಎ ಸ್ಟ್ರಾಟಜಿ-ಸ್ಟಿಲಿಂಗ್ ವಾದವು ಪ್ರಾಬಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿಯೊಂದು ಸ್ಥಾನಕ್ಕೂ ಗ್ರಂಡಿ ಮೌಲ್ಯವು ಶೂನ್ಯವಲ್ಲ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಏಕೆಂದರೆ, x ಭಾಗಶಃ ಕ್ರಮಿಸಲಾದ ಸೆಟ್ P ಯ ಸರ್ವೋನ್ನತ ಎಂದು ಭಾವಿಸೋಣ. Px ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಶೂನ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ, ಮೇಲಿನ ಸೂತ್ರದ ಪ್ರಕಾರ P ಸ್ವತಃ ಶೂನ್ಯವಲ್ಲದ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ; ಈ ಸಂದರ್ಭದಲ್ಲಿ, x ಎಂಬುದು P ಯಲ್ಲಿ ಗೆಲುವಿನ ಚಲನೆಯಾಗಿದೆ. ಮತ್ತೊಂದೆಡೆ, Px ಶೂನ್ಯವಲ್ಲದ ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ, Px ನಲ್ಲಿ ಗೆಲುವಿನ ಚಲನೆ y ಇರಬೇಕು, ಅಂದರೆ (Px) y ನ ಗ್ರಂಡಿ ಮೌಲ್ಯವು ಶೂನ್ಯವಾಗಿರುತ್ತದೆ. ಆದರೆ x ಒಂದು ಸರ್ವೋನ್ನತ, x> y ಮತ್ತು (Px) y = ಪೈ ಎಂಬ ಊಹೆಯಿಂದ, ಆದ್ದರಿಂದ ಗೆಲ್ಲುವ ಚಲನೆ y ಸಹ P ಯಲ್ಲಿ ಲಭ್ಯವಿದೆ ಮತ್ತು ಮತ್ತೆ P ಶೂನ್ಯವಲ್ಲದ ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರಬೇಕು. ಹೆಚ್ಚು ಕ್ಷುಲ್ಲಕ ಕಾರಣಗಳಿಗಾಗಿ, ಅನಂತವನ್ನು ಹೊಂದಿರುವ ಭಂಗಿಯು ಸಹ ಶೂನ್ಯವಲ್ಲದ ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆಃ ಅನಂತಕ್ಕೆ ಚಲಿಸುವುದು ಯಾವಾಗಲೂ ಗೆಲುವಿನ ಕ್ರಮವಾಗಿದೆ. ಸಂಕೀರ್ಣತೆ ಅನಿಯಂತ್ರಿತ ಸೀಮಿತ ಸ್ಥಾನದ ಆಟದ ವಿಜೇತರನ್ನು ನಿರ್ಧರಿಸುವುದು ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಇದರರ್ಥ ಪಿ = ಪಿ. ಎಸ್. ಪಿ. ಎ. ಸಿ. ಇ ಹೊರತು, ಅನಿಯಂತ್ರಿತ ಭಂಗಿ ಆಟದ ಗ್ರಂಡಿ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದು ಗಣನೆಗೆ ಕಷ್ಟಕರವಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಸಂಯೋಜಿತ ಆಟದ ಸಿದ್ಧಾಂತ ಗಣಿತದ ಆಟಗಳು