الگوریتم minimax برای بازی دوز

[zt1990]

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

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

[sirvan61]

این مقاله رو بخونید اگه نخوندید : http://www.neverstopbuilding.com/minimax
چیزی که من ازش فهمیدم اینه : هر بار چک کنیم در آینده چه اتفاقاتی ممکن است بیفتد (با تکرار تابع برای حالت های مختلفی که برای هر انتخاب پیش روی ماست و به همین ترتیب تا به برد یکی از دوطرف یا هیچکدام برسیم)
در واقع از الگوریتم بازگشتی که درخت بازی رو بررسی میکنه استفاده می کنیم. امتیازدهی به این صورته که اگر در یک مرحله، کامپیوتر برد، امتیاز زیاد مثبت ( مثلا 10 امتیاز) و اگر حریف برد، امتیاز زیاد منفی ( مثلا -10 امتیاز ) بازگردانده میشه. ولی از اونجایی که بین برد کامپیوتر در مرحله ی بعد یا در دو مرحله بعد، تفاوت هست، شماره ی مرحله رو از اندازه ی امتیاز نهایی (10) کم میکنیم تا بدین ترتیب، امتیاز بردی که در مرحله های پایین تر به دست میاد کمتر از امتیاز بردی که زودتر نصیب میشه باشه و وقتی ماکسیمم یا مینیمم میگیریم، اونی که زودتر هست انتخاب بشه
برای ما مهمه که زودتر ببریم یا دیرتر ببازیم، برای همین، وقتی نوبت کامپیوتره، ماکسیمم امتیاز رو حساب میکنیم و وقتی نوبت کاربره، مینیمم امتیاز
چون بیشترین سود و کمترین ضرر رو میخوایم...
کدی که من برای هوشمند کردن دوز خودم نوشتم :


float backtrack(dooz d, int level,float max_point,float min_point)
{
// empty_count : tedade khane haye khali ke ghablan be dast amade
// vacant : araye i ke mokhtasate khane haye khali e safhe ra darad .
char turn = (level%2 )?'x':'o';
int win = d.win();
if(win != 0 || !d.empty_count){
if(turn=='x')
return win*10-level;
else return win*10+level;
}
// promising check
if(max_point>0)
return 0;
if(min_point<100)
return 0;
if( level == 4)
return 0;

// end of promising check
float s ;
for(int i=0;i<d.empty_count;i++){

d.ar[d.vacant[i]->x][d.vacant[i]->y] = turn;
d.empty_count--;

s = backtrack(d,level+1,max_point,min_point);

d.ar[d.vacant[i]->x][d.vacant[i]->y] = NULL;
d.empty_count++;

if(turn=='x'){
if(s<min_point)
min_point = s;
}

else
if(s>max_point){
max_point = s;
choice = * d.vacant[i];
}

}
if(turn=='x')
return min_point;
return max_point;
}




کاراکتری که برای کامپیوتر هست، o و برای حریف ( کاربر عادی) x

درمورد promising check این کد بگم که برای هرس کردن درخت بازی و جلوگیری از طولانی شدن زمان تصمیم گیری کامپیوتر، حالاتی که مطمئنیم جواب در آن ها نیست و انتخاب نخواهند شد را به این صورت هرس میکنم که اگه مثلا در یک حالت فرزند، امتیاز مثبتی از برد به دست آمده، در فرزند بعدی، اگر در یک مرحله بعد به برد نرسیم حتما ادامه ی این شاخه، بی فایده است ؛ چرا ک حتی اگر در یک مرحله بعد از این مرحله به برد برسیم، امتیاز آن کمتر از امتیاز برد در مرحله ی بالاتر است و مسلما انتخاب نخواهد شد.
به همین ترتیب برای مینیمم انتخاب کردن ؛ اگر در یک مرحله، ببازیم، دیگر اهمیت ندارد که در مرحله ی بعد ببریم یا ببازیم، چون امتیاز آن کمتر است و مسلما اگر چنین حالتی پیش آید، کاربر می برد. پس اگر امتیاز فرزند بعدی در یک مرحله پیمایش، از نظر اندازه ( قدرمطلق) از بیشترین امتیازی که تاکنون برای حریف به دست آمده ( یعنی کمترین امتیاز برای ما - min_point ) بیشتر نبود، expand کردن آن بی فایده است. ( در واقعیت یعنی اگر در همان مرحله نبازیم و امتیاز منفی نگیریم، 0 برگردانده شود)