پیاده سازی درخت و لیست پیوندی

[hharddy]

سلام من برای پروژه یکی از درسام باید یه بازی شبیه "اتللو ریورسی" طراحی کنم و از ساختمان داده های مختلف استفاده کنم, بازی ای که من الان طراحی کردم فقط با ارایه پیاده سازیش کردم امکانش هست دوستان راهنمایی کنند که چجوری باید از درخت و لیست پیوندی تو این بازی استفاده کنم؟ یعنی کاربردش تو کدوم قسمت بازی هست؟

[vahid-p]

موضوع تاپیک رو بد انتخاب کردید. نوشتید "پیاده سازی درخت و لیست پیوندی" در صورتی که سوال شما نحوه استفاده از این دو در بازیتون هست. موضوع مناسب شاید این باشه "نحوه استفاده از درخت و لیست پیوندی در بازی اتللو یا ریورسی" یا "الگوریتم های مبتنی بر درخت، برای بازی اتللو یا ریورسی".

من با این بازی آشنایی ندارم ولی اگر از آرایه استفاده کردید و برنامتون جواب میده، لیست پیوندی هم تفاوت چندانی با آرایه نداره، فقط محدودیتی مثل آرایه نداره که بخواید از قبل اندازش رو مشخص کنید. اما فکر می کنم بازی شما یک نفره (به همراه کامپیوتر) است که در نتیجه نیاز به هوش مصنوعی دارد. این رو هم باید سرچ کنید چون بعیده کسی اینجا این بازی رو قبلا نوشته باشه که الان بتونه سریع بهتون جواب بده
اما با سرچی که زدم، الگوریتم های مختلفی برای این بازی ارائه دادن که خب مسلما بعضیاش به سادگی به ذهن خطور میکنه ولی ممکنه کامپیوتر حریف قدری نباشه (مثلا الگوریتم های حریصانه که در هر گام سعی کنه بیشترین تعداد مهره رو همرنگ خودش کنه). اما هر الگوریتمی نسبت به دیگری برتری داره و این هنر شما رو میرسونه از کدوم استفاده کنید و شاید بخواید تلفیقی یا ابتکاری عمل کنید. یا مثلا حالت های خاص رو هم به بازیتون اضافه کنید.
تمام اینا بحث الگوریتمی هست و ربطی به زبان برنامه نویسی نداره و شاید در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها (http://barnamenevis.org/forumdisplay.php?40-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%D 8%8C-%DA%A9%D8%A7%D9%85%D9%BE%D8%A7%DB%8C%D9%84%D8%B1%D 8%8C-%D9%87%D9%88%D8%B4-%D9%85%D8%B5%D9%86%D9%88%D8%B9%DB%8C-%D9%88-%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86-%D8%AF%D8%A7%D8%AF%D9%87-%D9%87%D8%A7) بهتر به جواب برسید. اما اگر الگوریتمتان مشخص است و فقط روی پیاده سازیش در زبان بخصوصی به مشکل برخوردید، در این انجمن بیشتر جای بحث داره.

کلام رو خلاصه کنم، فکر میکنم از منابع موجود اینترنت استفاده کنید، سریعتر به جواب برسید.
مثلا در لینک روبرو این بازی، استراتژیها و... رو توضیح داده که شاید برای راه حل های ابتکاری بخواید پیاده کنید مفید باشه:http://mathgame.ir/none-combinatorial-games/53-othello-first-lessons.html
یا در لینک روبرو سعی داشته از الگوریتمی برای هوش مصنوعی استفاده کنه که اتفاقا به گفته شما از درخت استفاده کرده: http://mnemstudio.org/game-reversi-example-2.htm

سرچ کنید به نتایج مشابهی میرسید.

[hharddy]

موضوع تاپیک رو بد انتخاب کردید. نوشتید "پیاده سازی درخت و لیست پیوندی" در صورتی که سوال شما نحوه استفاده از این دو در بازیتون هست. موضوع مناسب شاید این باشه "نحوه استفاده از درخت و لیست پیوندی در بازی اتللو یا ریورسی" یا "الگوریتم های مبتنی بر درخت، برای بازی اتللو یا ریورسی".

من با این بازی آشنایی ندارم ولی اگر از آرایه استفاده کردید و برنامتون جواب میده، لیست پیوندی هم تفاوت چندانی با آرایه نداره، فقط محدودیتی مثل آرایه نداره که بخواید از قبل اندازش رو مشخص کنید. اما فکر می کنم بازی شما یک نفره (به همراه کامپیوتر) است که در نتیجه نیاز به هوش مصنوعی دارد. این رو هم باید سرچ کنید چون بعیده کسی اینجا این بازی رو قبلا نوشته باشه که الان بتونه سریع بهتون جواب بده
اما با سرچی که زدم، الگوریتم های مختلفی برای این بازی ارائه دادن که خب مسلما بعضیاش به سادگی به ذهن خطور میکنه ولی ممکنه کامپیوتر حریف قدری نباشه (مثلا الگوریتم های حریصانه که در هر گام سعی کنه بیشترین تعداد مهره رو همرنگ خودش کنه). اما هر الگوریتمی نسبت به دیگری برتری داره و این هنر شما رو میرسونه از کدوم استفاده کنید و شاید بخواید تلفیقی یا ابتکاری عمل کنید. یا مثلا حالت های خاص رو هم به بازیتون اضافه کنید.
تمام اینا بحث الگوریتمی هست و ربطی به زبان برنامه نویسی نداره و شاید در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها (http://barnamenevis.org/forumdisplay.php?40-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%D 8%8C-%DA%A9%D8%A7%D9%85%D9%BE%D8%A7%DB%8C%D9%84%D8%B1%D 8%8C-%D9%87%D9%88%D8%B4-%D9%85%D8%B5%D9%86%D9%88%D8%B9%DB%8C-%D9%88-%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86-%D8%AF%D8%A7%D8%AF%D9%87-%D9%87%D8%A7) بهتر به جواب برسید. اما اگر الگوریتمتان مشخص است و فقط روی پیاده سازیش در زبان بخصوصی به مشکل برخوردید، در این انجمن بیشتر جای بحث داره.

کلام رو خلاصه کنم، فکر میکنم از منابع موجود اینترنت استفاده کنید، سریعتر به جواب برسید.
مثلا در لینک روبرو این بازی، استراتژیها و... رو توضیح داده که شاید برای راه حل های ابتکاری بخواید پیاده کنید مفید باشه:http://mathgame.ir/none-combinatorial-games/53-othello-first-lessons.html
یا در لینک روبرو سعی داشته از الگوریتمی برای هوش مصنوعی استفاده کنه که اتفاقا به گفته شما از درخت استفاده کرده: http://mnemstudio.org/game-reversi-example-2.htm

سرچ کنید به نتایج مشابهی میرسید.

سلام دوست خوبم
درباره عنوان تاپیک ممکن حق با شما باشه نخواستم زیاد عنوان طولانی بشه ممنون از گوشزد.
هوش مصنوعی هم بله باید استفاده کنیم ولی به عنوان آپشن و نمره اضافی هست نمره اصلی پیاده سازی این ساختمان داده ها و منطق صحیح بازیست.
این بازی به این شکل است که با محاصره کردن مهره حریف بصورت افقی و عمودی و یا اوریب رنگ و مهره و تغییر میدید به رنگ خودتون.
در قسمت محاصره افقی من تا اینجا لیست پیوندی دو طرفه نوشتم و میاد چک میکنه اگر رنگ خونه من با گره بعدی و قبلیش متفاوت بود به رنگ اون دوتا درمیاد.
تا اینجا فکر کنم درست رفتم مشکل من الان با تغییر رنگ عمودی و مورب هست
برای تغییر رنگ عمودی باید از درخت استفاده کنم حتما؟ نمیشه با همین لیست کار کنم؟
ممنون

[vahid-p]

اگر هوش مصنوعی نمیخواید که کارتون خیلی سادست (درخت max-min برای هوش مصنوعی بود)
اصلا نیازی به هیچ ساختمان داده خاصی نداره. مگر اینکه متوجه نوع بازی نشده باشم.
شما یک آرایه n*n (یک ماتریس) از نوع int یا byte یا short و... که کل صفحه رو بپوشونه (هر عنصر آرایه، نماینده یک خانه در بازی) رو لازم دارید و به هیچ چیز دیگه ای نیاز ندارید. بقیش یک سری الگوریتم های سادست (که حتی نمیشه بهش گفت الگوریتم تا شرایط بازی رو چک کنید)

ابتدا تمام خانه های آرایه صفر است (به معنی اینکه هیچ مهره ای قرار ندارد). همچنین مثلا عدد 1 رو برای رنگ سفید و -1 رو برای رنگ سیاه در نظر بگیرید.

حالا شما در هر مرحله باید چند چیز رو چک کنید:
1- نوبت کدوم بازیکن هست:
که با یک متغیر boolean میتونید اینکار رو انجام بدید

2- آیا مهره در محل درستی قرار گرفته یا خیر
محل درست مهره سه شرط داره: 1- در داخل صفحه باشد (یعنی متناظر یک خانه در آرایه باشد) 2- در محلی در آرایه قرار گیرد که قبلا صفر بوده باشد (اگر غیر این بود یعنی قبلا این خانه اشغال شده) 3- در 8 خانه کناری اون حداقل یکی از خانه ها غیر صفر باشد.

3- پس از چک کردن شرط دوم، و قرار گرفتن مهره جدید، باید از تمام خانه های همرنگ با مهره فعلی رو شناسایی کنید، اونهایی که در سطر برابر هستند یا در ستون برابر هستند و یا به صورت مورب 45 درجه در نظر بگیرید و بقیه مهره ها نیازی به در نظر گرفتنشون نیست (خب همه این مهرهایی که اهمیت دارن، میتونی سطر و ستون (یعنی آدرسشون در آرایه) رو در یک لیست ذخیره کنی و یکی یکی بررسی کنی و از لیست حذف کنی). حالا باید بین مهره های شناسایی شده درون لیست و نقطه مقصد تمام مهرهای غیر همرنگ (اگر مهره فعلی 1 است، تمام -1 ها در مسیر مستقیم بین این دو) رو 1 کنید. و به همین ترتیب ادامه بدید.

البته بازی یک سری شرط ههای دیگه هم داره که لازمه در موردش بخونید. کلا شروطی که لازمه اعمال بشن خیلی سادست و نیاز به کار خاصی یا استفاده از ساختمان داده خاصی نیست.