Lessons in Play : An Introduction to Combinatorial Game Theory, Second Edition

آیا تا به حال به این فکر کرده‌اید که بازی‌های ساده‌ای مانند تیک-تاک-تو یا شطرنج، چه ساختار ریاضی عمیقی در پس‌زمینه خود دارند؟ کتاب «Lessons in Play: An Introduction to Combinatorial Game Theory, Second Edition» نوشتهٔ مایکل اچ. آلبرت، ریچارد جی. نوواکوسکی و دیوید وولف، دریچه‌ای است به دنیای شگفت‌انگیز نظریهٔ بازی‌های ترکیبیاتی که در آن، هر حرکت و هر استراتژی با زبانی از اعداد و جبر تفسیر می‌شود. این کتاب که نسخهٔ دوم آن در سال ۲۰۱۹ توسط انتشارات «ای کی پیترز/سی‌آرسی پرس» منتشر شده، با ساختاری گام‌به‌گام، شما را از مفاهیم پایه تا پیشرفته‌ترین مباحث این رشتهٔ ریاضیاتی جذاب راهنمایی می‌کند.

دربارهٔ کتاب Lessons in Play —

کتاب «درس‌هایی در بازی» یک کتاب درسی جامع و در عین حال قابل‌دسترس برای ورود به نظریهٔ بازی‌های ترکیبیاتی است. بازی‌های ترکیبیاتی، بازی‌هایی با دو بازیکن هستند که در آن‌ها هیچ عنصر شانسی وجود ندارد و تمام اطلاعات برای هر دو بازیکن مشخص و کامل است. این کتاب با زبانی روان و با تکیه بر مثال‌های متعدد، مفاهیم کلیدی این حوزه را معرفی می‌کند. نویسندگان با ارائهٔ تعاریف بنیادین، تکنیک‌های پایه‌ای مانند استراتژی‌های حریصانه، تقارن و «دزدیدن استراتژی» را شرح می‌دهند و سپس به بررسی کلاس‌های خروجی بازی‌ها می‌پردازند. از جمله نقاط قوت این کتاب، ارائهٔ مطالعه‌های موردی متعدد از بازی‌های معروف مانند «داتس اند باکسز» و «دامینیرینگ» است که به درک بهتر مفاهیم انتزاعی کمک شایانی می‌کند. در ادامه، کتاب با رویکردی عمیق‌تر به جبر بازی‌ها می‌پردازد و نشان می‌دهد که چگونه می‌توان مجموعه‌ای از بازی‌ها را با عملیات جمع‌آوری ترکیب کرده و ساختارهای جبری جالبی ایجاد کرد. این بخش از کتاب، مفاهیمی چون اعداد حقیقی و اعداد سورئال (اعداد مافوق واقعی) را که توسط جان کانوی پایه‌گذاری شده‌اند، به زبانی ساده و قابل فهم معرفی می‌کند. هدف اصلی کتاب، فراتر از صرفاً تحلیل بازی‌های خاص، ایجاد یک چارچوب ریاضی قدرتمند برای درک و حل هر بازی ترکیبیاتی با قاعده‌ی «آخرین حرکت‌دهنده برنده است» است. سبک نگارش کتاب به گونه‌ای است که با وجود اثبات‌های دقیق ریاضی، هرگز از جذابیت و طراوت نمی‌افتد و خواننده را مشتاق به دنبال کردن مباحث می‌کند.

دربارهٔ نویسندگان

مایکل اچ. آلبرت (Michael H. Albert) استاد دانشگاه اوتاگو در نیوزیلند است و سهم عمده‌ای در توسعهٔ نظریهٔ بازی‌های ترکیبیاتی داشته است. ریچارد جی. نوواکوسکی (Richard J. Nowakowski) از اعضای هیئت علمی دانشگاه دالهاوسی در کانادا و یکی از چهره‌های شاخص و پرکاربرد در این حوزه با بیش از ۱۳۵ مقالهٔ علمی و شاخص اچ ۲۰ است. دیوید وولف (David Wolfe) نیز که مدرک دکترای خود را از دانشگاه کالیفرنیا، برکلی دریافت کرده، یکی از نویسندگان برجستهٔ حوزهٔ بازی‌های ترکیبیاتی است که بر روی کاربردهای این نظریه در هوش مصنوعی نیز فعالیت داشته است. هر سه نویسنده از متخصصان برجستهٔ این حوزه بوده و سال‌ها در زمینهٔ نظریهٔ بازی‌ها تحقیق و تدریس کرده‌اند.

چرا باید Lessons in Play را بخوانید؟

مطالعهٔ این کتاب دستاوردهای علمی و بینش‌های ارزشمندی برای شما به همراه خواهد داشت:

