بازرسی و ارزیابی در Hex (سحر و جادو)
جک ون ریجسویجک
بخش محاسبه علم دانشگاه آلبرتا ادمونتون
آلبرتا - کاندا T6G2H1
وضعیت هنر در برنامه‌های بازی Hex در حدود سال 2002 این است که کامپیوترها بتوانند به طور کامل روی موقعیت‌ها تا برد 6×6 بازی کنند و در برابری هستند با بهترین بازیکنان انسانی روی اندازه‌های برد تا حدود 9×9.
این گزارش به طور رایج وسایل مورد استفاده و پیشنهادی را برای بازرسی تخته بازی و اعمال ارزیابی کشف کننده را توصیف می‌کند.
1 مقدمه
برای یک مقدمه عالی برای بازی Hex و استراتژی آن نگاهی به کتاب Browne بیندازید.
مقالات مقدمه‌ای در مورد Hex در Scientific American by Gardner and stewart به چشم می‌خورد.
تکامل PSPACE از نسخه عمومی شده Hex توسط Even و Tarjan به اثبات رسیده است.
اثباتی برای خود Hex توسط Reisch عرضه شده بود.
وسایل الگوریتمی برای بازی Hex در این گزارش توصیف شده است که می‌تواند به صورت زیر خلاصه شود:
ارتباطات مجازی در برنامه Vadim Anshelevich Hexy (Ansoo): استفاده شده‌اند.
الگوهای تجزیه توسط Jing yang استفاده شده‌اند تا مقادیر باز 7×7 و 8×8 را اثبات کنند.
(YLPO1, YLPO2a, YLPO2b)
بازرسی الگو بر پایه روش yang است و تست شده است اما هنوز در برنامه Jack Van Rijswick استفاده نشده است.
Queen bee (Rijoo)
مدلهای شبکه در چندین فرم ارائه شده‌اند.
البته به طور قابل توجه در Hexy که یک شبکه الکتریکی مانند آن است.
فاصله هندسی در Queen bee استفاده شده است.
کاهش y توسط Steven Meyers پیشنهاد شده است که بر پایه مشاهدات توسط creaigschensted میباشد.
اولین سه روش در بخش 2 توصیف شده‌اند.
در حالیکه بخش 3 جریان شبکه و روشهای 2 فاصله را توصیف می‌کند.
وسیله کاهش y در بخش 4 ارائه شده است.
AppendixA شامل بعضی پیش زمینه‌ها روی ارائه هندسی Hex است.
2 جستجو (بازرسی)
نه ارتباط مجازی و نه الگوهای تجزیه روشهای بازرسی تخته بازی نیستند.
هر دو روش از الگوهای محلی ارتباطات اثبات شده، ایجاد الگوهای جدید از الگوهای کوچکتر استفاده می‌کنند.
انواعی از استفاده از الگوهای تجزیه که از الگوهای کروی استفاده می‌کنند به عنوان یک افزایش بازرسی تخته‌بازی ایمن در الگو بازرسی استفاده شده‌اند.
1-2- ارتباط مجازی
ارتباطات مجازی الگوهای محلی هستند که یک ارتباط را گارانتی می‌کنند.
دو نوع ارتباط مجازی وجود دارد: قوی و ضعیف، یک ارتباط ضعیف توسط قانون And ایجاد شده است که یک برنده گارانتی شده است که ابتدا بازیکن برنده را تأمین می‌کند.
یک ارتباط قوی توسط قانون or ایجاد شده است که یک برنده است بدون در نظر گرفتن اینکه چه کسی اول بازی می‌کند.
هر ارتباطی یک حامل دارد که نیستی مجموعه‌ای از خانه‌ها است که مورد نیاز است تا برای ارتباط با کار خالی شود.
قانون And در شکل 1-I نمایش داده شده است.
این قانون یک ارتباط ضعیف بین q,p را پایه‌گذاری می‌کند که تأمین می‌کند که برآمدگی میانی m خالی است و ارتباطات قوی بین m,p و بین q,m وجود دارد.
ارتباط می‌تواند توسط بازی در نقطه m ایجاد شود.
قانون And نیاز به 2 حامل دارد که نپوشاند و حامل نتیجه ارتباط ضعیف اتصال این دو حامل به اضافه خانه m است.
شکل 1-II کاربرد قانون or را نشان می‌دهد.
یک ارتباط قوی بین p,q وجود دارد اگر دو یا چند ارتباط ضعیف بین p,q باشد که تأمین می‌کند که حاملین این ارتباطات یک فاصله خالی دارند که مطمئن می‌کند که حریف نمی‌تواند تمام ارتباطات ضعیف را یکباره مسدود کند.
سپس ارتباط می‌تواند توسط قوی کردن یکی از ارتباطات ضعیف غیر متأثر ایمن شود.
حامل نتیجه ارتباط قوی اتصال حاملین ارتباطات ضعیف است.
یک زیان ارتباطات مجازی این است که آنها ناقص هستند.
با این حس که مثالهایی از موقعیت‌هایی وجود دارد که نمی‌توانند با قوانین And-or ثابت شوند.
شکل 2 مثالی می‌دهد که بر پایه داده شده در [Ansoo] است.
موقعیت یک ارتباط مجازی ضعیف است بین q,p جاییکه m یک حرکت برنده است.
روش ارتباط مجازی هدفی است برای اثبات ارتباط.
با پیدا کردن ارتباطات مجازی بین m,p و بین q,m که در این حالت به نتیجه نمی‌رسد.
چون هیچ ارتباط قوی مجازی بین m,p وجود ندارد.
همین داستان برای تنها حرکت برنده دیگر (به طور قرینه مساوی n) به کار می‌رود.
دلیلی که روش ارتباط مجازی نمی‌تواند این موقعیت را ثابت کند این است که قانون And شامل تعهد بی‌شرطی است که ارتباط برنده شدن می‌خواهد از نقطه میانی m استفاده کند.
در این حالت بازی با حریفی که مجبور شده است r را اشغال کند پیش می‌رود.
جواب برنده تک n است.
اگر حریف سپس s را بازی کند، ارتباط می‌تواند پایه ریزی شود اما شامل گره m نمی‌شود.
این شرط اصلی پنهانی قانون And را مختل می‌کند که چرا آن نمی‌تواند توسط بازریس ارتباط مجازی کشف شود
2.2 الگوهای تجزیه الگوهای تجزیه کاملا مشابه با ارتباطات مجازی هستند؛ آنها همچنین از الگوهای کوچکتر ساخته شده‌اند و مطمئن می‌کنند ارتباط بین 2 گروه از مهره‌ها را با یک الگویی از خانه‌ها که نیاز ایت برای این ارتباط با کار خالی باشد.
شکل 3 مثالی را نشان می‌دهد که گروههای b2,b1 یک ارتباط گارانتی شده دارند.
ارتباط از الگوی کوچکتر A استفاده می‌کند که a1 را به a2 مرتبط می‌کند.
دستور برای ارتباط بین a و b به صورت زیر است: ـ اگر حریف در یکی از (8و7و4و3و1) بازی کند سپس در 2 جواب دهد و سپس از الگوی A بین 2 و b2 استفاده کند.
اگر حریف در یکی از (6و5و2) بازی کند و سپس در 4 جواب دهد و از الگوی A استفاده کند بین b1 و 4 و الگوی A بین 4 و b2 .
یک فرق مهم بین ارتباطات مجازی و الگوهای تجزیه این است که الگوهای تجزیه می‌تواند شامل خانه‌های غیر خالی باشد.
یک مثال در شکل 4 نشان داده شده است.
خانه سیاه c1 در وسط مربوط است به گروه C2 در سمت راست که از گروه از خانه‌های دو تایی در سمت چپ استفاده می‌کند.
اگلوهای تجزیه می‌تواند هر موقعیت Hex باشد.
الگوهای تجزیه به طور مشخصی کارا هستند و Jimg yang را قادر می‌کند تا بعضی حرکت‌های باز 7×7 را ثابت کند با استفاده از تنها چندصد الگو که یک بازرسی تخته بازی به ترلیونها گره نیاز خواهد داشت.
بدبختانه هیچ الگوریتم غیرخودکار برای مسافت کتابخانه‌ای از الگوهای تجزیه تا کنون ساخته نشده است.
دلایل yang دستی ساخته شده‌اند و توسط کامپیوتر بازبینی شده‌اند.
3-2 بازرسی الگو بازرسی الگو توسط الگوهای تجزیه روح داده شده‌اند.
اما این الگو از الگوهای جهانی به جای الگوهای محلی استفاده می‌کند.
این الگو یک افزایش از بازرسی تخته‌بازی است.
شکل 5 نشان می‌دهد یک موقعیت تخته را که white برای حرکت کردن از دست داده است.
از دست رفتن آنها بستگی به سلولهای علامت‌گذاری شده «X» دارد.
تنها اگر White تمام خانه‌های بدون علامت را روی تخته اشغال می‌کرد، Black برنده می‌شد.
مجموعه‌ای از خانه‌های x الگوی گزارش است که از بافت‌دهی را ثابت می‌کند.
اگر white مثل شکل 5-II باز می‌کند، موقعیت نتیجه یک برنده است برای Black .
الگوی گزارش تعیین شده در نمودار تمام آنچه است که Black برای برنده شدن نیاز دارد و بدین جهت ثابت می‌کند که تمام خانه‌های بدون علامت در 5-II در حال از دست دادن حرکت‌هایی برای White در موقعیت قبلی بودند.
بدین ترتیب آن 15 حرکت اضافی را به یکباره تکذیب می‌کند برای بهبود بازرسی تخته بازی استاندارد که هر کدام از آن حرکت‌ها به طور مستقل باید تکذیب می‌شدند.
به طور رسیم یک مجموعه از سلولهای خالی در موقعیت Hex p یک الگوی گزارش است اگر نتیجه بازی تغییرناپذیر باشد حتی زمانیکه سمت از دست رفته تمام خانه‌های خالی را نه در اشغال کند.
یک الگوی گزارش برای یک موقعیت تک نیست چون اضافه کردن یک خانه خالی به یک الگوی گزارش همیشه الگوی گزارش معتبر دیگری را ایجاد می‌کند.
آنجا یک الگوی گزارش در هر موقعیتی وجود دارد چون الگو که شامل تمام خانه‌های خالی است همیشه اندکی معتبر است.
در موقعیت که بازی تمام شده است، الگوی گزارش یک بست خالی است.
در هر موقعیت دیگری P یک الگو است که می‌تواند محاسبه شود.
ـ اگر یک حرکت برنده m وجود داشته باشد، سپس p یک برنده است و الگوی گزارش شامل m همراه با از دست دادن الگوی گزارش از موقعیت نتیجه است.
ـ اگر هیچ حرکت برنده شدن نباشد، سپس یک مجموعه‌ای از الگوهای گزارش برنده شدن برای حریف وجود دارد یک فاصله خالی دارد و وحدت این الگوها، الگوی گزارش بازنده شدن برای p را تشکیل می‌دهد.
این دو قانون الگو مانند قوانین ارتباطات مجازی And, or هستند.
2.4 بازرسی الگوی تجزیه الگوهای گزارش منافع خودکار و کامل بودن را ترکیب می‌کنند اما کمتر کارا هستند.
چون الگوها محلی نمی‌باشند.
این مشکلی در موقعیت برنده شدن نیست.
چون تنها یک حرکت برنده شدن نیاز است تا امتحان شود.
اما این یک مشکل است در یک موقعیت بازندگی مثل در شکل I-6 الگوی بازندگی شامل 3 ارتباط محلی مستقل است.
هر گاه White در یکی از سه ارتباط محلی بازی کند، Blank به همان شکل جواب می‌دهد.
هر حرکتی توسط white خارج از الگوی گزارش نامربوط است و Blank می‌تواند در جواب از یک حرکت فرار کند.
در نتیجه تمام خانه‌ها خارج از الگوی گزراش خانه‌های مرده هستند و بازیکن برنده نیاز دارد که هرگز در هیچ کدام از آنها بازی نکند.
هر کدام از ارتباطات محلی می‌توانند به صورت مستقل ثابت شوند.
بازرسی الگو این را تشخیص نداده است.
برای هر حرکتی که White در منطقه c امتحان می‌کند، بازرسی بعدی ارتباطات را دوباره از a,b ثابت می‌کند.
در اینجا ممکن است یک راه برای ایجاد الگوی بازرسی باشد تا به طور مستقل الگوهای محلی را مطرح کند.
زمانیکه White حرکتی را در شکل 6-II امتحان می‌کند، بازرسی یک برنده را برای Black با الگوی تعیین شده برمی‌گرداند.
White اکنون توجه می‌کند که این الگو شامل 3 گروه از خانه‌ها است.
2 تا از این گروهها توسط آخرین حرکت بازی شده White به هم مربوط نمی‌شدند.
بنابراین White ممکن است اکنون موارد زیر را حدس بزند: اگر موقعیت حقیقتا یک بافت باشد و از دست دادن الگوی گزارش شامل زیر الگوهای مستقل باشد و سپس آخرین حرکت بازی شده تنها با یکی از زیر الگوها دخالت داشته باشد.
اجازه دهید گروههای مداخله‌گر آن گروههای الگو در 6-II باشند که همجوار با آخرین حرکت White می‌باشند و دیگر گروهها را دست نخورده بنامید.
اگر این حدس درست باشد سپس گروههای دست نخورده ارتباطات محلی قوی هستند و گروه مداخله شده یک ارتباط محلی ضعیف است.
این ارتباط محلی ضعیف بخشی از یک ارتباط محلی قوی است که هنوز کاملا کشف نشده است.
برای اثبات این حدس، White می‌تواند موقعیت را همانطور که در شکل 6-III نشان داده شده است تغییر دهد.
زیر الگوهای دست نخورده توسط مهره‌های سیاه جایگزین شده‌اند تا ارتباطاتشان را محکم کنند و آنها توسط مهره‌های سفید احاطه شده‌اند.
آخری ضروری است چون حدس این است که بخشهای باقیمانده از الگوی بافت در 6-I مستقل هستند از بخشی که هنوز کشف نشده است.
بدین جهت باید مجبور کرد که Black ببرد بدون استفاده از هیچ یک از خانه‌های مجاور با گروههای دست نخورده که با اضافه کردن مهره‌های سفید احاطه شده به انجام رسیده‌اند.
در موقعیتی که بدین ترتیب ایجاد شده است White تنها نیاز دارد که خانه‌های در گروه مداخله شده از 6-II را بازبینی کند.
اینها 3 خانه‌ای هستند که در 6-II تعیین شده‌اند.
اگر این بافتی را برای White در پی داشته باشد، سپس موقعیت 6-I همچنین بافتی برای White است و الگوی گزارش برای 6-I آن الگویی در 6-II است به اضافه گروههای دست نخورده 6-III .
بازرسی الگوی اکتشافی در حالیکه در تئوری خیلی قدرتمند است، الگوهای گزارش خیلی حساس به حرکت خوب هستند که در تمرین دستور داده شده است.
شکل 7 نشان می‌دهد مثالی را اگر حرکت در a اول امتحان شود، الگوریتم شامل این خواهد شد که موقعیت یک برنده است با الگوی گزارش شامل تنها یک خانه a .
اگر به عبارت دیگر حرکت ابتدا در b امتحان شود برنده ثابت شده است اما نتیجه الگوی گزارش شامل 3 خانه است.
الگو هنوز معتبر و درست است اما بزرگتر است از آنچه که نیاز است باشد.
زماینکه به الگوها برمی‌گردیم، آنها به طور سریع خیلی بزرگ رشد می‌کنند اگر مراقبت خاص نباشد تا آنها را به کوچکی که ممکن است نگه دارد.
یک الگو که تخته کامل را می‌پوشاند معتبر است اما همچنین مضر میباشد.
چون جستجو سپس یک جستجوی استاندارد آلفا-بتا میشود.
جنبه دیگر بازرسی الگو این است که این الگو می‌تواند تنها برنده‌ها و بازنده‌ها را ثابت کند.
این الگو مقادیر اکتشافی را پیدا نمی‌کند زمانیکه هیج دلیلی وجود نداشته باشد.
هر دو این مشکلات می‌توانند با استفاده از بازرسی الگو به عنوان یک افزایش بازرسی اکتشافی استاندارد آلفا- بتا سبک شوند.
اگر عمیق شدن تکراری استفاده شود سریع‌ترین برنده ابتدا در نظر گرفته میشود و الگوی گزارش تمایل دارد که به کوچکترین حد ممکن در نظر گرفته شود.
که جعلی برای یک الگوریتم افزایشی آلفا- بتا در Appendix B شامل شده است.
ارزیابی: روشهای رسیدن به ارزیابی‌های اکتشافی از موقعیت‌های Hex برای پیدا کردن سخت می‌باشند.
مفاهیمی مانند تعادل مواد و جنبش و دگرگونی که در خیلی دیگر از تخته‌های بازی مفید هستند، در Hex بی‌معنی هستند.
روشهای ارزیابی به طور معمول بر پایه اندازه‌گیری خصوصیات نمودار بازی هستند مانند جریان شبکه در Hex y و فاصله نمودار در Quecn bee .
تنها روش شناخته شده که از یک چنین مدلی استفاده نمی‌کند کاهش y است که در بخش 4 توصیف شده است.
مدلهای هندسی مانند جریان شبکه و فاصله از یک ارائه هندسی Hex طوریکه در شکل 8 نشان داده شده است استفاده می‌کنند که در آن Black سعی می‌کند بین t,s ارتباط دهد.
هر موقعیت 2 تا از چنین نمودارهایی را دارد، یکی از دیدگاه‌ها Black و دیگری دیدگاه White است.
برای توصیف این نمودارها Appendix A را ببینید.
3-1 جریان شبکه نمودار ارائه کاهش از یک موقعیت Hex می‌تواند دیده شود به عنوان یک جریان شبکه جاییکه مایعات از s به t جریان می‌یابند.
هر پیوند ظرفیت واحدی دارد به جز برای پیوندهایی که ازs به t سرچشمه می‌گیرند که ظرفیت معینی دارد.
حداکثر ظرفیت جریان از s به t به عنوان یک ارزیابی اکتشافی از موقعیت گرفته شده است.
به طور نزدیک بسته به این هدف مدل جریان الکتریکی است که مایع نیست اما الکتریسیته است که از میان شبکه عبور می‌کند.
ارتباطات شبکه در این حالت حداکثر ظرفیت را ندارند اما همه آنها مقاومت واحدی دارند.
ارتباطات در s و t مقاومت صفر دارند.
مقاومت کل بین s,t به عنوان ارزیابی اکتشافی از موقعیت استفاده شده است.
شانون و مور یک ماشین بازی فیزیکی Hex ساختند که از این وسیله استفاده کرد.
همین روش در Hexy استفاده شده است.
این مدل‌ها همچنین می‌توانند استفاده شوند تا فراهم کنند ارزشهای اکتشافی را برای حرکت‌های موجود که برپایه مقدار جریان اخیر از میان ارتباطات شبکه است.
Hex y از اسراف انرژی استفاده می‌کند از تمام ارتباطات همجوار با یک گره که در نمودار ارائه مقادیر برای تکمیل کردن مربع‌هایی از تمام مسیرها در آن پیوندها، طوریکه پیوندها همگی مقاومت واحدی دارند.
مدلهای جریان شبکه مربوط به مفهوم ارتباط هندسی هستند که رجوع می‌کند به تعداد راههای مشخص که دو راس را در یک نمودار مربوط می‌کند.
یک درجه بالایی از ارتباط منجر میشود به یک موقعیت مطلوب طوریکه راههای زیادی برای ارتباط وجود دارد.
3-2 فاصله هندسی فاصله هندسی بین s و t می‌تواند به عنوان یک تخمین اکتشافی از موقعیت استفاده شود.
طوریکه در n+1 شروع میشود و به 1 می‌رسد اگر و تنها اگر بازی برنده شود.
این تخمین کمی ضعیف است طوریکه می‌تواند دیده شود با تشخیص اینکه بازی یک حرکت در مرکز یک تخته خالی فاصله هندسی را برای حریف کاهش نمی‌دهد.
یک روش بهتر اندازه «2 فاصله» است که در Queen bee استفاده شده است.
در معیار فاصله هندسی منظم، فاصله یک راس U به گره t یک برابر بیشتر از فاصله حداقل همجواران u به t است.
با اندازه‌گیری فاصله این راه مقادیر برای محاسبه تعداد «حرکات آزاد» مورد نیاز برای کامل کردن ارتباط چشم‌پوشی از کوشش حریفان برای بستن این ارتباطات است.
2 فاصله به نظر می‌رسد در عوض در دومین فاصله کوتاه همسایگان U به t این بینش این است که حریف می‌تواند کوتاه‌ترین فاصله را ببندد.
Queenbee دو فاصله را به دو مرز در نمودار کاهش black خلاصه می‌کند.
کوچکترین این اعداد به عنوان فاصله کل سیاده در نظر گرفته شده‌اند.
و تعداد رویدادهای این فاصله در برد بالقوه سیاه است.
زمانیکه دو موقعیت فاصله یکسان بین دو مرز دارند، سپس موقعیت با بالاترین عامل بالقوه ارجح است.
گویا که راههای بیشتری برای تشخیص این فاصله وجود دارد.
ارزیابی کامل برد توسط محاسبه تعداد یکسان برای White در نمودار سفیدرنگ تهیه شده است و سپس فرق بین این اعداد را برای مشکی و برای سفید در نظر می‌گیرد.
حرکات توسط جمع کردن اعداد سفید و سیاه در هر سلول ارزیابی شده‌اند.
با تشخیص اینکه خانه‌های مهم آنهایی هستند که نزدیک به پایه‌ریزی برای یک ارتباط برنده‌شدن برای هر دو بازیکن هستاند.
علی رغم جریان شبکه و مدلهای ارتباط 2 فاصله طبیعت حریف از یک بازی 2 بازیکنه را می‌گیرد.
گرچه آن از یک مانع مهم رنج می‌برد، می‌تواند گاهی اوقات یک موقعیت را زمانیکه در واقع یک برنده است برچسب بزند.
یک مثال در شکل 9 نشان داده شده است.
2 فاصله سیاه بین مرزهای سیاه گسترده میباشد.
در حالیکه 2 فاصله سفید بین مرزهای سفید اینطور نیست.
معیار دو فاصله شامل این میشود که سیاه بازنده است.
در واقع موقعیت یک برنده برای سیاه حتی زمانیکه سفید ابتدا بازی می‌کند میباشد.
چنین موقعیت‌های انحراف از حالت طبیعی نادر هستند.اما آنها در بازرسی/جستجوهای تخته بازی اتفاق می‌افتند و ممکن است گاه‌گاهی نتیجه جستجو تغییر کند.
4 تبدیلy بازی y توسط Graig Schensted کشف شده است که به طور نزدیک مربوط به Hex میباشد.
به علاوه Hex یک حالت خاص از آن باشد.
این بازی را PSPACE کامل می‌کند و هر روشی برای بازی Y فورا یک روشی را برای بازی Hex ارزانی می‌دارد.
چنین روش کاهش Y است که بر پایه مشاهدات توسط Graig Schinsted و Steren Meyers میباشد.
4-1 بازی y بازیy روی یک تخته مثلثی شکل که با موزاییک‌های شش گوش فرش شده است بازی میشود.
هدف این است که یک زنجیرهای بنا نهاده شود که تمام سه طرف تخته را به هم مرتبط کند مانند شکل 10 شکل 11 شرح می‌دهد که Hex یک حالت خاصی از y است.
بازی y در این شکل مساوی با بازی Hex در منطقه خالی است.
بدین ترتیب یک اندازه تخته n × Hex n می‌تواند به یک اندازه تخته y 2n-1 تبدیل شود با اضافه کردن 2 منطقه مثلثی شکل.
هر منطقه با مهره‌هایی از رنگی از مرز Hex پر شده است که به آن متعلق است.
با بحث مانند آنهایی که در Hex استفاده شده است، می‌تواند دیده شود که y نمی‌تواند در یک بخت آزمایی به پایان برسد و باید برای اولین بازیکن یک برنده تئوریکی باشد.
یک راه رسیدن به یک اثبات شگفت‌آور از صفت خاص بدون بخت‌آزمایی بر پایه کاهش میکرو است که در بخش بعدی توصیف شده است.
4-2 کاهش میکرو در نظر بگیرید یک تخته y با سایز n را کاملا با مهره‌های سیاه و سفید مانند شکل 12-I پر شده است.
این تخته سپس به یک تخته با سایز n-1 کاهش می‌یابد جاییکه هر خانه روی تخته n-1 مربوط میشود به یک گروهی از سه خانه روی تخته n ، این 3 خانه باید همجوار باشند و تشکیل یک مثلث جهت‌یابی شده مثل کل تخته را تشکیل دهد.
تخته n-1 سپس با مهره‌های سیاه و سفید پر می‌شوند جاییکه رنگ یک خانه توسط اکثریت رنگ‌های سه خانه روی تخته بزرگتر تعیین شده است.
همینکه آن به نتیجه مطلوب می‌رسد، رنگ مهره تک روی تخته سایز 1 تعیین می‌کند که چه کسی در هر کدام از تخته‌های قبلی برنده بوده است.
این به خاطر این است که هر غیر از یک رنگ با یک مرحله کاهش نگه داشته شده است طوریکه هر پیوند در زنجیر مربوط به یک مثلث کوچک با حداقل 2 مهره از آن رنگ میباشد.
اگر یک زنجیر یک طرف تخته را لمس کند، سپس زنجیر مربوطه در تخته کاهش یافته هم همینطور خواهد بود.
یک زنجیره برنده بدین ترتیب زنجیرهای برنده مربوطه را در تمام تخته‌های کوچکتر تولید خواهد کرد.
شامل تخته نهایی سایز 1-که در آن یک زنجیر برنده به سادگی یک مهره روی تخته است و این روش کاهش میکروفورا ثابت می‌کند که y نمی‌تواند در یک بخت‌ازمایی به پایان برسد.
با توسعه بیشتر، ان یک اثبات بدون بخت آزمایی برای Hex می‌دهد که کاملا متفاوت از آنها است که توسط Gale, Beck داده شده است.
4-3 کاهش ماکرو یک تخته y همچنین می‌تواند به یک تخته با یک سایز کوچکتر تبدیل شود با حذف کردن یکی از سه ردیف مرزی.
این کاهش ماکرو نام دارد.
هر موقعیتی سه زیر موقعیت کاهش ماکرو دارد.
مشاهده این است که یک موقعیت شامل یک زنجیر برنده است اگر و تنها اگر حداقل 2 تا از 3 زیرموقعیت کاهش ماکرو وجود داشته این می‌تواند دیده شود توسط تشخیص اینکه برنده‌های سه زیر موقعیت به طور آماده‌ای در تخته سایز 2 از مرحله یکی مانده به آخر در زنجیر کاهش ماکرو نشان داده شده‌اند.
کاهش ماکرو یک روش قابل قبول را برای بازی y پیشنهاد نمی‌کند چون آن تخته را از هم متلاشی می‌کند به زیرموقعیت‌های n3 که عددی است خیلی بزرگتر از مهره‌های o(n3) که کاهش ماکرو ایجاد می‌کند حتی زمانیکه در نظر گرفته میشود که نسخه‌های زیادی در بردی از زیرموقعیت‌های کاهش یافته ماکرو وجود داشته باشد.
4-4 کاهش نسبی تخته‌های خالی اگر کاهش ماکرو بتوان به موقعیت‌های با خانه‌های خالی گسترش یابد یک روش ارزیابی اکتشافی برای y و برای Hex به وجود آمده است.
یک راه برای انجام آن این است که احتمالی از ارتباط به هر خانه تخته اختصاص داده شود.
خانه‌ها که هم‌اکنون شامل مهره‌ها هستند احتمال 1 یا 0 دارد بر اساس اینکه چه کسی آنها را دارد .
خانه‌های خالی احتمال ½ دارند.
زماینکه کاهش یک مثلث از سلولهای با احتمالات p3,p2,p1 دو احتمالا g از خانه کاهش یافته احتمال داشتن حداقل 3 تا از خانه‌های Pi است.
بر اساس تئوری احتمال: q=p1p2+p1p3+p2p3-=p1p2p3 در واقع y بازی شانس نیست.
به علاوه احتمالات Pi مستقل نیستند.
چون بازی یک مهره روی یک تخته یک تعداد در حال رشد از احتمالات تا زنجیری از اشکال هندسی کاهش یافته را تغییر می‌دهدذ.
علی‌رغم این، این روش ممکن است یک راه خوب سریع – و – کثیف را برای یک ارزیابی اکتشافی از موقعیت y فراهم کند.
برای آسان کردن موضوع‌ها فاصله ]1- و 1+[ می‌تواند به جای ]1و0[ استفاده شود.
در آن حالت مهره‌های بازی شده مقدار 1- و 1+ دارند و یک خانه خالی مقدار 0 دارد.
بدین ترتیبات وی این‌گونه میشود: q=1/2 (p1+p2+p3-p1p2p3) این روش کاهش هرمی از مقادیر را ایجاد می‌کند که شروع میشود با خانه‌های از تخته با زی و به مقدار تکی از تخته سایز 1 که ارزیابی نهایی را ارائه می‌دهد می‌رسد.
تعداد محاسبات که در زنجیر کاهش کامل انجام شده‌اند n(n+1)(n+2) 1/6 میباشد.
محاسبات می‌توانند به طور افزایشی انجام شوند چون تمام آنها محلی می‌باشند که این ذخیره می‌کند بخشی از کار را به عنوانی بازی یک حرکت که اکثر مقادیر بدون تغییر را روی تخته‌های بزرگتر در زنجیر کاهش باقی می‌گذارد.
5-4 ارزیابی حرکت دگرگونی اکتشافی می‌تواند به میزان حرکت‌های موجود استفاده شود.
درست‌ترین راه انجام این است که هر حرکتی امتحالن شود و دیده شود که چقدر ارزیابی تغییر می‌کند که O(n2)×O(n3) مقدار می‌رسد.
یک تخمین خوب خیلی سریعتر می‌تواند توسط محاسبه مشتق نسبی ارزیابی نهایی با رجوع به هر کدام از مقادیر در هرم کاهش بدست آید.
اینها می‌توانند به آسانی محاسبه شوند و اگر V ارزیابی نهایی باشد.
این سه سهمی از A(p1p2p3) است.
چون p1 معمولا بخشی از 3 مثلث کاهش یافته است، سهم‌هایی از دیگر مثلث‌ها نیاز است تا اضافه شوند.
این محاسبه یک هرم ثانویه از مقادیر 5(n3) را در مراحل 0(n3) با استفاده از مقادیری در هرم کاهش شامل می‌شوند می‌سازد.
هرم ارزیابی حرکت در جهت دیگری ساخته شده است که با نمودار سایز 1- شروع میشود.
مشتقات نسبی پیش‌بینی‌های دقیقی برای تغییر در v نیستند.
A نمودار هندسی Hex Hex یک حالت خاص از بازی Shannon Switching است، یک بازی نمودار نقطه رنگی بازی Shannon Switching می‌تواند در هر نمودار توسط انتخاب 2 نقطه S,T باز میشود و به بازیکنان سیاه مهارت دهد تا این دو نقطه را به هم مرتبط کند.
در حالیکه بازیکن سفید سعی می‌کند از آن جلوگیری کند.
شکل 13 نشان می‌دهد یک نمودار هندسی بازی را که مساوی با تخته Hex 5×5 است.
زمانیکه White یک نقطه V را رنگ می‌کند، موقعیت نتیجه مساوی آنی است که V به سادگی از نمودار حذف شده است.
به طور مشابه یک حرکت توسط Black مساوی به هم رسیدن نقطه‌هاست که به معنی جداکردن آن از نمودار و معرفی لبه‌های جدید بین هر جفت از همجواران v است.
بدین ترتیب نمودار هندسی توسط یک نقطه هر حرکت کاهش می‌یابد.
شکل 14 نشان می‌دهد یک موقعیت در بازی رنگی نمودار در سمت چپ را و موقعیت مساوی در نمودار بازی کاهش را در سمت راست.
نمودار در شکل 14 بازی را از نقطه نظر Black ارائه می‌دهند.
همین موقعیت می‌تواند از نقطه نظر سیاه مثل شکل 15 ارائه شود.
الگوریتم‌ها در زیر کد کاذب برای الگوی الگوریتم جستجو و الگوریتم کاهش y دنبال میشود.
الگوی جستجوی پایه در جدول 1 تنها برنده‌ها و بازنده‌ها را برمی‌گرداند و هیچ ارزش اکتشافی ندارد.
عمل امدادی (P) آشکار می‌کند یک زنجیره برنده برای جهت حرکت در موقعیت p را.
ارزشهای برگشتی شامل یک ارزش برنده / بازنده با یک الگوی گزارش که این نتیجه را ثابت می‌کند میباشد.
همانطور که در تعریف از یک الگوی گزارش گفته شد، هر چیزی خارج از الگو بر برنده یا بازنده تاثیر نمی‌گذارد.
جدول 2 نشان می‌دهد چگونه جستجوی پایه‌ای آلفا-بتا را با جستجوی الگو افزایش دهیم.
جستجو مانند آلفا- بتا عمل می‌کند به اضافه الگوهای گزارش که هر وقت که ارزش یک برنده یا بازنده ثابت شده است برمی‌گرداند.
اگر ارزش برگشتی یک ارزش اکتشافی باشد، الگوی گزارش برگشتی چشم‌پوشی شده است.
ارزیابی عمل کمک‌کننده(P) یک ارزیابی اکتشافی از موقعیت p را تامین می‌کند که باید به طور محدودی بیشتر از بازنده یا کمتر از برنده باشد.
جدول 3 شامل الگوریتم کاهش Y برای محاسبه ارزیابی تخته ابتکاری به خوبی ارزیابی‌های حرکت فردی میباشد.
الگوریتم در ابتدا ]در نظر می‌گیرد...[ ]...[eval با حجم‌هایی از تخته و سپس محاسبه می‌کند کاهش‌های پی‌درپی Y را با استفاده از که f(p,q,r)=1/2 (p+q+r-2pqr)و e(k) شامل مقادیر در مثلث اندازه k+1 است.
در نهایت eval[0][0][0] رسیده است که شامل ارزش ابتکاری نهایی است.
سپس مقادیر حرکتی محاسبه‌شده‌اند که با حرکت 1=[0][0][0] شروع میشود و استفاده می‌کند از الگوریتم جستجو می‌تواند با هر افزایش مطلوب آلفا=بتا درست به همان طویل که توجه گرفته شده است که مقادیر برنده یا بازنده تنها برگردانده شده‌اند زمانیکه آنها ثابت شده‌اند و الگوها استفاده شده‌اند تنها زماینکه مقدار ثابت شده است.
الگوریتم کاهش y می‌تواند با انجام محاسبات همینکه حرکت‌ها روی تخته ایجاد شدند یا نشدند پیشرفت کند.
الگوریتم که در جدول 3 نشان داده شده است مقادیر را برای بازی y محاسبه می‌کند که به آسانی برای Hex n*n تغییر می‌کند.
با تبدیل موقعیت y با سایز تخته 2,2n-1 ناحیه مثلثی شکل ایجاد می‌کند که به طور مناسبی در بخش 1-4 و شکل 11 توصیف شده است.