public:t-622-arti-11-1:final_project
Differences
This shows you the differences between two versions of the page.
| public:t-622-arti-11-1:final_project [2011/04/22 23:56] – angelo | public:t-622-arti-11-1:final_project [2024/04/29 13:33] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 7: | Line 7: | ||
| border-width: | border-width: | ||
| border-spacing: | border-spacing: | ||
| - | border-style: | + | border-style: |
| border-color: | border-color: | ||
| border-collapse: | border-collapse: | ||
| Line 15: | Line 15: | ||
| border-width: | border-width: | ||
| padding: 4px; | padding: 4px; | ||
| - | border-style: | + | border-style: |
| border-color: | border-color: | ||
| background-color: | background-color: | ||
| Line 23: | Line 23: | ||
| border-width: | border-width: | ||
| padding: 4px; | padding: 4px; | ||
| - | border-style: | + | border-style: |
| border-color: | border-color: | ||
| background-color: | background-color: | ||
| Line 167: | Line 167: | ||
| </td> | </td> | ||
| <td> | <td> | ||
| - | < | + | < |
| <br> | <br> | ||
| < | < | ||
| Line 443: | Line 443: | ||
| </td> | </td> | ||
| <td> | <td> | ||
| - | < | + | < |
| <br> | <br> | ||
| < | < | ||
| Line 523: | Line 523: | ||
| <td align=" | <td align=" | ||
| <a href=" | <a href=" | ||
| - | <img src=" | + | <img src=" |
| </a> | </a> | ||
| </td> | </td> | ||
| <td> | <td> | ||
| - | < | + | < |
| <br> | <br> | ||
| < | < | ||
| Line 582: | Line 582: | ||
| <br> | <br> | ||
| <span onclick=" | <span onclick=" | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr valign=" | ||
| + | <td align=" | ||
| + | <img src=" | ||
| + | </td> | ||
| + | <td> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | I wanted to make a game playing agent for 9-men Morris game. And the game environment as well. For this project i looked into search algorithms and heuristics. | ||
| + | <div id=" | ||
| + | <p> | ||
| + | I'm using a modified version of A* algorithm, but i came up with the implementation. I found someone who had already made Nine-Men' | ||
| + | </p> | ||
| + | <p> | ||
| + | | ||
| + | </p> | ||
| + | <p> | ||
| + | The game is essentially split into three parts. | ||
| + | The player has to choose coordinates to place their piece on, if he gets a mill he has to choose which of the other players pieces he removes. And he also has to move his own pieces. | ||
| + | There are 4 things i took into consideration: | ||
| + | <ol> | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | </ol> | ||
| + | <br> | ||
| + | So the player tries to maximize the forming of mills and mobility and minimize forming of enemy mills. | ||
| + | </p> | ||
| + | <p> | ||
| + | It feels like you're playing against someone so i feel i have achieved to create a player that reacts correctly in basic circumstances, | ||
| + | I'm happy with the resulting program but i would have liked to look at even more ways ways of doing this, for instance using machine learning to train a system to play the game. Or looking at more search algorithms. | ||
| + | </p> | ||
| + | </ | ||
| + | <br> | ||
| + | <span onclick=" | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr valign=" | ||
| + | <td align=" | ||
| + | <img src=" | ||
| + | </td> | ||
| + | <td> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | The Ascr project itself is a console application in C++, below is a screenshot of the default | ||
| + | execution process with some additional paint strokes for " | ||
| + | <div id=" | ||
| + | <p> | ||
| + | The default execution consists of the following operations: | ||
| + | <ul> | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | probability of executable code being present; | ||
| + | < | ||
| + | < | ||
| + | Attempt to match those patterns in the process memory. | ||
| + | </ul> | ||
| + | </p> | ||
| + | <p> | ||
| + | We distinguish between two different approaches to binary analysis, based on whether we | ||
| + | are dealing with programs as a sequence of instructions stored in a physical file or as a process | ||
| + | containing those instructions along with any runtime information required. For physical files, the | ||
| + | approach is denoted as static analysis, and dynamic analysis for process analysis. In both cases, we | ||
| + | are interested in determining the functionality of the binary through some form of analysis. In this | ||
| + | project we tried to determine the functionality of Windows processes that originated from PE files | ||
| + | (Portable Executables). | ||
| + | </p> | ||
| + | <p> | ||
| + | Originally my approach was to focus solely on information available during runtime of the | ||
| + | process, however, as it turns out that method is sub optimal since the volume of data retrieved | ||
| + | expands too rapidly. | ||
| + | </p> | ||
| + | <p> | ||
| + | There is plenty of research material available on the topic of binary analysis, the following | ||
| + | are the relevant ones to this project: | ||
| + | <ol> | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | </ol> | ||
| + | </p> | ||
| + | <p> | ||
| + | The Ascr initially was built around the Debug API from Microsoft and has a functional | ||
| + | debugger interface within the project file. A debugger is not a functional analyzer on its own, so it | ||
| + | became apparent that references from the original PE file were needed. At that point, I focused | ||
| + | my efforts on writing a parser for PE executables, | ||
| + | The main result is a conjecture which appears to hold for the simple training executable. It | ||
| + | can be explained a bit formally as follows: | ||
| + | Let sj be a sequence of instructions, | ||
| + | the variance of sj for all j's, ν = [0 … 1]. The variance is a measurement to the stability of the | ||
| + | sequence sj in terms of the path through sj during runtime execution. | ||
| + | A sequence sn has ν = 0, iff for all oi ϵ sn, we can predict the exact path through sn and the | ||
| + | state of Prt at all times. A trivial example would be a nop sled or no-operations: | ||
| + | snop = { 0x90, 0x90, … , 0x90 } <=> Prt = { i+1, i+2, …, i+n }, ν(snop) = 0. | ||
| + | For all “first generation” sequences with ν = 0, we can map them directly to a set Ppe' = { D1, | ||
| + | D2, … , Dn }, where Di is a higher-level representation of that sequence. For other sequences with ν | ||
| + | > 0, we apply the following algorithm: | ||
| + | <br> | ||
| + | Let sk be a sequence where ν(sk) > 0 and |sk| > α, α is the largest single instruction. Then we | ||
| + | have an index Δ, such that sk = { o1, o2, … , oΔ , … , on } => s'k = { o1, o2, … , oΔ } and ν(s' | ||
| + | s'' | ||
| + | the functionality of s'' | ||
| + | see if we can reiterate this procedure on s'' | ||
| + | pattern. Since we are not emulating s'' | ||
| + | different sets, A and B. A contains the patterns for which ν = 0 and B the patterns for which | ||
| + | ν > 0. The set B is the source of all the variance in Ppe. By isolating that set, we can focus | ||
| + | the Ascr runtime analysis on those patterns, since by our conjecture, we can already | ||
| + | resolve for A. | ||
| + | Essentially, | ||
| + | accomplish through knowledge based engineering of the data gathered when executing the | ||
| + | patterns of B. However, I did not have enough time to see it happen. | ||
| + | </p> | ||
| + | </ | ||
| + | <br> | ||
| + | <span onclick=" | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr valign=" | ||
| + | <td align=" | ||
| + | <img src=" | ||
| + | </td> | ||
| + | <td> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | < | ||
| + | <br> | ||
| + | We want to try using STRIPS-like operators to make descriptive bids for a given bridge hand and bid history. | ||
| + | <div id=" | ||
| + | <p> | ||
| + | To our knowledge this is a fresh approach to the problem. | ||
| + | </p> | ||
| + | <p> | ||
| + | We managed to implement lazy-evaluation to structure bidding conventions. | ||
| + | </p> | ||
| + | <p> | ||
| + | We realized that we should modify the robot to pass the hand *and the bid history* to the convention card functions for evaluation but lacked time to implement such deep surgery. | ||
| + | </p> | ||
| + | </ | ||
| + | <br> | ||
| + | <span onclick=" | ||
| </td> | </td> | ||
| </ | </ | ||
/var/www/cadia.ru.is/wiki/data/attic/public/t-622-arti-11-1/final_project.1303516613.txt.gz · Last modified: 2024/04/29 13:32 (external edit)