RNA quantification and purity

A partir da análise conceitual exposta neste capítulo, pode-se observar que identi- ficar o algoritmo que se destaca em comparação ao outro é uma tarefa bastante complexa, pois o fato de cada um deles (YBWC e APHID) ser baseado em uma abordagem distinta (síncrona e assíncrona) faz com que ambos possuem aspectos positivos que se sobressaem em relação ao outro. De modo a sintetizar e agrupar todas as informações expostas neste capítulo, a Tabela3e a Tabela4apresentam os principais pontos positivos e negativos le- vantados, respectivamente, do algoritmo YBWC. Da mesma forma, a Tabela5e a Tabela

6 mostram os pontos fortes e fragilidades, respectivamente, do algoritmo APHID. Pontos Positivos do YBWC

Comunicação entre os Processadores

- Permite que os processadores trabalhem com as informações mais atualizadas.

- Redução da sobrecarga de busca.

Sincronização de Tarefas

- A busca é aprimorada caso os nós mais à esquerda (irmãos mais velhos) gerem uma poda ou um estreitamento na janela de busca.

- Tarefas menos complexas podem ser efetuadas localmente.

Janela de Busca Alfa-Beta

- Semelhança com a atualização de janelas do algoritmo serial Alfa-Beta.

- Redução da sobrecarga de busca.

Tabela de Transposição - Sem pontos positivos com relação ao desempenho

do algoritmo utilizando TT distribuída.

Portabilidade - Sem pontos positivos.

Tabela 3 – Pontos positivos do algoritmo YBWC Pontos Negativos do YBWC Comunicação entre os Processadores - Grande volume de troca de mensagens.

- Aumento da sobrecarga de comunicação.

Sincronização de Tarefas

- Diversos pontos globais de sincronização ao longo dos ramos mais à esquerda da árvore de busca. - Aumento da sobrecarga de sincronização. - Causa períodos de ociosidade dos processadores.

Janela de Busca Alfa-Beta

- Necessidade de constante troca de mensagens entre os processadores.

- Aumento da sobrecarga de comunicação

Tabela de Transposição

- Possui desempenho melhor com TT global com relação a TT local.

- A estratégia de busca por ID agrava a utilização de TT local.

Portabilidade

- Grande esforço de engenharia de software. - Requer conhecimento por parte do programador com relação ao mecanismo de troca de mensagens.

Capítulo 5. Comparação entre os algoritmos YBWC e APHID 55

Pontos Positivos do APHID Comunicação entre os Processadores

- Baixo volume de troca de mensagens.

- Comunicação é realizada através da Tabela Aphid. - Redução da sobrecarga de comunicação.

Sincronização de Tarefas

- Pontos globais de sincronização são fixos em uma profundidade pré-estabelecida.

- Redução dos períodos de ociosidade dos processadores. - Redução da sobrecarga de sincronização.

Janela de Busca Alfa-Beta - Redução da sobrecarga de comunicação.

Tabela de Transposição

- Possui melhor desempenho com TT distribuída.

- Atribuição dos nós aos mesmos processadores é realizada sempre que possível durante todo o processo de busca.

Portabilidade - Projetado para ser facilmente integrado a aplicações existentes.

Tabela 5 – Pontos positivos do algoritmo APHID Pontos Negativos do APHID Comunicação entre os Processadores - Sem pontos negativos.

Sincronização de Tarefas - Há uma relativa exploração desnecessária de nós.

- Aumento da sobrecarga de busca.

Janela de Busca Alfa-Beta

- Cada processador trabalha com uma janela diferente. - Possibilidade de explorar nós não relevantes para a busca. - Aumento da sobrecarga de busca.

Tabela de Transposição Distribuída - Pequena possibilidade de nós serem designados a processadores

distintos durante as iterações de busca.

Portabilidade - Desafio de se criar uma biblioteca para o algoritmo.

Tabela 6 – Pontos negativos do algoritmo APHID

Assim sendo, a partir das tabelas acima, é possível extrair os melhores aspectos positivos encontrados nos algoritmos YBWC e APHID. Pode-se observar que a principal vantagem do algoritmo YBWC é com relação à atualização da janela de busca alfa-beta, uma vez que o mecanismo utilizado neste algoritmo procura se assemelhar ao método utilizado no algoritmo serial Alfa-Beta. Tal fato contribui significativamente para que o retorno do YBWC seja igual ou parecido com o do algoritmo serial, além de evitar, ao máximo, que seja realizada a avaliação de nós desnecessários para a avaliação da busca. Quanto ao algoritmo APHID, é possível destacar diversos pontos positivos, dentre eles: a sua natureza assíncrona, a qual permite que os processadores realizem buscas simultanea- mente sem depender dos resultados de outros processadores, evitando longos períodos de ociosidade; o baixo volume de troca de mensagens, uma vez que os processadores se co- municam entre si por meio da estrutura Tabela Aphid, ao invés da rede de interconexão, o que reduz substancialmente o impacto da sobrecarga de comunicação; ótimo desempenho atuando com TT local. Ressalta-se que estas características destacadas foram considera- das para a construção de um novo algoritmo assíncrono de busca denominado ADABA, no escopo global no qual o presente trabalho está alocado.

Capítulo 6. Método Automatizado para Avaliação de Qualidade de Movimentos de Agentes Jogadores

de Damas 57

têm de ser a mesma para ambos os jogadores envolvidos. Convém salientar que tal estratégia é fundamental para a acuidade do cálculo da qualidade de movimentos, uma vez que em Damas (como em vários outros problemas práticos) o desempenho do agente é extremamente dependente do estado inicial do qual partiu. Tal fator é tão significativo que, tal como citado na seção 4.1.1, a garantia de invencibilidade do Chinook somente ocorre em jogos que partem do tabuleiro inicial padrão do jogo de Damas (SCHAEFFER et al., 2007). Ainda com relação aos jogos-teste, é im- portante ressaltar que, neles, o agente pode enfrentar qualquer adversário, inclusive ele mesmo (situação a que se denomina jogos por self-play). Assim sendo, caso os jogos-teste envolvam dois adversários A (jogador preto) e B (jogador branco) dis- tintos, os arquivos PDN gerados pelo módulo armazenarão, tanto os conjuntos de movimentos executados pelos jogador A (jogando com as peças pretas), quanto os conjuntos executados pelo competidor B (jogando com as peças brancas). Por outro lado, caso os jogos-teste ocorram por self-play, os conjuntos armazenados nos arqui- vos PDN se referirão aos movimentos executados pelo único jogador envolvido na competição jogando, ora com as peças pretas, ora com as peças brancas. Uma vez gerados todos os arquivos PDN correspondentes a todos os jogos-teste do torneio, o módulo AAAA produz uma pasta contendo todos eles.

Módulo FAQM: Este componente tem duas finalidades básicas: 1) Gerar um conjunto

de informações relacionadas ao comportamento que o agente Cake teria tido diante das várias situações (estados de tabuleiro) enfrentadas pelos agentes durante os jogos-teste; 2) Gerar as taxas de coincidência entre os movimentos executados pelos agentes nos jogos-teste (armazenados no arquivo PDN) e os movimentos que teriam sido executados pelo Cake nas mesmas situações. A primeira finalidade é executada no sub-módulo do FAQM denominado Análise Automática do Cake (AAC), ao passo que a segunda é cumprida no sub-módulo denominado Estatística de Coincidência de Movimentos (ECM). Tais sub-módulos serão descritos com mais detalhes nas seções 6.2 e 6.3, respectivamente.