#include <JogoDoGalo.h>

Inheritance diagram for CJogoDoGalo:

Collaboration diagram for CJogoDoGalo:

Public Member Functions
	CJogoDoGalo (void)

	~CJogoDoGalo (void)

TProcuraConstrutiva *	Duplicar (void)
	Cria um objecto que é uma cópia deste.

void	Copiar (TProcuraConstrutiva *objecto)

void	SolucaoVazia (void)
	Coloca o objecto no estado inicial da procura.

void	Sucessores (TVector< TNo > &sucessores)
	Coloca em sucessores a lista de estados sucessores.

bool	SolucaoCompleta (void)
	Verifica se o estado actual é objectivo (é uma solução completa)

void	Debug (void)
	Mostra o estado no ecrã, para debug.

const char *	Acao (TProcuraConstrutiva *sucessor)

void	TesteManual (const char *nome)
	Inicializa a interação com o utilizador.

void	Codifica (uint64_t estado[OBJETO_HASHTABLE])
	Codifica o estado para um vetor de inteiros de 64 bits.

int	Heuristica (void)
	Função para calcular quanto falta para o final, o valor da heurística.

Public Member Functions inherited from TProcuraAdversa
	TProcuraAdversa (void)

	~TProcuraAdversa (void)

void	ResetParametros ()
	Método para inicializar os parâmetros (redefinir se forem adicionados parâmetros específicos)

int	MiniMax (int nivel=4)
	retorna o valor do estado actual, apos procura de profundidade nivel

int	MiniMaxAlfaBeta (int nivel=4, int alfa=-infinito, int beta=+infinito)
	retorna o valor do estado actual, apos procura de profundidade nivel. Idêntico a MiniMax

void	TesteEmpirico (int inicio=-1, int fim=-1, bool mostrarSolucoes=true)
	Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.

int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parametros atuais.

int	Heuristica (void)
	chamar após calcular a heurística (grava o valor, dependendo da parametrização)

bool	ExisteHeuritica (void)

int	MaiorAmeaca (TVector< int > &qMin, TVector< int > &qMax, int maxAmeaca)
	Utilitário para calculo de uma heurística standard em jogos simples.

Public Member Functions inherited from TProcuraConstrutiva
	TProcuraConstrutiva (void)

virtual	~TProcuraConstrutiva (void)

virtual void	Copiar (TNo objecto)
	Fica com uma cópia do objecto.

virtual const char *	Acao (TNo sucessor)
	Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.

virtual bool	Acao (const char *acao)
	Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.

virtual bool	Parar (void)
	Verifica se a procura deve ser interrompida.

virtual bool	Distinto (TNo estado)
	Verifica se o estado actual distinto do fornecido.

virtual void	MostrarSolucao (void)
	Mostrar solução, seja um caminho ou o próprio estado.

int	LarguraPrimeiro (int limite=0)
	Executa a procura em largura primeiro, algoritmo cego.

int	CustoUniforme (int limite=0)
	Executa a procura por custo uniforme, algoritmo cego.

int	ProfundidadePrimeiro (int nivel=0)
	Executa a procura em profundidade primeiro, algoritmo cego.

int	MelhorPrimeiro (int nivel=0)
	Executa a procura melhor primeiro, algoritmo informado.

int	AStar (int limite=0)
	Executa a procura A*, algoritmo informado.

int	IDAStar (int upperBound=0)
	Executa a procura IDA*, algoritmo informado.

int	BranchAndBound (int upperBound=0)
	Executa o algoritmo Branch-and-Bound, um algoritmo informado.

void	LimparEstatisticas (clock_t &inicio)

void	FinalizarCorrida (clock_t inicio)

int	LowerBound ()

void	NovaLinha (bool tudo=true)

Public Attributes
TVector< char >	tabuleiro

Public Attributes inherited from TProcuraAdversa
bool	minimizar
	o jogador actual deve minimizar o custo (ou maximizar caso tenha o valor falso)

