Ave: Вставка в richedit

https://forum.sources.ru/index.php?showtopic=421159&view=findpost&p=3845506

MBo: Для выделения части строки используйте функцию Copy

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845500

swf: Метод минимакса, который используют для игр двух лиц с полной информацией, описан в книге Нильса Нильсона "Принципы искусственного интеллекта".
Есть два игрока, назовём их Мин и Макс. Мин минимизирует свой проигрыш, Макс максимизирует свой выигрыш. Каждая позиция - вершина игрового дерева. Дерево "слоистое", чередуются слои с ходом Мина и слои с ходом Макса. Мы играем за Макса, неважно, какой ход он делает, первый или второй. Начинаем строить дерево от текущей позиции с ходом Макса.
Теперь, внимание, игровое дерево строится с порождением всех возможных ходов для каждой позиции. Это полный перебор. И его (дерево) для данной размерности мы не построим вплоть до позиций, где игра заканчивается. Строим, докуда можем. Построили. Теперь придумываем эвристическую оценочную функцию, чтобы оценивать позицию одним числом. Её придумывают так, чтобы позиции с большей оценкой были выгодны Максу. Для листов (позиций без продолжения) рассчитываем оценку согласно эвристике, затем оценка распространяется вверх к корню дерева и Макс выбирает из всех возможных ходов ход с большей оценкой.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845496

OpenGL: Да просто запусти обход вглубь из текущей вершины

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845495

kiddan: Добрый день, вопрос может и глупый но решить не могу! Есть переменная S string, имеет в себе n- количество символов, нужно разбить её на строки по 5 символов и записать в файл. Пример s:= '1234567890098765432101'; на выходе 12345
67890
09876
54321
01

https://forum.sources.ru/index.php?showtopic=421262&view=findpost&p=3845489

FasterHarder:
изначально так и было (в первых сообщениях), а потом уже по совету amk инвертировал, но это ведь НЕ принципиально с т.з. алгоритма

AVA12, выше ведь писал, что планирую запускать BFS от каждого тупика, а сам тупик закрашен "красным". Насчет правил, да, согласен, конечно, и они выработаны, но здесь все равно, что-то не всегда четко, т к к конкретной вершине можно подойти разными путями, при этом она может иметь разный цвет в зависимости от подхода.

Вообще, надо бы разобраться подетальнее с этой раскраской, конечно, чтобы снять любые сомнения.
Все тупики получены. Сразу их все безраздумья красим в красный цвет. Тут однозначно!
Перебираем в цикле все тупики. Берем i-й тупик и запускаем от него BFS. Не уверен, что бфс тут идеально подходит, но вроде должен подходить) (прим. дуги к этому моменту в орграфе инвертированы + также все вершины кроме тупиковых имеют "серый" цвет, якобы непосещенные). Т е все возможны 3 цвета: красный (ход туда ведет к победе), зеленый (ход туда приводит к победе противника), серый.

возможные случаи раскраски:
1. стоим на красной вершине и дуга к серой ---> красим серую в зеленый - тут вроде однозначно.
2. стоим на зеленой вершине и дуга к серой ---> красим серую в красный - тут вроде однозначно.
3. стоим на зеленой и дуга к зеленой. хм... Тут момент: а надо ли зеленую перекрашивать в красный? получается, что, НЕТ! сделав вершину-достижения красной будем обман игрока, он подумает, что надо в нее заходить, а соперник потом переведет его дальше в красную). Т е вариант "зеленая-зеленая" оставляем без изменений
4. стоим на красной и дуга к красной. хм... Тут момент: а надо ли красную перекрашивать в зеленую? получается, что, ДА! если оставить красной, то это будет обманкой для игрока, т к соперник его следующим ходом переведет в красную.
все, др.комбинаций здесь нет.

что-то мне подсказывает, что это НЕТОЧНЫЙ алгоритм раскраски, который не учитывают все возможные случаи. Как обычно с графами, все намного тоньше и умнее)
что не так с подалгоритмом раскраски??

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845487

Rouse_: Вообще эта плавающая точка тот еще зверек.
Давеча вылезла ошибка у одного из клиентов, казалось бы обычное число 8.07875.
Но если это число было в Double и его присвоить переменной типа Currency то под 64 бита получим 8.0788, а под 32 - 8.0787 и дальше все рассчеты поплывут :wall:

Случайно наткнулись.

Выкрутится конечно можно примерно так:


Но есть еще неявные преобразования, поэтому похоже придется использовать кастомные типы и все преобразования делать через "class operator Implicit/Explicit"

https://forum.sources.ru/index.php?showtopic=421187&view=findpost&p=3845486

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

