{"id":768,"date":"2009-03-04T20:43:53","date_gmt":"2009-03-04T11:13:53","guid":{"rendered":"http:\/\/nexfinity.net\/?p=81"},"modified":"2014-06-23T17:08:40","modified_gmt":"2014-06-23T17:08:40","slug":"draughts-ai-my-approach","status":"publish","type":"post","link":"https:\/\/cjohnson.id.au\/game-dev\/draughts-ai-my-approach\/","title":{"rendered":"Draughts AI – My Approach"},"content":{"rendered":"

I am happy to say that I have finished programming my Draughts game. If you have been following my Twitter<\/a> then you may have noticed that there is one thing holding me back from releasing it, memory leaks. I personally expected to have a few since I haven’t had a great deal of experience writing more sophisticated applications in C\/C++. I got around to checking these leaks the day before I was heading back to University for the semester so I haven’t been able to address all of them yet but plan to soon. For the mean time I would like to discuss the AI that I have used in this game.<\/p>\n

One of the fundamental concepts behind AI is the Turing Test as discussed in Alan Turing’s<\/a> 1950 paper “Computing Machinery and Intelligence<\/a>“.<\/p>\n

\n

A human judge engages in a natural language conversation with one human and one machine, each of which tries to appear human. All participants are placed in isolated locations. If the judge cannot reliably tell the machine from the human, the machine is said to have passed the test. In order to test the machine’s intelligence rather than its ability to render words into audio, the conversation is limited to a text-only channel such as a computer keyboard and screen.<\/p>\n<\/blockquote>\n

With this in mind I decided to brainstorm several things that would cause my game to fail this Turing Test. The first notable thing is moving a piece into a position in which the opponent can jump that piece when there are other more advantageous positions on the board. The second is if the computer player doesn’t take the obvious jumps and double jumps. To put these into play I decided to assign a priority to all of the possible moves that a computer opponent could take. Any moves which resulted in capturing an opponents piece would would receive an increase in priority and any moves that resulted in being captured by the human player resulted in a decrease in priority. The computer would then take a random move out of the list of moves with the highest priority.<\/p>\n

The system described above is the crux of the AI. Overall effect works really well towards the start of the game but sort of falls apart as the pieces become scattered across the board since the AI moves pieces at random. I’d like to think that the aggressiveness of the computer early on makes its flaws less apparent towards the end but this not always the case.<\/p>\n\n

Thanks for reading. Hopefully towards the end of this week you should be seeing the source code of Draughts here. For now enjoy some of these screen shots.<\/p>\n","protected":false},"excerpt":{"rendered":"

I am happy to say that I have finished programming my Draughts game. If you have been following my Twitter then you may have noticed that there is one thing holding me back from releasing it, memory leaks. I personally expected to have a few since I haven’t had a great deal of experience writing […]<\/p>\n<\/a>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/posts\/768"}],"collection":[{"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/comments?post=768"}],"version-history":[{"count":1,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/posts\/768\/revisions"}],"predecessor-version":[{"id":970,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/posts\/768\/revisions\/970"}],"wp:attachment":[{"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/media?parent=768"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/categories?post=768"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cjohnson.id.au\/wp-json\/wp\/v2\/tags?post=768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}