Poset game
সমন্বিত গেম তত্ত্বে, পজিট গেমগুলি কৌশলের গাণিতিক গেম, যা নিম এবং চম্পের মতো অনেক সুপরিচিত গেমকে সাধারণীকরণ করে। এই ধরনের খেলায়, দুইজন খেলোয়াড় একটি পোজেট (আংশিকভাবে সাজানো সেট) দিয়ে শুরু করে এবং পালাক্রমে পোজেটের একটি পয়েন্ট বেছে নেয়, এটি এবং তার চেয়ে বড় সমস্ত পয়েন্ট সরিয়ে দেয়। যে খেলোয়াড়ের বেছে নেওয়ার কোনও পয়েন্ট থাকে না, সে হেরে যায়। খেলাটি একটি আংশিকভাবে সাজানো সেট (পি, <) দেওয়া হলে, পি থেকে এক্স সরিয়ে গঠিত পজিটকে বোঝানো যাক। পি-তে একটি পজিট খেলা, যা প্রচলিতভাবে অ্যালিস এবং বব নামে দুই খেলোয়াড়ের মধ্যে খেলা হয়, তা নিম্নরূপঃ অ্যালিস একটি পয়েন্ট x ω পি বেছে নেয়; এইভাবে পি-কে পিএক্স দিয়ে প্রতিস্থাপন করে, এবং তারপর ববকে পালা দেয় যে পিএক্স-এ খেলে, এবং অ্যালিসের দিকে মোড় দেয়। একজন খেলোয়াড় হেরে যায় যদি তার/তার পালা হয় এবং বেছে নেওয়ার মতো কোনও পয়েন্ট না থাকে। উদাহরণস্বরূপ, যদি পি একটি সসীম সম্পূর্ণরূপে সাজানো সেট হয়, তবে পি-তে খেলাটি ঠিক নিমের একটি খেলায় খেলার মতো একই রকম যার আকার |P।।।। কারণ, উভয় খেলায়, এমন একটি পদক্ষেপ বেছে নেওয়া সম্ভব যা একই ধরনের খেলার দিকে পরিচালিত করে যার আকার |P। এর চেয়ে ছোট যে কোনও সংখ্যা। একইভাবে, মোট অর্ডারের একটি বিচ্ছিন্ন ইউনিয়ন সহ একটি পজিট গেম নিমের একটি গেমের সমতুল্য, যার পজিটে চেইনের সমান আকারের একাধিক স্তূপ রয়েছে। হ্যাকেনবুশের একটি বিশেষ ক্ষেত্রে, যেখানে সমস্ত প্রান্ত সবুজ (যে কোনও খেলোয়াড় দ্বারা কাটা যেতে পারে) এবং প্রতিটি বিন্যাস একটি বনের রূপ নেয়, একইভাবে প্রকাশ করা যেতে পারে, একটি পজিটে একটি পজিট গেম হিসাবে, যেখানে প্রতিটি উপাদান x এর জন্য, সর্বাধিক একটি উপাদান y রয়েছে যার জন্য x y কে আবৃত করে। যদি x y কে কভার করে, তাহলে y হল সেই বনের x-এর প্যারেন্ট যেখানে খেলাটি খেলা হয়। চম্পকে একইভাবে প্রকাশ করা যেতে পারে, মোট অর্ডারের গুণফলের উপর একটি পজিট গেম হিসাবে যেখান থেকে অসীমটি সরানো হয়েছে। গ্রান্ডি ভ্যালু পজিট গেমগুলি নিরপেক্ষ গেম, যার অর্থ অ্যালিসের কাছে উপলব্ধ প্রতিটি পদক্ষেপ ববকেও পাওয়া যেত যদি অ্যালিসকে পাস করার অনুমতি দেওয়া হয়, এবং তদ্বিপরীত। অতএব, স্প্রেগ-গ্রান্ডি উপপাদ্য অনুসারে, একটি পজিট গেমের প্রতিটি অবস্থানের একটি গ্রান্ডি মান থাকে, যা নিমের খেলায় সমতুল্য অবস্থান বর্ণনা করে। একটি পজিটের গ্রান্ডি মানকে সর্বনিম্ন প্রাকৃতিক সংখ্যা হিসাবে গণনা করা যেতে পারে যা কোনও পিএক্স, x ω পি-এর গ্রান্ডি মান নয়। অর্থাৎ, এই সংখ্যাটি একটি পজিট গেমের সর্বোত্তম খেলা বর্ণনা করতে ব্যবহার করা যেতে পারে। বিশেষত, গ্রান্ডি মানটি শূন্য নয় যখন যে খেলোয়াড়ের পালা আসে তার জয়ের কৌশল থাকে এবং শূন্য যখন বর্তমান খেলোয়াড় তার প্রতিপক্ষের কাছ থেকে সর্বোত্তম খেলার বিরুদ্ধে জিততে পারে না। খেলায় একটি বিজয়ী কৌশল এমন একটি অবস্থানে নিয়ে যায় যার গ্রান্ডি মান শূন্য, যখনই এটি সম্ভব হয়। কৌশল চুরি একটি কৌশল-চুরি যুক্তি দেখায় যে গ্রান্ডি মান প্রতিটি পজিটের জন্য শূন্য নয় যার একটি সর্বোচ্চতা রয়েছে। কারণ, ধরা যাক x একটি আংশিকভাবে ক্রমযুক্ত সেট P-এর সর্বোচ্চ মান। যদি Px-এর গ্রান্ডি মান শূন্য হয়, তবে উপরের সূত্র অনুসারে P-এর একটি অ-শূন্য মান রয়েছে; এই ক্ষেত্রে, P-তে x একটি বিজয়ী পদক্ষেপ। অন্যদিকে, যদি Px-এর একটি অ-শূন্য গ্রান্ডি মান থাকে, তবে Px-এ অবশ্যই একটি বিজয়ী পদক্ষেপ y থাকতে হবে, যাতে (Px) y-এর গ্রান্ডি মান শূন্য হয়। কিন্তু এই অনুমান দ্বারা যে x একটি সর্বোচ্চ, x> y এবং (Px) y = পাই, তাই বিজয়ী পদক্ষেপ y পি-তেও পাওয়া যায় এবং আবার পি-এর অবশ্যই একটি অ-শূন্য গ্রান্ডি মান থাকতে হবে। আরও তুচ্ছ কারণে অসীম সহ একটি পজিটের একটি অ-শূন্য গ্রান্ডি মানও রয়েছেঃ অসীমের দিকে এগিয়ে যাওয়া সর্বদা একটি বিজয়ী পদক্ষেপ। একটি নির্বিচারে সীমাবদ্ধ পজিট গেমের বিজয়ী নির্ধারণ করা পি. এস. পি. এ. সি. ই-সম্পূর্ণ। এর মানে হল যে পি = পি. এস. পি. এ. সি. ই না হলে, একটি নির্বিচারে পজিট গেমের গ্রান্ডি মান গণনা করা গণনামূলকভাবে কঠিন। তথ্যসূত্র কম্বিনেটরিয়াল গেম থিওরি গাণিতিক গেম