Модератор: Модераторы разделов
/dev/random писал(а): ↑05.05.2010 18:02
Вручную проверять все "хорошие" и "нехорошие" положения. К примеру, в первом случае будет не "i<=6", а "i == 0 || i == 3 || i == 6".
Да, это превратится в головную боль при использовании большого поля. Но ничего не поделаешь, вы сами выбрали работу с одномерным массивом.
Код: Выделить всё
for((*tempx)=0; (*tempx)!=2; (*tempx)++)
for((*tempy)=0; (*tempy)!=2; (*tempy)++)
{
if(sk[*tempx][*tempy]=='X'&&sk[*tempx][*tempy+1]=='X'&&sk[*tempx][*tempy+2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;}
if(sk[*tempx][*tempy]=='X'&&sk[*tempx+1][*tempy]=='X'&&sk[*tempx+2][*tempy]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;}
if(sk[*tempx][*tempy]=='X'&&sk[*tempx+1][*tempy+1]=='X'&&sk[*tempx+2][*tempy+2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;}
if(sk[*tempx][*tempy]=='X'&&sk[*tempx-1][*tempy-1]=='X'&&sk[*tempx-2][*tempy-2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;}
}
BratSinot писал(а): ↑05.05.2010 21:36Вообщем переписал прогу на двумерный массив. Сделал вещь типа:
Код: Выделить всё
for((*tempx)=0; (*tempx)!=2; (*tempx)++) for((*tempy)=0; (*tempy)!=2; (*tempy)++) { if(sk[*tempx][*tempy]=='X'&&sk[*tempx][*tempy+1]=='X'&&sk[*tempx][*tempy+2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;} if(sk[*tempx][*tempy]=='X'&&sk[*tempx+1][*tempy]=='X'&&sk[*tempx+2][*tempy]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;} if(sk[*tempx][*tempy]=='X'&&sk[*tempx+1][*tempy+1]=='X'&&sk[*tempx+2][*tempy+2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;} if(sk[*tempx][*tempy]=='X'&&sk[*tempx-1][*tempy-1]=='X'&&sk[*tempx-2][*tempy-2]=='X') {printf("X WIN\n"); fprintf(fp, "X WIN\n"); esh=0;} }
Замечания будут? Или все нормально?
Не будет она интереснее. И думать он долго не будет. Для рядов больше пяти существует беспроигрышная стратегия для обоих игроков. Т.е. игра между двумя компьютеными игроками всегда будет заканчиваться вничью. Именно поэтому существует только игра "пять в ряд", но нет игр "шесть в ряд" и т.д.: не потому что "еще нет математического метода решения", а потому что он давно есть.eddy писал(а): ↑05.05.2010 17:01Вот именно, что 3х3 неинтересно. А вот если взять поле, скажем, 10^6x10^6, да рассматривать выигрышными только линии, длиннее, скажем, 10^4 крестиков или ноликов, то задача будет намного интереснее. И простым тупым перебором компьютер будет думать ооочень долго (не при определении, выиграл ли противник, а при выборе, куда поставить свой значок).
Вот мне и интересно: неужели еще нет математического метода решения подобных задач?
Если Вы хотите преодоьлевать искусственные сложности, то преодолевайте их своими силами. Если Вы хотите посторонней помощи, то не отказывайтесь так настойчиво от советов использовать простые решения.
Программа, которая будет работать медленно, прожорливо и не всегда, будет проще и короче, чем полная реализация точной выигрышной стратегии? О чём тут спорить? (: Уберите хотя бы "не всегда" -- будет хоть какой-то предмет для разговора.
/dev/random писал(а): ↑05.05.2010 22:27Нет, не нормально. Вы опять не проверяете выход за пределы.
В первом случае в начало нужно добавить условие tempx<=N-M (N=3 - размер поля, M=3 - знаков в ряд), во втором tempy<=N-M, в третьем оба, в четвёртом... А в четвёртом у вас вообще ошибка.
Есть категория задач, где реализация существующего алгоритма по определению проще, чем метод перебора. Крестики-нолики как раз из таких задач. А алгоритмические проблемы топикстартера проистекают исключительно из им же придуманной искусственной сложности: использования одномерного массива для двумерной задачи. А Ваше допущение "будет работать не всегда" для задачи, которая решается для любого случая даже на забытых ныне программируемых калькуляторах, выглядит немного смешно. Равно как и сравнение с qsort.drBatty писал(а): ↑06.05.2010 12:08не уберу. все уже много лет успешно используют ГА. они проще. а часто - решение находится намного быстрее, и оно иногда более оптимальное, чем выбранное "чистым математическим подходом". Особенно это проявляется в таких задачах -
"чисто-математический" подход является источником сложно-выявляемых ошибок, как у нашего ТС. А если решить задачу более простым способом - ошибок было-бы меньше. В данном конкретном случае объём памяти и быстродействие не играет никакой роли, а вот алгоритмические ошибки - играют...
И ещё почему не уберу: все уже много лет используют qsort, не смотря на то, что она иногда жутко тупит, тормозит, и переполняет стек (что ведёт к сбоям, зависаниям, и даже к уязвимостям). многие просто об этом не знают (:
А в большинстве практических случаев - это просто, надёжно, и быстро.
Не совсем так. Впрочем, подробное объяснение этого алгоритма мне кажется уже избыточным для этой темы.
С точки зрения научной терминологии это всё равно стратегия; даже если её разработка базировалась на переборе всех возможных исходов (как в случае 3x3; но стратегия существует и для "пять в ряд"). Но суть не в этом. Одно из неотъемлемых свойств стратегии (по определению, именно как научного термина) -- полнота, т.е. принципиальное отсутствие неразрешимых позиций. Если такие позиции возможны, это не стратегия. Поэтому в сложных играх (например, в шахматах или го) стратегии не существует. И соответственно, если Вы уже заговорили о вероятнростном методе с памятью предыдущих исходов, то по сравнению с ним реализация почти любой игровой стратегии будет проще; уж для "пять в ряд" -- точно.drBatty писал(а): ↑06.05.2010 12:36В данной задаче вовсе нет никакой стратегии, у вас просто заранее заготовленные ходы, которые дают верное решение. В данном случае вариантов мало, и этот подход даёт результаты. В других случаях нужна именно стратегия, куда и как делать ходы (в зависимости от ситуации, которая может быть и неизвестной при написании программы). Метод случайного выбора с историей (вероятность выбора зависит от прошлых исходов) даёт результат даже в неизвестных ситуациях - мой алгоритм всегда сделает какой-то ход, пусть даже и не оптимальный. Ваш алгоритм не сможет справится с неизвестной задачей - он "чисто-математический".
/dev/random писал(а): ↑05.05.2010 22:27Нет, не нормально. Вы опять не проверяете выход за пределы.
В первом случае в начало нужно добавить условие tempx<=N-M (N=3 - размер поля, M=3 - знаков в ряд), во втором tempy<=N-M, в третьем оба, в четвёртом... А в четвёртом у вас вообще ошибка.
Не по-моему, а по определению. Я уже написал, что использую это слово как чёткий научный термин. Также написал, что в определении этого термина присутствует требование полноты. Т.е. "беспроигрышной стратегией" можно назвать набор правил, который _всегда_ приводит к выигрышу либо ничьей, при _любых_ ходах противника. Если есть вероятностный элемент, это не стратегия по определению.drBatty писал(а): ↑06.05.2010 15:33это почему это?! не существует оптимальной стратегии, тут согласен. Но можно с лёгкостью создать допустимую, хотя и не оптимальную - достаточно взять любую, и в случае неразрешимой позиции выбирать случайный ход. Тогда неразрешимых не будет. Или "сделать случайный но допустимый ход" по Вашему - не стратегия? (:
Конечно, "грязное" решение тоже возможно. С этим я и не спорил. Но эта задача -- не тот случай, когда использование такого решения хоть чем-то оправдано.drBatty писал(а): ↑06.05.2010 15:33угу. потому-что вариантов много, и приходится сильно усложнять алгоритм. только в обычных КН можно сделать "в лоб"... Это верно. Я просто хотел сказать, что всегда возможно не только "чистое" решение, и иногда оно даже работает (:
и qsort я тоже потому упомянул - это "грязное" решение, оно тоже работает не всегда. но тем не мение, его используют почти все и почти всегда.
Да не 8, а 2; что же Вы о симметрии всё время забываете? Уж для ГА-то набор элементов всегда пытаются свести к минимуму для повышения эффективности обучения.
Что сделать? Попытаться прочитать невыделенную память? С чего Вы взяли, что этоь возможхно только в DOS?BratSinot писал(а): ↑06.05.2010 15:52/*для ТС: чтение из массива с выходом за границу может привести (по стандарту) к чему угодно. например к форматированию всех жёстких дисков (: Это язык такой... Что Си, что Си с плюсами... Нужно либо менять язык, либо проверять, либо создать такой алгоритм, который заведомо не выйдет за границу...*/
Вы часто видели операционные системы где это легко сделать? Я кроме dos'а не видел.
/dev/random писал(а): ↑06.05.2010 17:16В данном случае - да. Но вы хотели задел на будущее, чтобы можно было работать с большими полями. К примеру, если на поле 10x10 нужно поставить 5 в ряд, то N-M=5.
Кстати, вы нашли ошибку в четвёртом условии?
Код: Выделить всё
if(sk[*tempx][*tempy]=='X'&&sk[*tempx+1][*tempy-1]=='X'&&sk[*tempx+2][*tempy-2]=='X')t.t писал(а): ↑06.05.2010 16:23Не по-моему, а по определению. Я уже написал, что использую это слово как чёткий научный термин. Также написал, что в определении этого термина присутствует требование полноты. Т.е. "беспроигрышной стратегией" можно назвать набор правил, который _всегда_ приводит к выигрышу либо ничьей, при _любых_ ходах противника. Если есть вероятностный элемент, это не стратегия по определению.
В теории игр стратегия игрока в игре или деловой ситуации — это полный план действий при всевозможных ситуациях, способных возникнуть. Стратегия определяет действие игрока в любой момент игры и для каждого возможного течения игры, способного привести к каждой ситуации.
То, что Вы привели, -- не определение термина, а попытка объяснить его научно-популярным языком. Точного определения термина "стратегия" я в сети не нашёл (иначе бы привёл ссылку), а наизусть я его помню плохо: всё-же теорию игр нам вообще не преподавали. Требование полноты в этом определении я упоминал уже дважды. Впрочем, в приведенном объяснении это требование тоже присутствуепт, хотя и не столь точно сформулировано (выделение моё):drBatty писал(а): ↑06.05.2010 19:18http://ru.wikipedia.org/wiki/Стратегия_(математика)t.t писал(а): ↑06.05.2010 16:23Не по-моему, а по определению. Я уже написал, что использую это слово как чёткий научный термин. Также написал, что в определении этого термина присутствует требование полноты. Т.е. "беспроигрышной стратегией" можно назвать набор правил, который _всегда_ приводит к выигрышу либо ничьей, при _любых_ ходах противника. Если есть вероятностный элемент, это не стратегия по определению.я не говорил, что моя стратегия оптимальная, и что она (тем более) - беспроигрышная. Да она не оптимальная, и в некоторых случаях не приводит к выигрышу, даже если это и возможно. Это не лучшая стратегия, и тем не менее, это стратегия. ИМХО. Да, есть элемент случайности, ну и что? Случайное действие разве не действие?В теории игр стратегия игрока в игре или деловой ситуации — это полный план действий при всевозможных ситуациях, способных возникнуть. Стратегия определяет действие игрока в любой момент игры и для каждого возможного течения игры, способного привести к каждой ситуации.
В теории игр стратегия игрока в игре или деловой ситуации — это полный план действий при всевозможных ситуациях, способных возникнуть. Стратегия определяет действие игрока в любой момент игры и для каждого возможного течения игры, способного привести к каждой ситуации.
Это не стратегия. Стратегия даёт _гарантированный_ результат. По определению. Если в алгоритме есть вероятнростный элемент, то этот алгоритм -- не стратегия. Если игра по своим правилам основана на вероятностях событий, то для такой игры стратегии не существует по определению. Могут существовать алгоритмы, максимизирующие матожидание выигрыша -- но это не стратегии.
Если существет несколько ходов, признанных "одинаковыми" (точного термина не помню) с точки зрения ГА, то один из них обычно выбирается случайно и равновероятно. Подчеркну, что этот случайный выбор не является элементом стратегии: ведь с точки зрения стратегии все эти равновепроятные ходы _одинаковы_.drBatty писал(а): ↑06.05.2010 19:18нет, не забываю. в данном случае это не играет никакой роли - просто программа получается даже не простой, а совсем примитивной. Это если без симметрии. К тому-же, так играть намного интереснее - ваш вариант будет навязывать только 1 вариант. И так КН тупая игра, а с вашей оптимизацией... (: