Есть ли решение?

[Vergo]

Здравствуйте.
Заинтересовался я одной идеей. Наверняка многие слышали про игру Bubble Breaker. Там нужно цветные шарики убирать и очки набирать. Причем многие ошибочно пытаются убрать все шарики с поля, хотя смысл игры в том, чтобы вырастить максимально длинную цепочку шариков одного цвета и получить за это максимум возможных очков.
Так вот, алгоритм самой игры особых сложностей не представляет. А возможен ли поиск оптимального решения? Порылся в интернете и ничего подобного не смог найти. Хотя изначально собирался сам состряпать,.. но подумал, а может уже есть протореная дорожка
В итоге состряпал сам. Вроде все красиво, но мощностей не хватает у компа, чтобы просчитать поле размером 11х12 Алгоритм самый банальный: слева-направо, сверху вниз. Причем он работает, я убедился.
Может мне кто-то сразу сможет сказать, что для того, чтобы просчитать подобную задачку методом прямого перебора всех возможных вариантов "В лоб", понадобится "....дцать миллионов лет машинного времени" или чего-нить подобное.
Квадратик 6х7 считает достаточно шустро. Укладываюсь в 10 секунд (изначально было намного больше). Хотя многое зависит от стартового расположения шариков.
И в некоторый момент времени программа как будто переходит порог.. и начинает работать значительно медленнее. Были у меня мысли по поводу того, что что-то кэшу не нравится. Но опыта в данном вопросе нет.
Вот. Если кто-то заинтересовался и сможет помочь, с радостью предоставлю код для разборок. Он небольшой, 2-3 листика. Написано на масме, плоская модель памяти.
Либо может есть идеи принципиально другого подхода к решению задачи. Можно даже в свободной форме изложить

[rpy3uH]

[OFFTOP]
предлагаю сделать конкурс программистов по разработке алгоритмов поиска решения. У кого он будет работать быстрее тот и выиграл. Если интересно, то пиши в личку, обмозгуем ....

[Vergo]

Да чего уж в личку, начну тут, может и другие втянутся
Возвращаюсь к своим баранам. Код разбит на процедуры, поэтому оптимизировать их достаточно удобно по отдельности. Для начала расскажу пару слов про свой алгоритм "решения" этой задачи.
Выбирается первая попавшаяся группа шариков одного цвета. Если в группе шариков не менее двух (по одному нельзя убирать), то снимаем группу с поля, делаем сдвиг остальных шариков на освободившиеся места и идем дальше. До тех пор пока на поле есть еще хоть одна группа. Когда групп больше нет, возвращаемся на шаг назад, восстанавливаем удаленную группу, помечаем ее, и пытаемся найти другую группу шариков. Алгоритм рекурсивный.
Подобным методом решают задачи по прохождению лабиринта. Заходят в первую попавшуюся комнату и если из нее есть проход дальше, то идут дальше, пока не упрутся в стену. Затем помечают комнату как пройденную и возвращаются на шаг назад.
Все ходы в памяти сохранить не удастся, поэтому решил отвести буфер лишь для одной полной ветки "дерева" решений. В поле размером 11х12 максимальное теоретическое количество групп шариков равно 66 (11*12/2).
После каждого хода количество групп на поле уменьшается, поэтому достаточно сохранять примерно 50 промежуточных состояний.
Задача разбивается на 4 подзадачи. Основной цикл, в котором осуществляется переход по дереву решений, и три рабочих процедуры. Одна считает, сколько шариков в группе. Вторая - делает смещение шариков после хода. Третья - добавляет новый узел к дереву решений. Тут необходимо будет уточнить кое-какие тонкости, но это я сделаю позднее. Последняя процедура, судя по анализатору кода, получилась самой тяжелой.
В следующем посте выложу код для разборок одной из процедур. Только пояснения добавлю.

[Vergo]

    .586P
    .MODEL FLAT, stdcall
    option casemap:none

sizenod	=	16*14	;столько отводим места для одного узла
xx	=	11	;ширина поля
yy	=	12	;высота поля
zz	=	sizenod-18	;пока скажу, что это стартовое
    				;смещение в поле для работы
    				;процедуры сдвига шариков.
				;Правый нижний угол узла
    .data

pole DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;это стартовая позиция
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;сейчас заполнено
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;поле размерностью
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;7х6 (дабы снизить
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;время вычислений
        DB      0,0,0,0,0,0,0,0,5,3,3,3,5,3,5,0
        DB      0,0,0,0,0,0,0,0,5,4,4,4,1,4,5,0  ;1 - красный шарик
        DB      0,0,0,0,0,0,0,0,5,3,3,4,2,5,4,0  ;2 - синий
        DB      0,0,0,0,0,0,0,0,4,4,2,4,3,2,5,0  ;3 - зеленый
        DB      0,0,0,0,0,0,0,0,4,1,2,2,2,2,4,0  ;4 - желтый
        DB      0,0,0,0,0,0,0,0,3,3,3,2,3,3,3,0  ;5 - фиолетовый
        DB      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  ;0 - пустое место

thisnod   DWORD   0             ;базовый адрес текущего узла
score     DWORD    0             ;подсчет очков
lvl_nod   DB           0             ;уровень узла (уже вроде устарело)
color      DB            0             ;цвет текущей группы шариков
fill          DB            0             ;удаяем или помечаем - зависит от этого байта
ggg        DB          5 DUP (0)     ;просто выравнивание памяти
;------------------------------------------------
;line       DB      56 DUP (0)	     ;в дальнейшем задействуется для записи 
			     ;цепочки ходов оптимального решения 
basa    DB      sizenod*56 DUP (0)	;Буфер. Тут растет "веточка нашего дерева"
;------------------------------------------------

    .code

start:
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

        mov     esi, OFFSET pole          ;первый узел дерева
        mov     edi, OFFSET basa          ;создаем вручную, т.е.
        mov     thisnod, edi		;копируем исходное поле
        cld				;в начало буфера	
        mov     ecx, sizenod/4
        rep movsd

        call MAIN		              ;заныриваем в глубокий рабочий цикл :)
        
        ret

Примечание:
интерфейса ввода-вывода у программы на данный момент нет. На данном этапе и не надо. Стартовая позиция вбивается в область данных, результат можно посмотреть через отладчик. Главное сейчас - попытаться оптимизировать. А остальное дело техники.

MAIN PROC

        push    ecx
        push    ebx
        push    edx

        call    NEXT_NOD	;добавлем новый узел
        call    SHIFT		;наводим там порядок (сдвигаем шарики)

        mov     ecx, sizenod	;ecx - размер поля (узла)
        mov     ebx, thisnod	;ebx - базовый адрес текущего узла
L1:
        inc     ebx
        cmp     byte ptr [ebx], 0	;ищем шарик на поле
        jnz     L2
        loop    L1
        jmp     L99
L2:
        cmp     byte ptr [ebx], 10h	;смотрим, что же мы нашли.
        jl      L4			;Скажу заранее - помечается пройденная
        loop    L1			;группа шариков операцией add 10h.
        jmp     L99			;Если шарик не помечен - идем на L4
L4:
        mov     byte ptr fill, 0FFh          ;в текущем узле шарики не удаляются,
				;а только помечаются на удаление числом 0FFh.

        call    STEP			;STEP - процедура подсчета размера группы. И не только подсчета.
        cmp     eax, 1		;Возвращает в eax количесво насчитанных шариков.
        jnz     L3			;Если есть группа - идем на L3
        loop    L1			;если нет - проверяем след клетку текущего узла.
        jmp     L99
L3:
        mov     dh, byte ptr color	
;       call    COUNT 		     ;процедура подсчета очков. Пока не актуальна.

        call    MAIN			     ;вызываем саму себя (рекурсия, однако)

        add     dh, 10h		     ;после возвращения с дочернего узла
        mov     byte ptr fill, dh                  ;восстанавливаем и помечаем удаленную группу 
        call    STEP
        loop    L1
L99:
        dec     byte ptr lvl_nod	       ;уменьшаем лвл узла
        sub     dword ptr thisnod, sizenod      ;и восстанавливаем адрес текущего узла

        pop     edx
        pop     ebx
        pop     ecx

        ret
MAIN ENDP

[Vergo]

NEXT_NOD PROC
        push    ecx		;процедура добавляет к дереву новый узел,
        mov     esi, thisnod	;копирует в него позицию с родительского узла,
        mov     edi, esi              ;при этом клетки, помеченные на удаление (0FFh) - удаляем,
        mov     ecx, sizenod	;а клетки, которые были помечены на родительском узле
        add      edi, ecx	;как пройденные - приводим в непомеченное состояние (sub 10h)
        mov     thisnod, edi
        inc       byte ptr lvl_nod
L0:        
        lodsb
        cmp     al, 10h
        jl         L1
        sub     al, 10h
        jmp     L99
L1:
        cmp     al, 0FFh
        jnz      L99
        xor     al, al
L99:
        stosb
        loop    L0

        pop     ecx
        ret
NEXT_NOD ENDP

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

P.s.: Возможно вместо числовых значений тут стоит воспользоваться половинкой одного из регистров...

[Vergo]

STEP PROC
        push    ecx		             ;процедура подсчета соседей
        push    edx		             ;и заполнения найденной группы
				;байтом fill
        mov     dl, byte ptr fill	             ;ebx - стартовый адрес группы
        mov     dh, byte ptr [ebx]             ;eax - счетчик шариков в группе	
        mov     byte ptr color, dh              ;ecx - запоминаем предыдущий шаг
        xor     eax, eax
        mov     ecx, ebx
L1:    
        inc     eax
        mov     byte ptr [ebx], dl
L2:    
        push    ebx
        sub     ebx, 10h		 ;идем наверх
        cmp     byte ptr [ebx], dh
        jz      L1

        add     ebx, 11h		 ;идем направо (относительно старта)
        cmp     byte ptr [ebx], dh
        jz      L1

        add     ebx, 0fh	              ;идем вниз
        cmp     byte ptr [ebx], dh
        jz      L1
        
        sub     ebx, 11h	               ;идем налево
        cmp     byte ptr [ebx], dh 
        jz      L1

        pop     ebx		;стек используем для исключения багов в
        cmp     ebx, ecx	;"перекрестках" или развилках
        jz      L98
        pop     ebx
        jmp     L2
L98:
        cmp     eax, 1
        jnz     L99
        mov     byte ptr [ebx], dh
L99:
        pop     edx
        pop     ecx

        ret
STEP ENDP

[Vergo]

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

SHIFT PROC
        push    ebx
        push    ecx
        push    edx
        mov     ebx, dword ptr thisnod

        mov     esi, zz
        mov     edi, esi
        mov     ecx, xx
L0:
        push    ecx
        push    edi
        push    esi

        add     esi, 10h
        mov     ecx, yy
L1:
        sub     esi, 10h
        cmp     byte ptr [ebx+esi], 0
        jnz     L2
        loop    L1
        jmp     L3
L2:
        mov     dh, byte ptr [ebx+esi]
        mov     byte ptr [ebx+esi], 0
        mov     byte ptr [ebx+edi], dh
        sub     edi, 10h
        loop    L1
L3:    
        pop     esi
        pop     edi
        pop     ecx

        dec     esi
        dec     edi
        loop    L0
;-----------------------
L4:
        mov     esi, zz
        mov     edi, esi
        mov     ecx, xx
L5:
        cmp     byte ptr [ebx+esi], 0
        jz      L6
        dec     esi
        dec     edi
        loop    L5
        jmp     L99
L6:
        dec     esi
        cmp     byte ptr [ebx+esi], 0
        jnz	    L7
        loop    L6
        jmp     L99
L7:
        mov     ecx, yy
L8:
        mov     dh, byte ptr [ebx+esi]
        mov     byte ptr [ebx+esi], 0
        mov     byte ptr [ebx+edi], dh
        sub     esi, 10h
        sub     edi, 10h
        loop    L8
        jmp     L4
L99:
        pop     edx
        pop     ecx
        pop     ebx
        ret
SHIFT ENDP

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

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
end start