Public Attributes inherited from TProcuraConstrutiva
TNo	pai
	Ponteiro para o estado pai, na árvore de procura.

int	custo
	Custo total acumulado desde o estado inicial.

int	heuristica
	Estimativa para o custo até um estado objetivo, se disponível.

Additional Inherited Members
Static Public Member Functions inherited from TProcuraConstrutiva
static void	LibertarVector (TVector< TNo > &vector, int excepto=-1, int maiorQue=-1)

static int	NovoValor (const char *prompt)

Static Public Attributes inherited from TProcuraAdversa
static int	infinito = 1000
	valor de infinito (vitoria/derrota), omissao 1000

static bool	completo
	controlo para indicar se a procura foi realizada de forma completa (c.c. foi cortada)

static int	nivelOK = 0
	profundidade máxima no método iterativo

Static Public Attributes inherited from TProcuraConstrutiva
static TParametro	instancia = { NULL,1,1,1, NULL, NULL }
	ID da instância atual, a ser utilizado em SolucaoVazia().

static TVector< TParametro >	parametro
	Parâmetros a serem utilizados na configuração atual.

static TVector< TVector< int > >	configuracoes
	Conjuntos de configurações para teste empírico.

static int	geracoes = 0
	Número total de gerações realizadas na procura.

static int	expansoes =0
	Número total de expansões realizadas na procura.

static int	avaliacoes =0
	Número total de avaliações realizadas na procura.

static TVector< TNo >	caminho
	Solução retornada pela procura (os estados devem ser libertados).

static bool	memoriaEsgotada = false
	Flag indicando problemas de memória esgotada.

static TNo	solucao =NULL
	Estado objetivo encontrado, retornado pela procura (deve ser libertado).

static int	lowerBound = 0
	Valor mínimo que a solução pode apresentar, obtido pela procura.

static int	tamanhoCodificado = OBJETO_HASHTABLE
	Número de inteiros de 64 bits utilizados para codificar um objeto (≤ OBJETO_HASHTABLE).

static TVector< unsigned char >	ramo

static int	espacosRamo =2

static clock_t	instanteFinal = 0

Protected Member Functions inherited from TProcuraAdversa
int	NoFolha (bool nivel)
	fim da procura, por corte de nível (ou não haver sucessores), retornar heurística

bool	CorteAlfaBeta (int valor, int &alfa, int &beta)
	verifica se há um corte alfa/beta, atualizando alfa e beta

int	MetodoIterativo (int alfaBeta)
	iteração, aumentando o nível progressivamente

void	OrdenarSucessores (TVector< TNo > &sucessores, TVector< int > &id, int nivel)

void	SubstituirHT (int indice)

bool	ExisteHT ()

bool	ValorEstado (TValorEstado &valor, int operacao)
	ler ou gravar o melhor valor conhecido

bool	Utilizavel (TValorEstado &valor, int nivel, int alfa, int beta)
	ver se o valor obtido é utilizável no contexto atual

Protected Member Functions inherited from TProcuraConstrutiva
void	DebugExpansao (int sucessor, int sucessores, bool duplo=false)

void	DebugCorte (int sucessores=-1, bool duplo=false)

void	DebugSolucao (bool continuar=false)

void	DebugChamada (void)

void	DebugPasso (void)

void	DebugSucessores (TVector< TNo > &sucessores)

void	DebugIteracao (int iteracao)

void	DebugEstado (int id=-1, int pai=-1)

void	DebugRamo (char ramo, char folha)

int	ObjetivoAlcancado (int item, TVector< TNo > &lista)

int	ObjetivoAlcancado (TNo estado, bool completa=true)

int	SolucaoEncontrada (bool continuar=false)

void	CalculaCaminho (bool completa=true)

void	VerificaLimites (int limite, int porProcessar, TVector< TNo > &sucessores)

void	CalcularHeuristicas (TVector< TNo > &sucessores, TVector< int > *id=NULL, bool sortLB=false)

int	SolucaoParcial (int i, TVector< TNo > &sucessores)