P. S. У тебя на картинке цвета инвертированы. По-моему нагляднее так: красный цвет - "ты туда не ходи", зеленый цвет - "ты сюда ходи".

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845479

Bas: Может быть не прав, но срытые символы Вы обрабатываете? Давно не подходил к компу.

https://forum.sources.ru/index.php?showtopic=419400&view=findpost&p=3845476

FasterHarder: Akina, интересный граф и проблемы в программе возникли)
______________________.png (, : 40)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845473

Akina:

32.png (, : 50)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845468

amk: В таких играх не рассматриваются пути - только позиции. Путь интересен только проигрывающему - для него выгодно затянуть игру в надежде, что выигрывающий игрок ошибётся.
Не надо смотреть смежные вершины, пометка вершины уже сообщает тебе, выигрываешь ты или нет (см поправку в описании алгоритма). Смежные

Я допустил ошибку при именовании пометок. Вершину графа игры (позицию) принято считать выигрышной, если игрок, начиная в ней игру, при правильной стратегии выигрывает. Поэтому в описании надо поменять местами выигрышные / проигрышные позиции.

С этой поправкой алгоритм выглядит так:
Изначально все вершины непомеченные (помечены как неопределённые).
1. Тупиковые вершины помечаются как проигрышные - начиная в них игру игрок сразу проигрывает.
2. Вершины, из которых можно передвинуть фишку в проигрышную позицию помечаем как выигрышные - из них мы может передвинуть фишку в позицию, из которой противник проиграет.
3. Вершины, из которых все пути ведут в выигрышные позиции, помечаем как проигрышные - из них мы вынуждены передвинуть фишку в позицию, ведущую к выигрышу противника.

При маркировке позиций можно дополнительно определить число полуходов до окончания игры.
Вершины помеченные по первому пункту алгоритма получают оценку 0.
По второму - минимальная из оценок соседних проигрышных вершин + 1.
По третьему - максимальную из оценок соседних вершин (все они выигрышные) + 1.

При ходе из выигрышной позиции оптимальный ход делается в проигрышную позицию с минимальной оценкой - выигрывающий стремится как можно быстрее выиграть.
При ходе из проигрышной позиции оптимальный ход делается в позицию с максимальной оценкой - проигрывающий стремится затянуть игру.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845462

FasterHarder:


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

Добавлено 16.03.21, 10:08
Подытожим алгоритм! Кому не лень и несложно, плиз проверьте + поправьте, если что.

1. находим все возможные тупики от заданной вершины. Всего в графе N вершин. Будет одномерный массив, состоящий из N элементов. У тупиков будут стоять 1цы, у остальных 0. Поиск тупиков через ДФС(стек)
2. помечаем все тупики статусом "победа"
3. инвертируем дуги исходного графа!
4. в цикле перебираем все тупики и от каждого тупика запускаем BFS (очередь). Помечаем чередованием вершины статусом "победа-поражение". ВАЖНО! Если встретилась вершина со статусом "победа", а ей для данного пути надо поставить статус "поражение", то ставим "поражение", т к у "поражения" высочайший приоритет. Также не меняем статус "поражение" на "победа" при возникновении обратной ситуации. Есть такой момент здесь: при обходе BFS будет задействовано много "лишних" вершин, которые не принадлежат ни одному из возможных путей. Это некритично - не обращаем на это внимания) На самом деле не оч.понятно, в какой момент заканчивать BFS, запущенный от текущего тупика. Ладно, пусть работает до упора - это НЕ оптимально и здесь можно как-то усовершенстовать.
5. после назначения статуса "победа-поражения" смотрим смежные вершины от стартовой. Если есть хотя бы одна вершина со статусом "победа" - победил игрок №1, иначе игрок №2.

Для статуса "победа-поражение", наверное, завести отдельный одномерный массив из N элементов (0 - поражение, 1 - победа). По дефалту поставить всем статус = 1.
язык Си, никаких STL-ских (делающих всю работу) приблуд

примерно так

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845451

FasterHarder:
вот это, пожалуй, остался единственный момент в этой задаче, с которым бы разобраться

на мое ИМХО, "чей ход" вообще учитывать НЕ нужно.
мы ведь раскрашиваем граф как бы волнами (через BFS, наверное, надо будет сделать), где эпицентром является один из тупиков.
и в конце концов волны доходят до стартовой вершины и все.
и вроде достаточно просто посмотреть на:


т е раскраска автоматически чередует ходы игроков и дополнительно это уже не надо анализировать...
прикладываю картинку-доказательство)
_____________________.png (, : 86)

p.s. может быть я здесь сильно ошибаюсь и поторопился с таким выводом

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845444

Akina:
А тут зависит от того, чей ход. Если твой, и есть выигрышный путь - вершина выигрышная. Если не твой, и есть проигрышный путь - вершина проигрышная. Варианты, когда все пути одного типа - тривиальны.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845443