• درک بنیادین نظریهٔ بازی‌های ترکیبیاتی: با اصول اولیه، قوانین و ساختار بازی‌هایی که مبتنی بر استراتژی محض و اطلاعات کامل هستند، آشنا می‌شوید و چارچوبی برای تحلیل آن‌ها به دست می‌آورید.
• آشنایی با تکنیک‌های قدرتمند تحلیلی: روش‌هایی همچون «دزدیدن استراتژی»، «تغییر بازی»، و استفاده از تقارن برای ساده‌سازی و حل مسائل پیچیده را فرا می‌گیرید.
• کشف جبر حاکم بر بازی‌ها: با مفاهیم پیشرفته‌ای مانند جمع بازی‌ها، کلاس‌های خروجی، اعداد سورئال و ساختار جبری بازی‌ها آشنا شده و درک عمیقی از ماهیت ریاضیاتی آن‌ها پیدا می‌کنید.
• کاربرد عملی دانش در مثال‌های واقعی: با مطالعهٔ موردی بازی‌های گوناگون مانند «نیم»، «دامینیرینگ»، و «تاپلینگ دامینوز»، می‌آموزید که چگونه تئوری را در عمل به کار بگیرید.
• آشنایی با نرم‌افزارهای تخصصی و مسیرهای پیش‌رو: با «سی‌جی‌سوئیت» (CGSuite) به عنوان ابزاری برای تحلیل بازی‌ها آشنا شده و با حوزه‌های تحقیقاتی جدید مانند بازی‌های «داغ»، «کاملاً کوچک» و «حلقه‌ای» نیز دید پیدا می‌کنید.

این کتاب برای چه کسانی مناسب است؟

این کتاب یک منبع درسی استاندارد و عالی برای دانشجویان دورهٔ کارشناسی ریاضیات یا علوم رایانه است که به دنبال درک عمیقی از نظریهٔ بازی‌ها هستند. با این حال، دامنهٔ مخاطبان آن بسیار گسترده‌تر است و برای هر علاقه‌مندی که دارای بلوغ ریاضیاتی کافی باشد، قابل استفاده است. دانشجویان تحصیلات تکمیلی، محققان حوزهٔ ریاضیات گسسته و الگوریتم‌ها، و حتی برنامه‌نویسانی که به طراحی هوش مصنوعی برای بازی‌ها اشتغال دارند، می‌توانند از مطالب ارزشمند این کتاب بهره‌مند شوند. رویکرد گام‌به‌گام و مثال‌های فراوان، آن را برای مطالعهٔ خودخوان نیز مناسب ساخته است.

سوالات متداول

پیش‌نیازهای مطالعهٔ این کتاب چیست؟

داشتن دانش پایه‌ای در ریاضیات گسسته و آشنایی با اثبات‌های ریاضی برای درک کامل کتاب ضروری است. با این حال، کتاب با مفاهیم بسیار ابتدایی شروع شده و نیازی به دانش تخصصی قبلی در نظریهٔ بازی‌ها ندارد. مفاهیم جبری پیشرفته‌تر نیز به تدریج و با توضیحات کامل معرفی می‌شوند.

تفاوت نسخهٔ دوم با نسخهٔ اول در چیست؟

نسخهٔ دوم این کتاب، که در سال ۲۰۱۹ منتشر شده، نسبت به نسخهٔ اول (۲۰۰۷) تغییرات اساسی در چیدمان مطالب داشته است تا آن را قابل‌دسترس‌تر کند. همچنین تعداد زیادی تمرین و مثال جدید به آن افزوده شده و رویکردی دو مرحله‌ای برای برخی مباحث اتخاذ شده است؛ به این معنا که ابتدا مفاهیم اصلی با مثال ارائه شده و جزئیات انتزاعی‌تر به بخش‌های بعدی موکول شده است. بخش مربوط به نرم‌افزار «سی‌جی‌سوئیت» نیز در این نسخه به طور کامل بازنویسی شده است.

آیا کتاب به بازی‌های شانسی یا اطلاعات ناقص نیز می‌پردازد؟

خیر، همان‌طور که از عنوان آن پیداست، این کتاب به طور خاص بر روی بازی‌های ترکیبیاتی متمرکز است که در آن‌ها شانسی وجود نداشته و هر دو بازیکن از تمام اطلاعات جریان بازی آگاه هستند. بازی‌هایی مانند پوکر یا تخته‌نرد که در آن‌ها شانس یا اطلاعات پنهان نقش دارد، جزو حیطهٔ این کتاب محسوب نمی‌شوند.