void	ExplorarSucessores (bool jogo=false)

void	EditarParametros ()

void	EditarConfiguracoes ()

void	MostrarConfiguracoes (int detalhe, int atual=-1)

void	SolicitaInstancia ()

bool	TempoExcedido ()

bool	GeracoesExcedido ()

bool	ExpansoesExcedido ()

bool	AvaliacoesExcedido ()

void	MostrarCaminho ()

void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)

void	MostraRelatorio (TVector< TResultado > &resultados)

int	Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)

void	ConfiguracaoAtual (TVector< int > &parametros, int operacao)

int	MelhorResultado (TResultado base, TResultado alternativa)

void	CalculaTorneio (TVector< TResultado > &resultados)

void	MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)

void	BarraTorneio (bool nomes)

void	ExtrairConfiguracao (TVector< TResultado > &resultados, TVector< TResultado > &extracao, int configuracao)

unsigned int	Hash ()

void	LimparHT ()

bool	ExisteHT ()

Protected Attributes inherited from TProcuraAdversa
int	indiceHT

Static Protected Attributes inherited from TProcuraAdversa
static TValorEstado	valorHT [TAMANHO_HASHTABLE]

static int	reutilizadoAvaliacao

Static Protected Attributes inherited from TProcuraConstrutiva
static uint64_t	elementosHT [TAMANHO_HASHTABLE][OBJETO_HASHTABLE]

static int	custoHT [TAMANHO_HASHTABLE]

static uint64_t	estadoCodHT [OBJETO_HASHTABLE]

static int	colocadosHT = 0

Detailed Description

Definition at line 14 of file JogoDoGalo.h.

Constructor & Destructor Documentation

◆ CJogoDoGalo()

CJogoDoGalo::CJogoDoGalo ( void )

Definition at line 4 of file JogoDoGalo.cpp.

Here is the caller graph for this function:

◆ ~CJogoDoGalo()

CJogoDoGalo::~CJogoDoGalo ( void )

Definition at line 8 of file JogoDoGalo.cpp.

Member Function Documentation

◆ Acao()

const char * CJogoDoGalo::Acao ( TProcuraConstrutiva * sucessor )

Definition at line 83 of file JogoDoGalo.cpp.

◆ Codifica()

void CJogoDoGalo::Codifica ( uint64_t estado[OBJETO_HASHTABLE] )

virtual

Codifica o estado para um vetor de inteiros de 64 bits.

Note: Redefinição opcional. Necessário para identificação de estados repetidos por hashtable.

As variáveis de estado devem ser compactadas no vetor de inteiros de 64 bits. Todos os estados codificados têm de ser distintos de 0. Estados distintos, têm de ficar com codificações distintas.

Em diversos problemas, um mesmo estado pode ter múltiplas representações equivalentes. Por exemplo, se um conjunto de inteiros for um estado, este pode ser representado em vetor. No entanto a ordem é irrelevante, dado que é um conjunto. Assim não faz sentido guardar vários estados que sejam representações do mesmo estado. Há que normalizar o estado antes de o guardar, de modo a que seja dado como estado repetido, se uma das duas formas já tiver sido gerada. O exemplo do conjunto de inteiros, a normalização pode ser a ordenação do vetor, constituindo assim um estado único entre todas as formas que o conjunto pode ser representado em vetor. Problemas de tabuleiro, há simetrias que podem gerar várias versões da mesma posição.

Note: Se a verificação de estados repetidos for baseada em hashtables, a superclasse chama este método dentro de Sucessores().; Para otimizar o consumo de memória, são utilizadas hashtables com perdas. Se necessário pode alterar o tamanho da hashtable editando a macro TAMANHO_HASHTABLE; a variável tamanhoCodificado tem de ter o número de variáveis de 64 bits utilizadas, garantindo que o vetor estado[] não é acedido na posição tamanhoCodificado ou superior.

See also: SolucaoVazia()

void CSubProblema::Codifica(uint64_t estado[OBJETO_HASHTABLE])
{
    Vector<int> vetor; // assumindo neste exemplo que o estado é um vetor de inteiros pequenos
    Normalizar(vetor); // o vetor tem várias formas, e agora é normalizado por uma função de CSubProblema
    TProcuraConstrutiva::Codifica(estado); // chamar a superclasse após normalizar o estado
    // codificar números de 4 bits, assumindo que os inteiros pequenos cabem em 4 bits
    for (int i = 0, index = 0; i < vetor.Count(); i++, index += 4)
        estado[index >> 6] |= (uint64_t)vetor[i] << (index & 63);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 153 of file JogoDoGalo.cpp.

Here is the call graph for this function:

◆ Copiar()

void CJogoDoGalo::Copiar ( TProcuraConstrutiva * objecto )

Definition at line 22 of file JogoDoGalo.cpp.

Here is the caller graph for this function:

◆ Debug()

void CJogoDoGalo::Debug ( void )

virtual

Mostra o estado no ecrã, para debug.

Note: Redefinição opcional. Necessário para visualizar a procura, e explorar o espaço manualmente.

Esta função deverá mostrar claramente o estado atual, em texto mas da forma mais confortável possível. O formato texto destina-se principalmente a quem implementa o problema, e não utilizadores finais. É importante poder explorar o espaço de estados, para verificar a correta implementação dos sucessores, como também possa ver a árvore de procura dos algoritmos, para árvores pequenas, e assim detectar bugs.

Note: Antes de cada linha, chame a função NovaLinha(). Dependendo do contexto, NovaLinha() pode imprimir caracteres que representam os ramos da árvore de procura, criando uma visualização textual que simula a estrutura da procura.; A exibição do estado pode variar conforme o nível de debug definido em parametro[nivelDebug].valor. Um nível menor pode mostrar informações mais sucintas, enquanto um nível maior pode detalhar todas as variáveis do estado.

See also: NovaLinha()

void CSubProblema::Debug(void)
{
       NovaLinha();
    // neste exemplo o estado é apenas um número
    if(parametro[nivelDebug].valor <= atividade)
           printf("--<([%d])>--", variavel); // versão compacta do estado
    else {
        // versão mais elaborada do estado
    }
}

Reimplemented from TProcuraConstrutiva.

Definition at line 99 of file JogoDoGalo.cpp.

Here is the call graph for this function:

◆ Duplicar()

TProcuraConstrutiva * CJogoDoGalo::Duplicar ( void )

virtual

Cria um objecto que é uma cópia deste.

Note: Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a criar uma cópia do mesmo tipo. O código da subclasse geralmente segue um padrão e pode utilizar o modelo abaixo, aproveitando o método Copiar(). É especialmente útil na função de Sucessores(), na geração de um novo estado.

Returns: Retorna o novo estado, acabado de gerar.

Note: Caso exista falha de memória, colocar a variável memoriaEsgotada a true, para tentativa de terminar a execução de forma graciosa.

TNo CSubClasse::Duplicar(void)
{
    CSubClasse* clone = new CSubClasse;
       if(clone!=NULL)
           clone->Copiar(this);
       else
            memoriaEsgotada = true;
       return clone;
}

Implements TProcuraConstrutiva.

Definition at line 12 of file JogoDoGalo.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Heuristica()

int CJogoDoGalo::Heuristica ( void )

virtual

Função para calcular quanto falta para o final, o valor da heurística.

Note: Redefinição opcional. Necessário para utilizar os algoritmos informados.

Returns: Retorna a melhor estimativa, sem ultrapassar a real, do custo do estado atual até ao objetivo.

A função heurística é crítica para utilizar os algoritmos informados. Deve devolver uma estimativa sem ultrapassar o custo real, do custo que falta para atingir o estado objetivo mais próximo do estado atual. Se a estimativa não ultrapassar o custo real, a heurística será admissível. No entanto, em alguns casos, heurísticas não admissíveis podem ser utilizadas, podendo acelerar a procura, mesmo que ocasionalmente levem a resultados subótimos.

No final, chame a função heurística da superclasse para atualizar as estatísticas e o número de avaliações. Se estiver configurado, esse processo também pode introduzir ruído na heurística, o que pode impactar certos algoritmos de procura.

Esta função pretende-se rápida, e o mais próxima possível do valor real, sem ultrapassar.

Note: Num problema, existindo alternativas, umas mais rápidas menos precisas, outras mais lentas mais precisas, é aconselhada a criação de um ou mais parametros para que a heurística possa ser calculada de acordo com o parametro definido. Em fase de testes logo se averigua qual a versão que adiciona mais vantagem à procura.; Uma heurística pode resultar de um relaxamento do problema. Verifique se o problema sem uma das restrições (fazendo batota), se consegue resolver mais facilmente. Utilize como heurística o custo de resolver o problema sem essa restrição.

void CSubProblema::Heuristica(void)
{
    heuristica = 0; // ponto de partida, há 0 de custo
    // utilizar neste exemplo a distância até 1000, local onde estará o objetivo
    heuristica = abs(variavel - 1000);  
    // chamar a função heurística da superclass
    return TProcuraConstrutiva::Heuristica();
}

Reimplemented from TProcuraConstrutiva.

Definition at line 124 of file JogoDoGalo.cpp.

Here is the call graph for this function:

◆ SolucaoCompleta()

bool CJogoDoGalo::SolucaoCompleta ( void )

virtual

Verifica se o estado actual é objectivo (é uma solução completa)

Note: Obrigatória a redefinição.

Returns: Retorna verdadeiro se é um estado objetivo, ou falso caso contrário.

Este método verifica se o estado atual é objetivo, e portanto temos uma solução completa. A complexidade da verificação depende do problema, podendo ser um teste simples ou envolver múltiplas condições.

Note: Este método será chamado pelos algoritmos de procura no momento adequado, não necessariamente na geração de sucessores. Por isso, deve ser implementado separadamente de Sucessores(), garantindo que a avaliação do objetivo seja feita apenas quando necessário.

bool CSubProblema::SolucaoCompleta(void) {
    // pode ser um simples teste, ou algo mais complexo, dependente do problema
    // verificar se as condições pretendidas estão satisfeitas
    return variavel > 1000;
}

Reimplemented from TProcuraConstrutiva.

Definition at line 54 of file JogoDoGalo.cpp.

Here is the caller graph for this function:

◆ SolucaoVazia()

void CJogoDoGalo::SolucaoVazia ( void )

virtual

Coloca o objecto no estado inicial da procura.

Note: Obrigatória a redefinição.

Este método inicializa as variáveis de estado no estado inicial vazio. Representa o estado inicial antes de qualquer ação ser realizada na procura. Caso existam dados de instância, deve neste método carregar a instância. A primeira instrução deverá chamar o método da superclasse, conforme modelo em baixo.

Note: A variável instancia.valor, tem o ID da instância que deve ser carregada.; Se a função Codifica() estiver implementada, o tamanho do estado codificado deve ser determinado após o carregamento da instância, pois diferentes instâncias podem exigir tamanhos distintos.

See also: Codifica()

void CSubProblema::SolucaoVazia(void)
{
    TProcuraConstrutiva::SolucaoVazia();
       // acertar as variáveis estáticas, com a instância (ID: instancia.valor)
       CarregaInstancia(); // exemplo de método em CSubProblema para carregar uma instância
    // inicializar todas as variáveis de estado
       variavel = 0;
    // Determinar o tamanho máximo do estado codificado, se aplicável
       tamanhoCodificado = 1;
}

Reimplemented from TProcuraConstrutiva.

Definition at line 28 of file JogoDoGalo.cpp.

Here is the call graph for this function:

◆ Sucessores()

void CJogoDoGalo::Sucessores ( TVector< TNo > & sucessores )

virtual

Coloca em sucessores a lista de estados sucessores.

Note: Obrigatória a redefinição.

Parameters

sucessores - variável com a lista de estados sucessores a retornar.

Este é o método principal, que define a árvore de procura. Para o estado atual, duplicar o estado por cada ação / estado que seja sucessor. Alterar as variáveis de estado para corresponderem à ação efetuada no estado sucessor. Caso o custo não seja unitário, definir o custo da ação. Chamar o método da superclasse no final, já que irá atualizar estatísticas, bem como eliminar estados que sejam repetidos, dependendo da parametrização.

Note: O custo da ação deve ser definido aqui, mas ao chamar Sucessores() da superclasse, ele será acumulado para representar o custo total desde o estado inicial.; O método Duplicar() já coloca as variáveis de estado iguais ao estado atual. Apenas modifique as variáveis de estado que precisam refletir a ação i.; Caso seja feita uma verificação e a ação afinal não é válida, apagar o estado.; Não é preciso considerar estados repetidos, a verificação será feita na superclasse.

void CSubProblema::Sucessores(TVector<TNo>&sucessores)
{
    CSubProblema* novo;
    for(int i = 0; i < numeroAcoes; i++) {
        sucessores.Add(novo = (CSubProblema*)Duplicar());
        // aplicar a ação i nas variáveis de estado
        novo->variavel = i;
           // se o custo não for unitário, indicar o custo da ação
        novo->custo = 1 + i / 10;
        // Caso o estado gerado não seja válido, remova-o da lista e liberte a memória:
        if (!novo->EstadoValido()) // exemplo de método em CSubProblema para verificar a validade
            delete sucessores.Pop();
       }
    TProcuraConstrutiva::Sucessores(sucessores);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 38 of file JogoDoGalo.cpp.

Here is the call graph for this function:

◆ TesteManual()

void CJogoDoGalo::TesteManual ( const char * nome )

virtual

Inicializa a interação com o utilizador.

Note: Redefinição necessária para definir as instancias existentes.

Esta função arranca com o teste manual, orientada para o programador. A interface permite:

visualizar e trocar de instância
explorar o espaço de estados nessa instancia, executando ações
ver um caminho que esteja gravado (por exploração manual ou por execução de um algoritmo)
ver e editar qualquer parametro de execução
o algoritmo é também um parametro, podendo naturalmente ser alterado
há parametros sobre limites de execução, informação de debug, opções de implementação e opções de algoritmos
executar o algoritmo com a configuração atual
adicionar a configuração atual a um conjunto de configurações de teste
executar um teste empírico, executando todas as configurações de teste, no conjunto de instâncias selecionadas

Esta função deve ser redefinida para inicializar a variável com informação dos IDs das instâncias disponíveis. Essa variável é do tipo TParametro, mas não está na lista de parametros, devendo ser inicializada aqui.

Note: A instância selecionada irá ser carregada em SolucaoVazia(), utilizando o valor atual.; Esta função deve ser o ponto de entrada, a executar no main.

See also: TParametro

void CSubProblema::TesteManual(const char* nome)
{
    // indicar que há 10 instâncias, sendo a instância inicial a 1
       instancia = { "Problema", 1,1,10, "Características dos problemas", NULL };
       TProcuraConstrutiva::TesteManual(nome);
}
 
// exemplo do main
int main()
{
    CSubProblema problema;
    problema.TesteManual("CSubProblema");
}

Reimplemented from TProcuraConstrutiva.

Definition at line 118 of file JogoDoGalo.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ tabuleiro

TVector<char> CJogoDoGalo::tabuleiro

Definition at line 22 of file JogoDoGalo.h.

The documentation for this class was generated from the following files:

Teste/JogoDoGalo.h
Teste/JogoDoGalo.cpp

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CJogoDoGalo()

◆ ~CJogoDoGalo()

Member Function Documentation

◆ Acao()

◆ Codifica()

◆ Copiar()

◆ Debug()

◆ Duplicar()

◆ Heuristica()

◆ SolucaoCompleta()

◆ SolucaoVazia()

◆ Sucessores()

◆ TesteManual()

Member Data Documentation

◆ tabuleiro