FasterHarder: amk, прикольный метод с раскраской, у меня даже мысли не возникло про это)

но есть ряд моментов!
1. некая взятая вершина может принадлежать разным путям. Для одного пути - победная, для другого - проигрышная. Как понимаю приоритет имеет "проигрышный" статус вершины, т к никто из игроков не хочет оказаться в этой вершине независимо от того по какому пути дошел до нее, т к немедленно будет наказан соперником??
2. чтобы понять, побеждает игрок №1 или №2 надо раскрасить граф и просто посмотреть на ПЕРВЫЙ ход 1ого игрока: есть ли смежная хотя бы ОДНА победная вершина?? Их может быть НЕСКОЛЬКО - игрок №1 может вставать в любую.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845442

amk: На самом деле никакие пути искать не надо. Такие задачи решаются раскраской графа.
Вершины помечаются как выигрышные и проигрышные. И по этой раскраске строится оптимальная стратегия.

Изначально все вершины непомеченные (помечены как неопределённые).
1a. Тупиковые вершины помечаются как выигрышные - поставив в них фишку мы выигрываем.
2. Вершины, из которых можно передвинуть фишку в выигрышную позицию помечаем как проигрышные - если мы поставим в них фишку, противник передвинет её в выигрышную позицию и выиграет.
1b. Вершины, из которых все пути ведут в проигрышные позиции, помечаем как выигрышные - если мы поставим в них фишку, противник будет вынужден передвинуть её в проигрышную позицию.

Закрасив исходную позицию, мы получаем оптимальную стратегию и определяем, кто при оптимальной стратегии выигрывает.
Алгоритм работает и для некоторых графов с циклами, если выигрывающей стороне удаётся обойти цикл.

Поправка: Позиция называется выигрышной, если игрок, делающий в ней ход выигрывает.
Поэтому в описанном алгоритме надо поменять местами проигрышные и выигрышные позиции.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845440

FasterHarder: Akina, я лишь частично (очень частично) понял твое сообщение.
Как мне показалось, ты намекаешь на выигрышную стратегию, например для игрока №1. Выигрышная стратегия - стратегия, приводящая к победе, независимо от ходов противника (при безошибочной игре противника не всегда существует). Смысл ее в том, что игрок №1 "направляет" игрока №2 по нужному пути независимо от того, как сходит игрок №2.
Игроку №1 надо, чтобы расстояние до тупика было НЕЧЕТНЫМ (1, 3, 17, 9999 шагов и т.д.) или четным, если рассматривать случай, когда игрок №1 уже походил в какую-то вершину. Например, стоит игрок №1 в стартовой вершине, перед ним развилка на 173 смежных вершины. Ему нужно сходить в вершину, расстояние от которой до тупика четное число. Затем ходит игрок №2 - куда захочет. Игрок №1 снова выбирает из набора возможных путей ту вершину, расстояние до тупика которое четно и т.д. Т е игрок №1 постоянно "навязывает" свой путь независимо от того, куда сходил игрок №2. Все это хорошо, но ведь возможны случаи, когда ходит игрок №1 и перед ним стая вершин и у КАЖДОЙ вершины расстояние до тупика - нечетное число. Выбора как бы нет, но это не означает, что игрок №1 не может выиграть. Он может временно согласиться пройти по "неправильному" для него пути, а через несколько итераций снова задать свое направление.
Да, я понимаю, что в своем сообщении ты не это описывал), просто решил написать про выигрышную стратегию, которая здесь вот таким образом не применима.

Akina, я бы хотел провести декомпозицию алгоритма на подалгоритмы, т к мне не хватает ума все это охватить и понять сразу. И пусть будет неоптимально, просто бы хоть как-то понять. (хотя в задаче еще есть ограничение по времени 8-) , т е как бы намек на то, что метод грубой силы тут не нужен, хотя я не уверен, что без него вообще можно реализовать)
---------------------------------------------------------
Вот хотелось бы понять, насколько все это пригодится в решении (забыл сделать ремарку, что тупиков может быть больше одного, разумеется + из конкретной вершины можно проложить путь разной протяженности до разных тупиков):
1. Получение всех тупиков достижимых из заданной вершины. В этом может помочь DFS+стек (вроде стек, а не очередь, т к она для BFS вроде). В результате будет сформирован одномерный массив вершин в том или ином виде. Хотя структуры данных оч.важны тоже, разумеется - без них дело гиблым оказывается при кодировании)
2. Получить множество всех вершин, через которые может проходить какой-либо путь до какого-либо тупика
3. ДЛЯ КАЖДОЙ вершины из п.2 найти расстояние ДО КАЖДОГО тупика! Это двумерный массив, где по оси Ох, допустим откладываются тупики, по оси Oy - №вершины, а на пересечении - расстояние между ними (или можно просто true/false аля чет/нечет длина)