This second edition of Lessons in Play reorganizes the presentation of the popular original text in combinatorial game theory to make it even more widely accessible. Starting with a focus on the essential concepts and applications, it then moves on to more technical material. Still written in a textbook style with supporting evidence and proofs, the authors add many more exercises and examples and implement a two-step approach for some aspects of the material involving an initial introduction, examples, and basic results to be followed later by more detail and abstract results. Features Employs a widely accessible style to the explanation of combinatorial game theory Contains multiple case studies Expands further directions and applications of the field Includes a complete rewrite of CGSuite material This second edition of Lessons in Play reorganizes the presentation of the popular original text in combinatorial game theory to make it even more widely accessible. Starting with a focus on the essential concepts and applications, it then moves on to more technical material. Still written in a textbook style with supporting evidence and proofs, the authors add many more exercises and examples and implement a two-step approach for some aspects of the material involving an initial introduction, examples, and basic results to be followed later by more detail and abstract results. Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Dedication 6 Table of Contents 8 Preface 12 0: Combinatorial Games 18 0.1 Basic Terminology 20 Problems 24 1: Basic Techniques 28 1.1 Greedy 28 1.2 Symmetry 31 1.3 Parity 33 1.4 Give Them Enough Rope! 33 1.5 Strategy Stealing 34 1.6 Change the Game! 37 1.7 Case Study: Long Chains in Dots & Boxes 38 Problems 46 2: Outcome Classes 52 2.1 Outcome Functions 53 2.2 Game Positions and Options 54 2.3 Impartial Games: Minding Your Ps and Ns 59 2.4 Case Study: Roll the Lawn 62 2.5 Case Study: Timber 64 2.6 Case Study: Partizan Endnim 68 Problems 71 3: Motivational Interlude: Sums of Games 76 3.1 Sums 76 3.2 Comparisons 78 3.3 Equality and Identity 83 3.4 Case Study: Domineering Rectangles 85 Problems 88 4: The Algebra of Games 92 4.1 The Fundamental Definitions 92 4.2 Games Form a Group with a Partial Order 101 4.3 Canonical Form 106 4.4 Case Study: Cricket Pitch 113 4.5 Incentives 116 Problems 117 5: Values of Games 122 5.1 Numbers 122 5.2 Case Study: Shove 131 5.3 Stops 133 5.4 A Few All-Smalls: Up, Down, and Stars 135 5.5 Switches 141 5.6 Case Study: Elephants & Rhinos 142 5.7 Tiny and Miny 144 5.8 Case Study: Toppling Dominoes 145 5.9 Proofs of Equivalence of Games and Numbers 148 Problems 150 6: Structure 156 6.1 Games Born by Day 2 156 6.2 Extremal Games Born by Day n 158 6.3 More About Numbers 163 6.4 The Distributive Lattice of Games Born by Day n 165 6.5 Group Structure 167 Problems 168 7: Impartial Games 172 7.1 A Star-Studded Game 173 7.2 The Analysis of Nim 175 7.3 Adding Stars 177 7.4 A More Succinct Notation 178 7.5 Taking-and-Breaking Games 180 7.6 Subtraction Games 182 7.7 Keypad Games 192 Problems 195 8: Hot Games 198 8.1 Comparing Games and Numbers 199 8.2 Coping with Confusion 202 8.3 Cooling Things Down 205 8.4 Strategies for Playing Hot Games 212 8.5 Norton Products 214 8.6 Domineering Snakes 217 Problems 219 9: All-Small Games 224 9.1 Cast of Characters 225 9.2 Motivation: The Scale of Ups 232 9.3 Equivalence Under ✰ 233 9.4 Atomic Weight 236 9.5 All-Small Shove 240 9.6 More Toppling Dominoes 241 9.7 Clobber 242 Problems 246 10: Trimming Game Trees 250 10.1 Introduction 250 10.2 Reduced Canonical Form 251 10.3 Hereditary-Transitive Games 254 10.4 Maze 255 10.5 Ordinal Sum 256 10.6 Stirling-Shave 259 10.7 Even More Toppling Dominoes 263 Problems 265 ω: Further Directions 268 ω.1 Transfinite Games 268 ω.2 Algorithms and Complexity 269 ω.3 Loopy Games 270 ω.4 Kos: Repeated Local Positions 271 ω.5 Top-Down Thermography 271 ω.6 Enriched Environments 272 ω.7 Idempotents 272 ω.8 Misère Play 272 ω.9 Scoring Games 273 A: Top-Down Induction 276 A.1 Top-Down Induction 276 A.2 Examples 277 A.3 Why Is Top-Down Induction Better? 280 A.4 Strengthening the Induction Hypothesis 282 A.5 Inductive Reasoning 284 Problems 285 B: CGSuite 288 B.1 Installing CGSuite 288 B.2 Worksheet Basics 289 B.3 Programming in CGSuite’s Language 292 C: Solutions to Exercises 294 D: Rulesets 320 Bibliography 334 Index 338 A thorough revision of a popular text in combinatorial game theory, this second edition reorganizes presentation to make it more widely accessible.