# First Grade Euler Project

15 May 2017My two friends in our group and I have finished a final course project: First-Grade Euler. The OCR tech is powered by ABBYY.

My two friends in our group and I have finished a final course project: First-Grade Euler. The OCR tech is powered by ABBYY.

Ordinary programming | Logic programming |
---|---|

Identify problem | Identify problem |

Assemble information | Assemble information |

Figure out solution | coffee break :) |

Encode solution | Encode info in KB |

Encode problem instance as data | Encode problem instance as data |

Apply program to data | Ask queries |

Wow, logic programming is really amazing.

But, reality is reality. The following process is:

Ordinary programming | Logic programming |
---|---|

… | … |

Apply program to data | Ask queries |

Start the program | Start the program |

Program finished | Running |

Graduate | Running |

Global travel | Running |

There are two important ordering methods for solving CSP problems using backtracking search:

- Minimum Remaining Values (MRV)
- Least Constraining Value (LCV)

The former is for ordering variables. It tells us that it’s better to consider the variables with minimum remaining values, so it’s also known as the most constrained variables method. The latter is for ordering values. After we decided to consider one variable, there are many values to consider. It tells us that it’s better to consider the least constraining value firstly.

Most of the people believe that MRV leads the searching fail-fast, and LCV leads the searching succeed-fast. Choose the fail-fast variable but choose the succeed-fast value. Choose the most constrained variable but choose the least constraining value. It seems that the two ordering methods are not consistent, right?

Actually, this question confuses me a lot. After struggling hard, I believe the truth is in my mind now. Both methods want the searching end-fast. MRV leads the searching not only fail-fast but also succeed-fast. LCV leads the searching succeed-fast, but not fail-fast. When considering to choose variables, choosing the most constrained variable makes the searching tree thin, so it leads the searching end-fast. When considering to choose values, there are two cases. Suppose that we have $n$ values to consider, that means we have $n$ sub searching trees currently. If all the $n$ sub searching trees fail in the end, then it’s no matter how we order the values. If one of the sub searching trees succeeds, it’s better to consider this succeeding sub searching tree. We believe the least constraining value has the most probability to succeed, so we consider the least constraining value firstly, and so this leads succeed-fast.

After fighting for an hour, our little Ghost killed the eval Pacman. :P

Actually, it’s a task in UCB CS188 course Pacman project. In this task, we write a method controlling the pacman to earn more scores. The method in the above screencast is a depth-3 expectimax search with a tricky evaluation function. It’s hard for me to get more scores.

The following $\alpha \beta$ pruning algorithm looks clever, however, it has a tricky bug. Can you find where the bug is?

```
def alpha_beta(state, alpha, beta):
if state.finished():
return state.calcScore()
for next_state in state.next():
alpha = max(alpha, -alpha_beta(next_state, -beta, -alpha))
if alpha >= beta:
break
return alpha
```

Tips: This code is able to find the correct solution, but may be more time-consuming.

Older
Newer