El proyecto Cadenas de Markov: Computer Chess, reúne nociones de teoría del lenguaje y procesos estocásticos discretos de primer orden.

ETC: 15 horas (fecha límite - 5 clases)

2-3 estudiantes por equipo

Tómese su tiempo tanto en la calidad como en el contenido.

El profesor asociado y los profesores asistentes no responderán preguntas sobre el proyecto.

ESCALA: 40 puntos

  1. 10 puntos
  2. 15 puntos
  3. 15 puntos

The Markov Chains Project: Computer Chess, reúne nociones de teoría del lenguaje y procesos estocásticos discretos de orden uno.

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

“Camarógrafo: ¿Crees que un ser humano alguna vez vencerá a una persona en el ajedrez? John: Oh ... ¿entre un ser humano y una persona? Mi dinero está en la computadora ".

Parte 1: datos legibles y comprensibles

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

" PARA computadora una vez me golpeó en ajedrez, pero no fue rival para mí en el kick boxing. "

El desafío es alto, el torneo anual mundial de ajedrez para desafiar a los primeros científicos de la computación: crear un programa capaz de vencer a un humano en el ajedrez. Esta es la primera vez y debe mostrarle al mundo el potencial de la TI.

Para familiarizarse con las reglas del ajedrez, puede ver en un bucle los viejos torneos de Mikhail Tal, Bobby Fisher y Anatoly Karpov, así como el prometedor debut del joven y formidable Garry Kasparov.

Los posibles movimientos (en términos de movimiento, no de posición) se registran como símbolos del alfabeto. Una serie de movimientos de toma de decisiones significa que a partir de una configuración favorable dada, existe al menos una estrategia que permite llegar con seguridad a una posición favorable de jaque mate.

Por lo tanto, la computadora construirá árboles de decisión para configuraciones favorables (como en el proyecto 1). Tomemos, por ejemplo, las siguientes palabras para una configuración favorable A:

  • abbaaccad
  • baacdaadd
  • abaacdddd

Para reducir el árbol vamos a utilizar otra técnica distinta a la del tema 1. En el primer paso, asignarás además del símbolo, el número de veces que ha pasado el arco. Inicialmente, este número es igual a 1 para cada arco.

El segundo paso consiste en calcular el coeficiente de compatibilidad entre dos estados. En nuestro ejemplo, fusionaremos dos estados si son compatibles con 100%. Dos estados son compatibles con 100% si tienen los mismos símbolos predecesores y sucesores. Por ejemplo, en los prefijos abba y baab, el binomio ab o ba son compatibles con 100%. Durante la fusión, también es necesario fusionar el número de pasajes a través de los arcos (por lo que aquí sumamos 1 + 1).

El tercer paso es fusionar estados 50% compatibles, es decir, solo con los mismos sucesores o solo con los mismos predecesores. Por lo tanto, es posible hacer converger los estados finales en un solo estado final, ya que todos los estados finales tienen los mismos sucesores (aquí el conjunto vacío).

El cuarto y último paso se utiliza para fabricar la cadena de Markov en el tiempo discreto asociado. Para cada estado, la probabilidad de los arcos de entrada (resp. Salida) es igual al número de pasajes de este arco dividido por la suma de los números de entrada (o salida, este número es el mismo).

Clasificación

  1. Etapa 1 (2 puntos)
  2. 2do paso (3 puntos)
  3. Paso 3: no converja en todos los casos posibles, al menos dos de los cuales el estado final (3 puntos)
  4. Paso 4 (2 puntos)

Parte 2: Estudio de la conducta

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

Beuscher: ¿Hay alguna posibilidad de que esto sea uh ... algún tipo de uh ... muy avanzado ... quiero decir, acabamos de entregar una reina para obtener su reina y ahora estamos básicamente ... um ... "

Ahora que tiene autómatas estocásticos (una deliciosa mezcla de autómatas y cadena de markov), es hora de estudiar su comportamiento, es decir, el estudio de la cadena de Markov asociada. Recuerda analizar cuidadosamente los estados finales (jaque mate).

Estudie el comportamiento de las siguientes dos cadenas de Markov en tiempo discreto:

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

El estado 6 es un estado final.

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

Los estados absorbentes son las configuraciones de "jaque mate". El estado s0 es el estado inicial, por lo que el vector inicial comienza solo con este estado.

Clasificación

  1. Canal 1 (7 puntos)
  2. Canal 2 (8 puntos)

Parte 3: Reducción y predicción de autómatas

Proyecto de cadenas de Markov: Proyecto de cadenas de Markov de ajedrez informático

"El ajedrez es la lucha contra el error". - Johannes zukertort

Ahora que su sistema de aprendizaje automático está en funcionamiento, es hora de pensar en la parte técnica. Su computadora tiene dos núcleos y, por lo tanto, es posible realizar computación paralela. Entonces surge el problema del Bus, ¿necesita uno o dos Buses para enrutar la información a los procesadores? Sabiendo que la información siempre llega de acuerdo a un proceso de envenenamiento de tasa λ y que son atendidos con un proceso de Poisson de tasa similar, calcular la distribución estacionaria, la ocupación de los procesadores, el número de mensajes perdidos así como el tiempo promedio de espera antes de ser atendidos para ambas configuraciones.

Clasificación

  1. Modelado de las dos configuraciones (5 puntos)
  2. Análisis de la primera configuración (5 puntos)
  3. Análisis de la segunda configuración (5 puntos)