vidoff30 мая 2014 в 08:31

Алгоритм минимакс на примере игры «Собери 4 (connect4)»

4 мин

14K

Алгоритмы *

Комментарии 22

dimakovalenko 30 мая 2014 в 08:37

Спрячьте пожалуйста статью под кат. Спасибо за внимание.

vidoff 30 мая 2014 в 08:39

Почему? И что такое кат?

andymitrich 30 мая 2014 в 08:40

Прочитали бы всё-таки правила публикации — не задавали бы таких вопросов.

dimakovalenko 30 мая 2014 в 08:44

Большие посты обчно помещаются под habracut (есть такой специальный тег, который вы можете использовать в своей статье что бы спрятать бОльшую часть статьи под кнопкой «Читать дальше»). В результате в списке постов будет видно только начало вашего поста, а кто заинтересуется — тот нажмет кнопку «Читать дальше» и прочитает весь пост.

vidoff 30 мая 2014 в 08:42

А что неверно — поправьте, буду умнее в следующий раз (на ум приходят только пару :)

dimakovalenko 30 мая 2014 в 08:46

А еще есть такая кнопка «Ответить» под каждым комментарием — пожалуйста пользуйтесь ею что бы ответить кому-то конкретно. Читать комментарии «в один столбик» — глаза вылазят.

vidoff 30 мая 2014 в 08:50

Поставил тег после примерно 300-50 символов, нормально сейчас?

andymitrich 30 мая 2014 в 08:51

Норм.

vidoff 30 мая 2014 в 08:52

Спасибо за совет

dimakovalenko 30 мая 2014 в 08:52

Вроде бы да, так лучше, спасибо.

vidoff 30 мая 2014 в 08:52

Спасибо за совет

Biga 30 мая 2014 в 09:50

Ок, продолжаем ликбез.

Для простого «спасибо» достаточно плюсануть комментарий, нажав на «стрелочку вверх» в его правой части.
Если вам такой способ кажется недостаточно выразительным, можно изложить всю свою признательность хабраюзеру, отправив ему личное сообщение.
Суть в том, что комментарии типа «спасибо» не несут полезного содержания для остальных читателей Хабра.

Чтобы отправить личное сообщение хабраюзеру, нужно открыть страницу профиля адресата (нажав на его имя или юзерпик, которые являются ссылками), и найти на этой странице иконку с конвертом (располагается справа от чисел рейтинга).

vidoff 30 мая 2014 в 09:57

:) — выложил материал чисто чтобы кому-то было полезно, а всякуя по-ь выслушивать, ну блин вообще неинтересно

andymitrich 30 мая 2014 в 10:02

Простите, конечно, но это называется неуважением. Вам не пое-ь говорят, а излагают правила сайта, которые вы, очевидно, не удосужились прочитать. Будете и дальше вести себя столь вызывающе, ваш пост заминусуют и больше вы на Хабр ничего не напишете.

vidoff 30 мая 2014 в 10:05

спасибо на самом деле за советы, но блин — написал я спасибо вам и еще… реально благодарен… а тут еще минусуют за то что поблагодарил — во до чего докатились:)

dimakovalenko 30 мая 2014 в 10:08

Просто на хабре свои правила — они изложены в письменном виде, доступны всем и касаются оформления статей, комментирования, стиля изложения, даже грамотности :) Соблюдение этих правил, вместе с системой кармы и плюсов за посты, некоторым образом гарантирует что хабр не скатится в хаос «каждый постит хрень и вообще творит что хочет», как многие другие сайты в рунете у которых вроде бы все начиналось хорошо. Если вы пишете сюда — просто соблюдайте их, как и все остальные, только и всего :)

vidoff 30 мая 2014 в 10:11

ОК. Я стараюсь соблюдать — с катом вот промашка вышла, исправил сразу же. И не грубил никому и все такое — говорил спасибо.

HomoLuden 3 июн 2014 в 09:08

По сути комментарии будут?
Суть Минимакса не раскрыта, на мой взгляд.

«Максимум выгоды при минимуме удачи», «Минимум ущерба при максимально худшем стечении обстоятельств».

Про оптимизацию весов / функции оценки сумбурно.

По оформлению… Не ставьте знаки препинания сразу после тэгов кода и переносите последующий текст на следующую строку явно. То, что представлено в статье сейчас, выглядит как сломавшаяся разметка.

Код не анализировал… за качество оного не скажу ничего.

vidoff 3 июн 2014 в 10:06

Это результаты без теории можно сказать — плод моих собственных измышлений в минимакс. Но, определенный положительный результат есть! Если у вас есть соображения по поводу увеличения силы игры программы напишите пожалуйста, испробую, изложу результаты.

HomoLuden 4 июн 2014 в 12:06

Я исследую вот прям также методом научного тыка генетические алгоритмы, что не есть хорошо. Без теоретической базы трудно нормальные тесты написать.

В Вашем случае без нормальной теоретической базы даже выбор весов становится чисто случайным (тот же полунаучный тык). Повезет Вам — совпадут веса с конкретным случаем. Вы распространите такие же веса на другие кейсы, а там они не будут работать как надо. И Вы об этом можете и не узнать. Выбор параметров модели очень важен в таких задачах. Скажем, почему ходам соперника больше вес дается, а своему — меньше, и почему сопернику именно столько-то. Все это нужно обосновать, чтобы иметь возможность ошибки детектить (тесты писать).

Кстати, МиниМакс как раз хорошо вписавыется в задачу оптимизации на ГА. Как говорится, «веселее вместе».

vidoff 8 июн 2014 в 20:06

Добился абсолютной победы над программой! Благодаря, в том числе, вашим замечаниям: повышение значимости ответа соперника (понял примерно так), т.е. на практике достигается путем умножения результата соперника на константу более единицы, я выбрал (от фонаря) = 10 и алгоритм обыграл программу при ходе первым и при ходе вторым. Теперь функция минимакс выглядит вот так:

Step game(TicTac *field, int deep, WHO it, TicTac t){
	int i=0;
	float rait, koeff = 1 - Koeff[it]*deep;
	Step s, r;
	s.step = -1;
	s.rait = -1000.;
	if(deep > DEEPMAX){
		s.rait = 0.;
		return s;
	}
	for(i=0; i<NSIZE_I*NSIZE_J; i++){
		if( validstep(field, i) ){
			field[i] = t;
			rait = c4getrait(field, t);			
			if(rait >= WIN){
				field[i] = EMPTY;
				s.rait = 100.*koeff;
				s.step = i;
				return s;
			} else if(!isstep(field)){
				rait = 0.;				
 			} else {
				r = game(field, deep+1, it, (t==Tic)?Tac:Tic);
				rait-=(CorrectK[it]*r.rait);
			}
			if(rait > s.rait){
				s.rait = rait;
				s.step = i;
			}
			field[i] = EMPTY;
		}
	}
	s.rait = s.rait*koeff;
	return s;
}

Задачу можно считать решенной и переходить к более сложной игре)))

HomoLuden 13 июн 2014 в 11:58

А таперича прогоните через профайлер, найдите нагруженные места и попробуйте улучшить производительность :)

Зарегистрируйтесь на Хабре, чтобы оставить комментарий