درختی نداریم که این خصوصیات رو داشته باشه؟

[Ner'zhul Arthas]

یک درختی میخوام بسازم که:
1. بشه شاخه هاش رو با خود اصلیش عوض کرد.
2. در هر برگش بشه خوصوصیات زیر رو داشت.
3. سرعتش کند نباشه.

من اینو ساختم ولی درست کار نمیکنه:


Private Structure RateStructure
Public Rate As Long
Public X1 As Byte
Public Y1 As Byte
Public X2 As Byte
Public Y2 As Byte
Public NextRate As Array
End Structure


که NextRate داخلش آرایه ای از نوع همین RateStructure قرار میگیره ولی بعد از مدتی دچار مشکل میشه.

[Alireza_Salehi]

یعنی چی با خود اصلیش عوض کرد؟

مشکلش رو هم که نگفتید ، بر اساس چه منطقی همچین ساختاری برای درخت تعریف کردید!

این چه نوع درختیه؟

اگر با کلاس درختتون رو تعریف کنید خیلی بهتره!


تمام انواع درختها و عملیات اونها در کتاب های ساختمان داده موجوده!

[Ner'zhul Arthas]

با خود اصلیش عوض کرد یعنی:

شاخه ی اصلی رو مساوی یکی از زیر شاخه هاش قرار بدیم.
بعد اون زیر شاخه ه میشه همون شاخه ی اصلی.

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

این درخت مثل بقیه درختاست فقط هر برگش چند خصوصیت که اونجا نوشتم داره. یعنی x1 , y1 ,...

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

[Alireza_Salehi]

در یک درخت هیچ وقت مستقیما یک گره را مساوی فرزندانش قرار نمیدهند ، اول باید گره های اضافی رو Free کنید.در ضمن ما از کجا بدونیم چه اروری یا مشکلی داره (پیام خطا یا مشکل رو شرح بدید)!

منظورم این بود که آیا این یک درخت عمومیه یا تعداد فرزندان هر گره ثابته؟

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

[Ner'zhul Arthas]

مشکلش نا معلومه دو دو تا رو میده پنج تا!
به هر حال از فکر حل کردن مشکل اون استراکچر بیاید بیرون.

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

تعداد فرزندای هر شاخه ثابت نیست ممکنه یکی باشه ممکنه نودتا.

مشکل من همین تعریف گره هاست.

چطوری تعریف کنم؟

[__H2__]

سلام
سریعترین راه استفاده از Collection ها است.
مثلاَ کدی شبیه زیر:


Public Class Node
Public Child As New System.Collections.Hashtable
Public Parent As Node
Public value As RateStructure
End Class


البته این کد برای نمونه است و باید آن را بست و توسعه دهید.

راه های بسیار دیگری هم دارد، مثلاَ به جای ذخیره مجموعه فرزندان، فقط اشاره گر اولین فرزند را ذخیره کنید و نیز هر فرزند بدانید فرزند بعدی کیست و والدش کیست و.... و... و...

البته میتوانید از Node های کنترلر TreeView هم استفاده کنید.
چند وقتی نیستم ولی اگر خواستید و توضیح بیشتری دادید میتوانم کد دقیقتری را بدهم.
توضیح بیشتر را برای آن میگویم که برخی از روش ها برای اطلاعات کم مناسب است و در مبنای زیاد به RAM فشار می آورد در عوض خیلی سریع است و برخی دیگر کمی کند تر است ولی از جهت RAM بسیار کم مصرف.
مثلاَ یک سوال، این درخت شفیق شما! قرار است نهایتاَ چند شاخه و برگ و ایل و تبار داشته باشد؟؟؟

[Ner'zhul Arthas]

حدودا 20 به توان 7.

[titbasoft]

اگر منظورتون یک درخت باینری است:
http://www.codeproject.com/vb/net/SimpleBTree.asp

البته توجه کنید که یک درخت یک ساختار داده ای است که خودش به طور مستقیم جزئیات (پراپرتی هایی که گفتید) رو نگهداری نمیکنه. اگر دقت کنید هر نود یک value داره از نوع object این object می تونه یک تایپ خاص باشه که خودتون ساختیدش.

[Ner'zhul Arthas]

نه، اگر باینری بود که خیلی راحت بود.

کار با کلکسیون چطوریه؟
نمیشه به جای کلکسیون یه جور آرایه گذاشت؟ یا چیز دیگه ای؟

[titbasoft]

شاید سوالم رو این طوری بپرسم بهتر باشه. شما اصلا چی کار می خواین بکنین؟! منظورم اینه که سناریویی که روش کار می کنید رو یکم توضیح بدید. چون من هنوز شاید صورت مساله رو درست متوجه نشدم

[Alireza_Salehi]

یکی از روش های رایج پیاده سازی درخت عمومی (تعداد فرزند متغییر) استفاده از لیسته ، که فکر کنم با توجه به مطالب اولین پست هدف شما هم همین بوده ، با این حال روش پیاده سازی درخت (ارتباط بین گره ها ، فرزندان و ...) وابستگی زیادی به کاربرد داره ، اگر کاربرد این درخت رو شرح بدید بهتر می تونیم کمکتون کنیم.

[Ner'zhul Arthas]

این درخت رو برای هوش مصنوعی شطرنج میخوام.

روش کارش اینه که تمام حالات ممکن رو که کامپیوتر میتونه انجام بده بدست میاره و بهشون امتیاز میده و لیست میکنه.

بعد میره تمام حالات بعدی رو چک میکنه. یعنی وقتی مثلا حرکت e2e4 رو کرد حریف چه حرکت هایی میتونه بکنه و اون حرکتا هر کدوم چه امتیازی دارن.
بعد اینا رو هم لیست میکنه در زیرشاخه ی همون حرکتی که نتیجش این حرکات میشده.
و این عمل هی تکرار میشه تا محلت فکر کردنش به پایان برسه و بعد با محاسبه ی بالاترین امتیاز بهترین حرکت رو انجام میده.

[Alireza_Salehi]

اگر از الگوریتم Minimax (جستجوی اول عمق) برای شطرنج استفاده کنید نیازی به درخت ندارید، یک روال بازگشتی که به صورت منطقی یک درخت را شبیه سازی میکند جستجو را انجام میدهد و بهترین حرکت بعدی را پیدا می کند و نیازی به وجود واقعی درخت نیست، می تونید محدودیت زمانی رو هم به اون اعمال کنید.

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

ساختن درختی با این ابعادی که شما گفتی هم حافظه می خواد هم جستجوی این درخت کندتر از روشهای هوش مصنوعیه، روش Minimax بعلاوه Alpha-beta Pruning برای این کار خوبه البته روش های جستجوی زیادی در هوش مصنوعی با مزایا و معایب مختلف وجود داره.

برای نگه داشتن سابقه حرکات هر بازیکن هم یک لیست کافیه.

[Ner'zhul Arthas]

این minimax چطوریه؟
چطور کار میکنه؟ لینکی چیزی دارید بدید.

این روشی که من مخوام استفاده کنم نیاز به ده بار فکر کردن نداره مدام فکر میکنه مثل انسان. وقتی حریفش بازی میکنه این بازم داره فکر میکنه.
وقتی بازی کرد هم ادامه میده فکر کردنشو، دوباره از اول فکر نمیکنه.
تو روشای دیگه همچین چیزی است؟

[Alireza_Salehi]

این الگوریتم قابل استفاده در بازیهای n نفره ست (که البته شطرنج 2 نفره است)

این الگوریتم دو بخش اصلی داره اولی حرکت های مجاز برای هر وضعیتی(در هر حالتی از بازی که باشیم) رو تولید میکنه دومی به این حرکت ها امتیاز میده (با توجه به وضعیت حریف- تا چه حد این حرکت ها به نفع ماست)، بعد یک روال بازگشتی با توجه به حدی که براش تعریف شده (محدودیت عمق( تا چند حرکت بعدی رو می خواهید پیش بینی کنید) ، محدودیت زمانی، محدودیت منابع ،...) بهترین حرکت رو (با توجه به امتیاز ها) انتخاب میکنه.

فقط کافیه در هر لحظه ای که نیاز به حرکت وجود داره (نیازی به از اول فکر کردن نیست) این روال بازگشتی رو با ورودی وضعیت فعلی و حد مورد نظر صدا بزنید ،بهترین حرکت بعدی رو بهتون میده!

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

http://ai-depot.com/LogicGames/MiniMax.html

در مورد minimax تو goolge جستجو کن مطلب زیاد هست. ولی اگر دنبال مطلب فارسی میگردی کتاب های هوش مصنوعی مهرداد فهیمی ، رامین رهنمون و ... در بازار هست همشون یه فصل برای Minimax دارند، با توجه به این که این الگوریتم جزئیات و بهینه سازی هایی برای بهبود سرعت و عملکرد داره (مخصوصا Alpha-Beta که گفتم با توجه به حالت های زیادی که در شطرنج وجود داره خیلی مهمه) پیشنهاد میکنم اگر با مطالب هوش مصنوعی آشنایی ندارید یکی از همین کتاب های ترجمه رو بخونید.

[Ner'zhul Arthas]

روشی که قبلا گذاشته بودم همین minimax بود.
ولی در هر بار که نوبتش میشد باید شروع میکرد به فکر کردن و تا زمانش تموم شه یا تا تعداد دفعات پیشبینی حرکات بعدی تموم شه میتونست فکر کنه.

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

فقط هر بار که خودش یا حریفش بازی میکنه محدوده ی تفکرش تغییر میکنه.
ولی از نتایج تفکرات قبلیش در محدوده ی تفکرات جدیدش هست.
که دوباره نیاز نیست اونا رو محاسبه کنه.

[__H2__]

حدودا 20 به توان 7.

سلام
شوخی میکنی؟:بوس: اگه واقعا اینطور باشه، به طرز فجیحی وحشتناک است!!:گیج: :متعجب:
با یک حساب سر انگشتی، اگر برای هر کدام تنها 4 بایت مصرف شود (به اندازه یک اشاره گر، که دیگر کمتر از این نمیشود!!) شما نیاز به 4GByte حافظه دارید! که در حالت واقعی اصلاَ با 4 بایت مشکلتان حل نمیشود و در نتیجه امکان ندارد.:متعجب:

مگر از پیج فایل در هارد استفاده کنید، که آنهم برنامه های عظیم و سنگینی مثل 3DStudioMax هم همچین فایلهای حجیمی نمی سازند!:گیج:

بدون شک الگوریتم اصلیتان مشکل دارد و باید روشتان را اصلاح کنید. چون شاید به حافظه چند ده گیگی نیاز پیدا کنید و کاربر بیچاره باید فقط یک هارددیسک بخره مخصوص برنامه شما و احتمالا موهایش سفید میشه تا برنامه تان کارش تمام شود و جواب نهایی را بدهد. :بوس:

از همان الگوریتم های غیر درختی استفاده کنید! منظورم این است که حالت را ذخیره نکنید! همانطور که دوستمان arsp_2004 (http://www.barnamenevis.org/forum/member.php?u=33355) هم گفت. شما به صورت تودرتو حالات را بررسی کنید و به هرمسیر امتیازی دهید، مثلاَ حرکتی که موجب "مات" میشود بالاترین امتیاز را دارد و حرکتی که باعث "مات" شدن خود رایانه میشود بالاترین امتیاز منفی، سپس شما اولین حرکت مسیری را که بالاترین امتیاز را دارد اجرا کنید و هیچ چیز را برای بعدا ذخیره نکنید!

البته من سورسی برای شطرنج دارم ولی تا حالا وقت نکرده ام بررسی اش کنم و تازه مشکل بزرگی دارد، نه با VB است و نه برای Windows و نه برای ...

[Ner'zhul Arthas]

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

باید میگفتم بستگی به سرعت کامپیوتره داره و زمانی که فکر میکنه. :اشتباه:

راستی 4 گیگ نمیشه، 10 گیگ میشه. :لبخند:

[__H2__]

سلام


4 * (20 ^ 7) = 5120000000
4GB = 4294967296

[Ner'zhul Arthas]

یه متغیر دیگه هم برای Rate بود با اون اگر 4 بایتی فرض کنیم، میشه 10 گیگ.

8 بایت ضرب در 20 به توان 7 میشه: 10240000000

10240000000 بایت = 10000000 کیلو بایت = 9765.625 مگا بایت = 9.5367431640625 گیگا بایت

[Alireza_Salehi]

واقعا جالبه!

جهت اطلاعتون باید بگم بدون توجه به قدرت محاسباتی کامپیوتر ها همیشه الگوریتم ها جهت بدست آوردن راندمان بالاتر در حال پیشرفت و بهینه شدن هستند ، در ضمن چنین رقم بزرگی برای بازی شطرنج حتی در یک سوپر کامپیوتر با قدرت مثلا 80 ترا فلاپ هم مسخرس، چون دلیلی وجود نداره با وجود روش های کم هزینه تر منابع رو به هدر بدیم!

الگوریتم های موجود در هوش مصنوعی به سادگی و با کمترین هزینه (زمان و فضا) بازی شطرنج رو اداره می کنند،در ضمن کاری که با کمی فکر کردن و کد نویسی در چند ثانیه قابل انجامه باشه رو به دلیل الگوریتم غلط موکول به امکانات آینده نمی کنند.

بدون شک همچین رقمی به طرز فجیعی وحشتناکه (البته برای شطرنج)!

[Ner'zhul Arthas]

بازم که شما به کامپیوتر های امروزی کار دارید.
ابر کامپیوتر هم امروزی به حساب میاد.
در آینده هم که حافظه به اندازه ی کافی رشد کنه اصلا نیازی به محاسبه نیست. همه ی حالات با بهترین جوابشون ذخیره شده هست.
مثل حرکاتی که در Deep Fritz 10 هست که بیش از 3 گیگه.


چون دلیلی وجود نداره با وجود روش های کم هزینه تر منابع رو به هدر بدیم!

منابع یا اطاق ها؟
مثل اینه که یه خونه ی خیلی بزرگ دارید بعد برای این که هزینه کم شه تو یه اطاق زندگی کنید.
خوب خونه رو بفروشید یه کوچیکش رو بخرید.

شما اگر از الگوریتمی که گفتم بهتر سراغ دارید بگید.


کاری که با کمی فکر کردن و کد نویسی در چند ثانیه قابل انجامه باشه رو به دلیل الگوریتم غلط موکول به امکانات آینده نمی کنند.

من که به امکانات آینده موکول نمیکنم.
الگوریتمی هم که من میگم نتیجش با نتیجه ی الگوریتمی که شما میگید خیلی فرق میکنه.

اگرم میگید الگوریتمم غلطه بگید کجاش.

[Alireza_Salehi]

این همه بازی شطرنج از سطح مبتدی گرفته تا حرفه ای به کمترین امکانات قابل بازی کردن هستند، حتی اون کامپیوتر هایی که برای شکست دادن بزرگان شطرنج طراحی شده اند هم نسبت به کاری که قراره انجام بدند (شکست نفر اول در جهان) این همه وقت و سخت افزار تلف نمی کنند (دقت کنید نسبت به کاری که انجام میدهند)!

این که چرا این روش غلطه یا چطور میشه اصلاحش کرد خیلی وقت میبره ، اگر یک کتاب هوش مصنوعی بخونید راه های زیادی برای رسیدن به نتیجه بهتر با هزینه کمتر پیدا می کنید!

یک دلیل ساده و واضح برای غلط بودن روش حافظه زیادیه که می خواد ، با توضیحاتی که شما دادید این یک برنامه شطرنجه که فقط یه کم بیشتر از بقیه قراره فکر کنه!

تفاوت الگوریتم هایی که برای چنین مسائلی به کار میره در اینه که تا چه مرحله ای آینده رو پیش بینی می کنندو چقدر به هدف نزدیک میشن و به نسبت این پیش بینی و روش هایی که برای بهینه سازی روش جستجو (بهینه سازی و حذف مسیر های زاید جستجو در روش های هوش مصنوعی نقش کلیدی داره)در فضای آینده وجود داره فضا و امکانات سیستم رو مصرف می کنند، اصلا ربطی هم به قدرت محاسباتی نداره ،

در ضمن اون حالات و جواب هایی که ذخیره شده هستند تنها دلیل وجودیشون اینه که اگر به کار نمیرفتند مراحل جستجو چندین مرتبه حجیم تر و پر هزینه تر می شدند.

به نظر میرسه برنامه شما این همه حافظه رو برای محاسباتش به کار میبره نه برای نگهداری حالات ذخیره شده!

بالاخره یک نسبت معقولی باید بین هزینه پایگاه دانش و سود این پایگاه باشه ، اگر هزینش به سودش نیاد که به درد نمیخوره!

[Ner'zhul Arthas]

این همه بازی شطرنج از سطح مبتدی گرفته تا حرفه ای به کمترین امکانات قابل بازی کردن هستند، حتی اون کامپیوتر هایی که برای شکست دادن بزرگان شطرنج طراحی شده اند هم نسبت به کاری که قراره انجام بدند (شکست نفر اول در جهان) این همه وقت و سخت افزار تلف نمی کنند (دقت کنید نسبت به کاری که انجام میدهند)!

من که واسه ی شکست دادن قهرمانا برنامه نمینویسم؛ واسه دلم مینویسم.
امکاناتی که گفتم اجباری نیست برنامه با خود کامپیوتر پیش میره.
فریتز هم که تنها برنامه ی شطرنجه که تونسته قهرمان بزرگی (کاسپارف) رو شکست بده(به اون هدفی که میگید برسه) بسته به کامپیوتری که داره اجراش میکنه قوی و ضعیف میشه.
فریتز 10 نتونسته فریمنیک رو شکست بده. باهاش مساوی کرده.(به هدفش نرسیده)


این که چرا این روش غلطه یا چطور میشه اصلاحش کرد خیلی وقت میبره ، اگر یک کتاب هوش مصنوعی بخونید راه های زیادی برای رسیدن به نتیجه بهتر با هزینه کمتر پیدا می کنید!

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

منم دارم فکر کردن انسان رو تو برنامه پیاده میکنم ولی شما میگی الگوریتم غلطه.


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


به نظر میرسه برنامه شما این همه حافظه رو برای محاسباتش به کار میبره نه برای نگهداری حالات ذخیره شده!

برای هر دو به کار میبره.


بالاخره یک نسبت معقولی باید بین هزینه پایگاه دانش و سود این پایگاه باشه ، اگر هزینش به سودش نیاد که به درد نمیخوره!
از کجا میدونید سودش به هزینش نمیارزه؟

[Alireza_Salehi]

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

در ضمن اگر نسبت به حافظه موجود کار میکنه خوب اشکالی نداره ، ولی حتما میشه بهینه ترش کرد، شک نکنید!

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

امیدوارم موفق باشید.

[__H2__]

سلام
در تایید حرفهای کاربر arsp_2004 (http://www.barnamenevis.org/forum/member.php?u=33355) باید بگویم،
همانطور که من گفتم سورسی دارم و به درستی شطرنج بازی میکند!
ولی برای ریزپردازنده AVR است که سرعتی در حد چند مگاهرتز دارد و حافظه RAM چند کیلوبایتی و حافظه برنامه چند کیلوبایتی.

واقعاَ جالب است، یک مدار الکترونیکی که باشما شطرنج بازی میکند، میشود آن را ساخت خیلی راحت فروخت یا حداقل در مسافرت و... از آن استفاده کرد. البته من خودم در شبیه ساز با آن کارکرده ام.

[__H2__]

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

البته همین حالا با TaskManager امتحان کردم، بی انصاف 100MB از RAM را گرفته!!
شاید هم دیده حافظه مفته، این کار را کرده! RAM من 1G است، شاید با RAM کمتر حافظه کمتری بگیرد! (برنامه های مصرف بالا معمولا برحسب حافظه خالی در دسترس عمل میکنند)

[Alireza_Salehi]

100M کجا و 8G کجا!

همین شطرنج ویستا با درجه سختی 10 (1-10) فقط از CPU استفاده میکنه و تقریبا موقع فکر کردن همه کاراش رو با همون حدود 100M انجام میده- که البته بیشترش مال گرافیک سه بعدیشه!

یعنی حداکثر کارایی در مصرف حافظه!

[amirsadeghi]

راجع به خود ساختار درختها مقاله ندارید؟