Нужна помощь с программой
Всем привет. Нарисовалась проблема- девушке на 1 курсе института задали написать на Паскале игру крестики-нолики в поле 20*20, чтобы компьютер начинал и не проигрывал. Пока никаким премудростям не учили, преподаватель дал детям очень мало знаний. Как мы прочитали на форумах - задача достаточно сложная. Может, у кого остались наработки в этом направлении, и не жалко поделиться- были б безмерно благодарны.
Задача на умение шевелить мозгами. Собственно, цель такого задания именно в том, чтобы студент подумал своей головой. Ничего сверхсложного в задаче нет, никакие специальные знания не требуются. Зато умение решать подобные задачи очень пригодится при дальнейшем обучении.
В интернете наверняка есть готовые решения, только зачем тогда учиться?
Могу подсказку дать: от размера поля ничего не зависит. Можно начать с 2х2, перейти к 3х3, потом к 4х4 (на бумажке, без всяких Паскалей), и к этому моменту станет понятно, как должен играть первый игрок. Останется только формализовать алгоритм.
Самое смешное, что не так все просто. В инете готовых решений нет. Только примерные алгоритмы. Но в них используются моменты, еще не известные студентам (рекурсии, ИИ). И не для паскаля. Теоретически, примерно понятно, что делать, но задача не только чтобы комп не проиграл, но, желательно- выиграл:) А тут уже и вычисление вероятности выигрыша в зависимости от хода. Короче говоря, нам сильно навернутого не надо (читала, что проводятся даже соревнования программеров- чья программа не проиграет:)). То, что смогли написать- комп иногда проигрывает. Время поджимает. Просто может кто-то уже подобное реализовывал именно на паскале и имеет возможность помочь девушке? Первоначально задача была вообще 100*100, но, как я понимаю, тут уже особой разницы нет 20*20 или н*н.
Самое смешное, что не так все просто. В инете готовых решений нет.
+++ Быть такого не может. Крестики-нолики - базовый пример, с которого начинается теория игр.
Только примерные алгоритмы.
+++ Вообще-то, это и есть ответ.
Но в них используются моменты, еще не известные студентам (рекурсии, ИИ).
+++ Без рекурсии вполне можно обойтись, а от искусственного интеллекта избавиться не получится, поскольку заставить компьютер играть с человеком - автоматически означает пусть простенькую, но все-таки ИИ-задачку.
И не для паскаля.
+++ А это вообще пофиг. Только вопрос знания синтаксиса конкретного языка. Описать алгоритм можно на любом языке.
Теоретически, примерно понятно, что делать, но задача не только чтобы комп не проиграл, но, желательно- выиграл:)
+++ Надо сесть и поиграть. Точнее, сначала надо формализовать, что есть победа, три крестика подряд или надо ряд/вертикаль/диагональ из конца в конец заполнить. А может еще что-то. В первом случае начинающий при правильной игре выигрывает первыми же тремя ходами.
+++ Поиграмши, формализовать алгоритм в любом виде, хоть на русском языке, проверить работоспособность (все так же, на бумажке). В случае успеха уже формально описать алгоритм и релизовать его на языке программирования. Можно и по-другому как-нибудь подходить, суть от этого не меняется.
А тут уже и вычисление вероятности выигрыша в зависимости от хода.
+++ Не увидел задачи вычисления каких бы то ни было вероятностей.
Просто может кто-то уже подобное реализовывал именно на паскале и имеет возможность помочь девушке?
+++ Повторюсь. Лучше решить задачу не до конца, но самостоятельно, чем тупо сдуть готовое решение. Задача НЕ сложная, но подумать - надо.
Первоначально задача была вообще 100*100, но, как я понимаю, тут уже особой разницы нет 20*20 или н*н.
+++ Принципиально - никакой. И таки определитесь, что надо, не проиграть или выиграть. Если первое и критерием выигрыша является заполненная вертикаль/горизонталь/диагональ (подозреваю, что именно так оно и есть, судя по первому курсу), задачу может решить пятиклассник. Она не простая, а очень простая. Искать решение такой задачи в интернете - позор, извините.
Вы прям как мой муж- если есть алгоритм, то уже все просто:) но дети этого не учили, в принципе, только начали и знают только основы. В инете алгоритмы, которые не только не проигрывают, но стремятся выиграть- с вероятностями. И, как я уже сказала, лучшие алгоритмы соревнуются в среде программистов, поэтому и готовых решений нет:) Так что, думаю, не так все просто как кажется. Девочка сама что смогла написала, но комп проигрывает иногда. Я уже писала, как я понимаю алгоритм- нужно отследить не только ближайшую к х ячейку, но и через ячейку. Это как понимаю я, программированием занимавшаяся более 10 лет назад и только по программе курса:)
Вы прям как мой муж- если есть алгоритм, то уже все просто:)
+++ Так и есть. Задача программист - изобрести алгоритм и излоить его на языке программирования. Первое в реальной жизни гораздо сложнее, второе при начичии первого- довольно тупая механическая работа.
но дети этого не учили,
+++ Чего "этого"? Вы так и не написали, что считается выигрышем. У меня мощнейшее подозрение, что заполненная целиком горизонталь (вертикаль, диагональ). Если так, учить ничего не надо, никакие знания не нужны, требуется только немного подумать - задачка для школьника, а не для студента, если говорить о непроигрыше. Выигрышная стратегия несколько сложнее, но и для ее реализации не надо быть академиком.
В инете алгоритмы, которые не только не проигрывают, но стремятся выиграть- с вероятностями.
+++ Нет тут никаких вероятностей. Например, если первый игрок при правильной стратегии выигрывает, он просто выиграет, и все, второй может пыжиться как угодно. Или, например, если второй игрок при правильной стратегии получает минимум ничью, первый не выиграет никогда. Вместо того, чтобы находить гораздо более сложные задачи в интернете, совершенно не понимая, о чем они, лучше помогите ребенку подумать собственной головой, пользы от этого для ребенка же будет гораздо больше. Тем более, ребенок не такой уже и ребенок.
И, как я уже сказала, лучшие алгоритмы соревнуются в среде программистов, поэтому и готовых решений нет:)
+++ Застрелиться. Лучшие алгоритмы крестиков-ноликов объявлены секретными. Вообще-то, оно давно обсосано со всех сторон в куче учебников. На каком-нибудь Прологе программа будет состоять из одной строчки, причем эта программа будет реализовывать правильную (наилучшую из возможных) стратегию, только продолжаю сильно подозревать, что все это не имеет ни малейшего отношения к задаче Вашего ребенка.
Так что, думаю, не так все просто как кажется. Девочка сама что смогла написала, но комп проигрывает иногда. Я уже писала, как я понимаю алгоритм- нужно отследить не только ближайшую к х ячейку, но и через ячейку. Это как понимаю я, программированием занимавшаяся более 10 лет назад и только по программе курса:)
+++ Необязательно быть программистом, чтобы писать алгоритмы.
1. Взять кастрюлю.
2. Если не получилось, купить кастрюлю и вернуться к п. 1.
3. Налить в кастрюлю воды.
4. Если не получилось, сходить по воду и вернуться к п. 3.
5. Затопить печь.
6. Если не получилось, наколоть и принести дров, затем вернуться к п. 5.
7. Поставить кастрюлю на печь.
8. Ждать, пока вода закипит.
9. Высыпать в кастрюлю пельмени.
10. Если не получилось, вырастить корову, замочить ее с сортире, вырастить пшеницу, изготовить фарш из первого и тесто из второго, вложить первое во второе. Вернуться к п. 1.
11. Ждать, когда пельмени всплывут, но не более 10 минут.
12. Снять кастрюлю с печи.
13. Выловить пельмени.
14. Перерыв на обед.
Это алгоритм. Написанное Вами о том, что нужно отслеживать какие-то ячейки - не алгоритм.
Хотите помочь ребенку - заставьте его думать.
Я Вашу задачу, как ее понял, несмотря на занятость, уже решил несколькими разными способами, несмотря на то, что меня никто не учил решать такие задачки.
Хотите помощи - не проблема, но для этого сначала все-таки четко сформулируйте задачу, а также предъявите мысли ребенка на эту тему. Только не думайте, что выдам исходник на Паскале, который будет делать все, как надо. Только направление, куда копать или указание на заблуждения, ставшие причиной ошибки в текущей реализации.
Помочь решить задачу - готов в меру сил и времени, решать ее за Вас, простите, не буду. Точнее, за Вашу девочку, ибо сие занятие видится мне абсолютно бессмысленным, пользы от него не будет ни Вам, ни мне, ни, что главное, ей самой.
Девочка вообще не очень-то и программист, но вот задали такую задачу. Как могла- решила:) Но не так, как требуется. Вот и вся проблема:) критерий- 5 рядом, я уже написала ниже. Мы уже по этой проблеме прошерстили и хабрахабр и форумы программеров, где исходниками обмениваются. Подходящих для реализации решений не нашли.
вот что на форумах пишут:
"надо разделить математическую и программискую части
в общем по матчасти - есть альфа-бета отсечения (см. в поисковиках) на графе позиций,
PS Как-то писал как хобби программу, играющую в рэндзю.
В Центральном Шахматном клубе (Москва, Гоголевкий бульвар) есть секция рэндзю, а неё есть подсекция (может быть сейчас отделение или как-то ешё называет) по программам, играющим в рэндзю. Можешь прийти, но какими-то чемпионскими алгоритмами едва ли кто поделиться (ибо ..., да и игра между программами за денежные призы)."
а по этой ссылке ищут то же, что и мы, там вообще жесть- http://forum.sources.ru/index.php?s=b9fc39d44317c82c6c4929050fa646b6&showtopic=9651
А реализация на с++ потянула на магистрскую работу:)
Пять в ряд - это почти рэндзю. Без дополнительных ограничений (которые в рэндзю есть) существует алгоритм для начинающего игрока, пользуясь которым, он гарантированно выигрывает. Это известный факт, сам алгоритм тоже секретным не является, но я распечатаю и съем это сообщение, если окажется, что первокурснику, для которого программирование не является профильной дисциплиной, дали задание этот алгоритм заново разработать. Наверняка все гораздо проще.
В общем, давайте полный текст задания.
Начинает человек, выигрывает комп или ничья. Поле 20*20, выиграет 5 рядом. Вот и все условие. По словам девочки.
В такой формулировке задача не имеет решения, поскольку, как я уже говорил, без дополнительных оговорок начинающий игрок при правильной игре выигрывает независимо от того, как играет второй.
Продолжаю пребывать в уверенности, что задачу такого уровня первокурсникам дать не могли. Что-то тут не так. Выясняйте точную формулировку задачи.
я, чессговоря, сама в шоке, особенно почитав форумы програмеров. но вроде это все условие.
а если, допустим, Вы бы посмотрели, что детка наваяла, смогли бы что-то подсказать, в чем ошибка алгоритма? Или это совсем наглость?
При такой постановке задача решения не имеет. Представьте себе то же самое на поле 2х2. Первый игрок выигрывает всегда, и это очевидно. В Вашей постановке задачи то же самое, только оно неочевидно, но доказуемо, и это давно доказано.
Бессмысленно пытаться решить задачу, которая заведомо не имеет решения, понимаете? Столь же бессмысленно рассматривать опытки решения нерешаемой задачи.
Вывод напрашивается сам собой - Ваш ребенок не сообщил о каких-то существенных условиях задачи. Пока не будет ПОЛНОГО набора условий, пытаться что-то делать не имеет смысла - задачи нет.
На всякий случай повторю еще раз. Задачу в приведенной Вами постановке не сможе решить ни первокурсник, ни академик, ни инопланетянин из цивилизации, опередившей в развитии нашу на сто тыщ мильонов лет, потому что решения не существует.
Просмотрела я программу, которую сотворила ребенок и ее товарищ-программист-первокурсник. Это случайный ход компа, похоже:(:(
Блин. Постарайтесь осознать, что решение можно не смотреть, оно не работает, потому что решить ЭТУ задачу НЕВОЗМОЖНО. Понимаете? Похоже, нет.
Попробуйте решить аналогичную задачу для поля 2х2. Там можно все возможные комбинации ходов перебрать. Быстро убедитесь, что какие бы ходы второй игрок не совершал, первый все равно победит. Если все равно неочевидно, возьмите поле 1х1;-)
Не надо смотреть решения, это бессмысленная потеря времени. Надо искать полное условие задачи.
Нет,я понимаю. Но ведь главное- чтобы комп хотел выиграть. Я бы написала что-то типа ... 1. Если в поле (ij)= х проверка поля (i+1,j) с вариантами действий в зависимости от содержимого. потом проверка (i,j+1) и так же по диагонали. Потом проверка (i+2,j) и т.д. т.е. на каждый вариант содержимого- несколько вариантов развития событий.
Нет,я понимаю. Но ведь главное- чтобы комп хотел выиграть.
+++ :-)))) Он ничего не хочет. Он железный.
Я бы написала что-то типа
+++ Зачем? Задача решения не имеет. По какому критерию оценивать решение, по степени выпученности глаз студента или размеру шишки на голове, порожденной битием об стену? А если преподаватель специально дал такую задачу (в чем я продолжаю сомневаться)? И все принесут неработающие решения (потому что других быть не может), а один скажет, что это невозиожно, как думаете, кого преподаватель зауважает?;-)
Сейчас попытаюсь вытрясти что-то другое. Но если нет- то что отвечать преподу??? И народ на форумах же что-то там пишет про оценки каждого хода, вероятность выигрыша при том или ином ходе. Там примерно те же условия все упоминают. Но очень сложные решения, не для первого курса.
Трясти надо не препода, а ребенка, который невнимательно записывает задания. Если же вдруг окажется, что условия именно таковы, в чем я сильно сомневаюсь, преподавателю можно и нужно так и сказать, что решения не сущестует, это ДОКАЗАНО математически в позапрошлом веке и сослаться на книжку "Го. Рэндзю.", написанную товарищами с фамилиями Гик, Носовский и Попов и изданную еще в СССР.
Девочка очень ответственная, вот что пишет по поводу постановки задачи: "Так нам, действительно, он именно так и сформулировал задачу. Все мои одногруппники плюнули и начали делать 3*3, а не 20*20, но даже в этом случае у них есть 2 или 3 способа, которым человек все-таки выигрывает, но они надеются, что преподаватель этими способами ходить не будет."
Девочка очень ответственная, вот что пишет по поводу постановки задачи: "Так нам, действительно, он именно так и сформулировал задачу.
+++ Скажите, как до Вас донести, что решения не существует?:-)
Все мои одногруппники плюнули и начали делать 3*3, а не 20*20, но даже в этом случае у них есть 2 или 3 способа, которым человек все-таки выигрывает, но они надеются, что преподаватель этими способами ходить не будет."
+++ Ну это просто позор для технического ВУЗа (он ведь технический?). На поле 3х3 второй завсегда может сделать ничью, и элементарно допетрить, как именно, имея только карандаш и бумагу.
Про 3*3 я знаю, мой муж в свое время еще для МК-61 такую прогу писал:):) А в ситуации с 20*20 возможно хотя бы не допускать проигрыша, как я поняла, проштудировав форумы.
А в ситуации с 20*20 возможно хотя бы не допускать проигрыша, как я поняла, проштудировав форумы.
+++ Я счас застрелюсь. Вы понимаете, что такое математически доказано? Дважды два равно четырем. Никаких "возможно хотя бы пять" не бывает. Можно убить себя об стену, прочитать все форумы и пережить конец света, все равно будет ровно четыре. Не пять, не 4,5, даже не 3,99, а только и исключительно 4.
+++ Вы можете убедиться в этом самостоятельно, ознакомившись с доказательством. Попутно, к сожалению, придется ознакомиться еще много с чем, поэтому можете просто поверить, что оно существует. Задача не имеет решения. Решения нет. Не бывает. Нельзя создать алгоритм, который не допустит проигрыша. Невозможно. Дважды два равно ровно четырем. Если сможете доказать обратное, Вас признают светилом науки, совершите переворот в математике, сравнимый по степени резонанса с признанием неправильности таблицы умножения, весь мир будет у Ваших ног.
+++ В качестве тренировки разработайте алгоритм, который не будет хотя бы проигрывать на поле 2х2. Шансов на успех столько же.
Ну хорошо, берем ситуацию, Вы играете со мной... Я начинаю- значит всегда выигрываю или как? Вариант ничьей и выигрыша в принципе невозможен?
По условиям задачи второй игрок должен КАК МИНИМУМ не проигрывать.
По факту при правильной игре первый игрок выигрывает ВСЕГДА, и как раз этому компьютер можно обучить.
Стравливаем две программы, одна правильно играет за первого, вторая - как угодно за второго. Вторая всегда будет проигрывать, а по условию задачи она этого делать не должна. Задача нерешаема.
С тем же успехом можно пытаться решить задачу на поле 2х2, почему Вы упорно игнорируете этот вариант?
Хоть как-то в математике не бывает. Если решения нет, его просто нет. И это ответ, как ни странно.
Если же очень хочется, чтобы решение было, условие задачи должно быть другим.
Ок, Вы меня убедили. Наверно:) странно, что так много людей пытаются это решить:)
В общем, спасибо за потраченное время:) Пусть пишут дальше в свете того, что начинает комп. Авось и получится. Времени осталось мучиться- до пятницы:)
Из википедии "Игра до 4 одинаковых знаков на бесконечном поле неинтересна, ибо начинающий довольно быстро строит «вилку» и выигрывает. Игра при n больше или равно 6 также неинтересна из-за «ничейной смерти». Существуют стратегии, не дающие противнику построить нужную линию никогда. Однако при n=5 игра становится намного содержательнее. Такой вариант имеет специальное название — гомоку. Изначально в гомоку играли на доске размером 19×19, позже она была уменьшена до размера в 15×15 клеток."
и оттуда же- доказано, что выигрывает первый ходок:):) Распечатаем преподу статью вики:)
Википедия, так википедия.
http://ru.wikipedia.org/wiki/Рэндзю
Развитие теории привело к пониманию того, что начинающие (чёрные) имеют преимущество, достаточное для победы при точной игре независимо от защиты белых.
Решения НЕТ.
Злые вы:(:( Все программеры такие злые:( муж вот, правда, уже давно не програмер, но тоже злой. Никто девочке помочь не может:)
Короче, мы решили, что начинать будет компьютер:) Правда, расписать правильную тактику на выигрыш- та еще задача.
Задача действительно сложная. Она не для первокурсника. Раз уж сложилась такая ситуация, по мне лучше сообщить преподавателю, что решения нет и решить классическую задачку для поля 3х3 - думать придется и там, но тут не нужны отсутствующие знания, достаточно включенного мозга и можно получить нормально работающий результат.
3*3 это на тройку. А девочка нацелена на, хотя бы, четверку. Тем более кое-что написала. Конечно, сомневаюсь, что смогла хотя бы не допустить проигрыш, но, надеюсь, преподаватель оценит стремление:)
Нет, я не сомневаюсь, я поняла что кто начинает- тот выигрывает.
+++ Замечательно:-)
Значит будет начинать компьютер- тогда же есть надежда на выигрыш, не так ли?
+++ Только при реализации алгоритма с выигрышной стратегией. И не надежда, а так и будет. В математике вообще нет понятия "надежда". Право первого хода - необходимое, но не достаточное условие. Он, алгоритм, ни фига не простой, методом тыка его не изобрести, а в остальных случаях программа может и проиграть сильному игроку. Или даже не очень сильному, а то и откровенно слабому - смотря сколько в ней дыр будет. Думаю, доморощенный алгоритм будет близок к третьему варианту, и преподаватель на раз-два программу обыграет. В итоге получится, что условие задачи изменили по своему усмотрению, в отличие от оригинальной, она имеет решение, но предъявить это решение не смогли. В чем смысл? Сделать хоть что-нибудь, что будет хоть как-то работать и иг с ним, что задание было другим?
+++ А еще я продолжаю подозревать, что Вы пытаетесь решить задачу отличную от той, что задал преподаватель и продолжаю не понимать, в чем проблема уточнить задание вместо того, чтобы биться головой об стену, заранее зная, что результата не будет.
+++ Вы бы купили чайник, который греет воду, но не до 100, а до 80 градусов, только если емкость заполнена не больше, чем наполовину и только если воду посолить?;-)
ну вот, препод сказал, что в пятницу все защищают свои программы- т.е. нужно предоставить блок-схему, суть алгоритма и собственно, саму программу. В итоге, ни у кого не принял. Те, кто 3*3 написал- были отправлены писать дальше:) а остальные (девочка почти всю ночь составляла блок-схему и описывала алгоритм:)) были отправлены улучшать и до следующей недели:)
Мутный препод какой-то... че он от детей хочет?
К сожалению, я не обладаю телепатическими способностями.
Как поступить на мой взгляд правильно, уже говорил: сказать, что задача в такой постановке решения не имеет и уточнить, может быть задача состояла все же в чем-то другом? Опционально, но именно опционально, можно решить какую-нибудь часть задачи.
Изобрести решение, которого не может быть в принципе, точно не получится.
ТО, что не имеет решения, человек скажет. А то, что задачу не уточнил, а просто послал дорабатывать - факт. Мож. он денег хочет? :dash1
Верно в том смысле, что при правильной игре обоих игроков будет ничья.
Начинающий при правильной игре выигрывает, если второй ошибется с первым ходом. Ставим крест в центр (b2), ответ НЕ в угол - ошибка, приводящая к выигрышу начинающего.
Чтобы выиграл второй, первый должен сильнее налажать:-)
как я понимаю, в 3*3 только два варианта. Кто первый начал либо выиграл, либо ничья. Ну и тетий вариант- первый не умеет играть и элементарно ошибается:)
А, да, критерий 5 рядом (диагональ-горизонталь-вертикаль). Первоначально в поле 100*100, потом упростили 20*20
Я себе так представляю, что проверяется ячейка- если "х" то проверяется следующая по горизонтали, если "х" -то в след. ставится "о". если пусто- то еще следующая проверяется и ставится "о" между. И так повторить для вертикали и диагонали. Чтобы не допустить три. Но это только на непроигрыш. А вот на выигрыш - выше моего знания алгоритмов:)