И вот владея этой информацией (из п.3) разве невозможно проанализировать победу игрока №1 или №2??
Например, есть стартовая вершина и ходит игрок №1. Он может "просмотреть" все возможные пути (конкретно расстояния) до каждого достижимого тупика из этой вершины. Проблема выбора остается, т к путей нечетной длины может быть несколько...непонятно какой взять... :unsure: ... а может ЛЮБОЙ)) навряд ли...

в общем пока я далек от глубоко понимания решения поставленной задачи. нужна помощь)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845439

Akina: Начинать надо с "построения всех путей в графе". В данном случае строятся все пути от исходной вершины, приводящие в тупик. Далее - ищем "нечётные пути" (пути с нечётным числом рёбер), от которых "чётные" ответвляются только на "нечётных" шагах, а также "чётные" с ветвлением на "чётных" шагах, имеющих ответвление на "нечётный" путь на "нечётном" шаге, и т.п.

Реально это решается обратной задачей - т.е. после построения всех путей начинаем "закрашивать" проигрышные пути, сначала от тупиков, потом на "чётных" ветвлениях. Если в итоге получился незакрашенный путь от исходной вершины - первый выиграл, иначе выиграл второй (само собой предполагаем, что игроки делают наилучшие ходы).

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845436

FasterHarder: Всем хай! Сходу к делу!

Дан граф (ациклический, ориентированный невзвешенный). Кол-во вершин и дуг может быть несколько сотен тысяч (поэтому частные случаи даже можно не рассматривать). На произвольной вершине (стартовая вершина) кладут фишку. Есть 2 игрока. За один ход каждый из них может передвинуть фишку на смежную вершину по дуге. Игроки ходят по очереди. Цель игрока - загнать противника в тупик, т е получить ситуацию, когда у соперника нет хода. Побеждает тот, кто загнал противника в тупик.
------------------------------------------------------------------
Сначала показалось, что это несложно, но, подумав, осознал, что здесь что-то совсем для меня непростое...
Самая главная проблема - наличие параллельных путей при достижении тупика. Если бы их не было, тогда поиском в глубину все бы решилось нормально.

Это ведь задача на поиск оптимальной стратегии, как я понимаю. Но я не уверен, что ее можно в принципе получить, т к каждый ход все меняется и КАЖДЫЙ из игроков в каждый момент своего хода выбирает как бы "новую" оптимальную стратегию или по крайней мере ухудшает оптимальную стратегию противника.

Мне бы просто понять, к чему здесь стремиться), к каким алгоритмам и структурам данных.

Какие были мысли:
1. получать расстояния для каждого игрока от вершины с фишкой до всех тупиковых вершин (только тупиковых) + смотреть на четность-нечетность сделанных шагов. Но вроде это бессмысленно, т к алгоритмы типа Дейкстры находят кратчайшие пути, а ведь далеко не факт, что противник будет также следовать по этим кратчайшим путям и свернет на параллельный путь, убив весь этот анализ.
2. построить матрицу расстояний между всеми вершинами (алгоритм Флойда или +Уоршелла). Возможно, что это пригодится в каком-то моменте основного алгоритма. Но сама по себе эта матрица не решает проблему исходной задачи.
3. задействовать поиск в глубину(DFS). Уверен, что здесь это точно надо юзать!). Но, вообще, ДФС ведь нужен для ОБХОДА вершин графа, а НЕ для прокладки путей. Но благодаря дфс можно достаточно легко получить тупиковые вершины. Проблема, что вариантов достижение тупика от заданной вершины может быть тысячи (параллельные пути) + противник своим ходом может свернуть куда ему выгодно.
4. как-то применить топологическую сортировку графа. Это я от балды говорю)
---------------------------------------------------------------------
Как я понимаю, ведь по сути игроки равносильные исполнители, у них одинаковая возможность хода и анализа, т е достаточно понять, как действовать одному игроку, значит, 2ой будет действовать аналогично со своей колокольни только)
Я правильно понимаю, что анализ нужно проводить динамически, т е от вершины, где лежит фишка и НИКАКОГО предварительного анализа (до начала игры) делать НЕ нужно, да??

Вот хотелось бы понять, что конкретно нужно делать, когда делается ход игроком (не важно каким) от вершины с фишкой. Т е самое важное, как я вижу, понять, какие конкретно шаги предпринимать игроку в начале своего хода для вершины с фишкой - остальное уже тиражируется на все решение целиком. + какие структуры данных тут пригодятся

спс за внимание)

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845433