Checkers AI, anyone?

[kandieman101]

Has anyone here made a checkers AI? I am currently working on an AI for checkers for a school project, but it just seems overwhelming. Right now, the only AI I have is a random piece, and if it can make multiple moves... then a random spot out of those. Not really AI, anyways.

If anyone has made checkers AI and is willing to lend a helping hand, I'd appreciate it.

[Luke1]

I wont post code cause it can get long but i will give you some theory and you can go from there ...


- can the computer piece jump a player piece ?
1.) then jump the player

- find a random computer piece

1.) can the peice move diagonal left or right ?

2.) move piece, deleting its old position

3.) Player's turn

[kandieman101]

I have level 1 AI, which is just random piece... level 2 I am going to make it so that it either doesn't move into a jump, or at least protects itself (if possible).

The problem is, once I get to level 3 AI, I will have to "play ahead" like 3 turns, and determine the best piece to move, and the best spot. It all just seems very overwhelming.





BTW, rules of checkers is that if you CAN jump a piece, you MUST jump the piece. So the "can jump; jump" theory is already implemented.

[KingArthur]

try something like this

1. make a loop that checks all the AI's peaces
2. try simulate the moves it can do
3. if any pice can be eaten/the enemy can eat your pice simulate the move
4. if your pice will be eaten/any pice will eat yours simulate it(repeat until there aren't pices wich will be eaten)
5. give this move a score(you eated a pice, your pice was eaten the enemy got a king...)
6. next move
7.next pice

[kandieman101]

Hi KingArthur, thanks for the help... my teacher suggested recursion, and I understand recursion, I just can't apply it.

What if the CPU has all 12 pieces, and they can all move 2 spots... or maybe more if a king. How would I keep track of all this? Seems like a LOT.

[KingArthur]

I was thinking about something like this

const upleft=1,upright=2,downleft=3,downright=4
dim movesscore(NoOfPices) as byte
for i=0 to NoOfPices
  if pice(i).status=alive then
            createtmpGame
           if mustoverjump(pice(i)) then
           score=score+overjump(pice(I)) 'the numper of pices wich will be over jumped and simulates it
            'do some recursion here to check waht will happen after the overjump
      elseif canmove(pice(i),upleft) then
            tmpgame.pice(i).move upleft
            movesscore(i)=movescore(i)-NoOfpiceswichwillBeEaten  'returns the nomber of pices wich were overjumped(by the enemy)
       elseif ..... 'the same code for downright,downleft,upleft or just make it a loop I wrote it rather creepy
      end if
   end if
next 

well now that I wrote it I see it could be much better if you change this(I am to lazzy to write it all new):
1.make the loop in a main function and the checking in a recursive function(returns the move score)
2. the function keeps calling itself until it has simulated X moves or it cant move anymore
4. put that upleft,upright... in a loop
5. WTCH FOR ERRORS IN MY CODE I DIDN'T CHECK OR TEST IT

[kandieman101]

Thanks KingArthur, I will take a look at it. Unfortunately I am just leaving now...

BTW, you can use [Highlight=VB] instead of [PHP]

[alkatran]

Suggestion #1: Post this in Math forums

oh crap! buzzer, sorr,y cant say add point system (post above has that though)

[alkatran]

heh, free time.

Anyways.

First of all go through every piece checking how good it's next move would be, and for each one, have you level 2 ai move the other player (or even check every possible move and do the average... or mediant) then you then him.. and do pointage depending on how many pieces you can jump, he can jump and how much you progress towards his side.... if you really want to work, make some sort of formation checking algorythm which would give a score depending on how your menn are spread out.