public int negamax(..) { normal negamax.... return max; } }
This is another way which I found on google.
public getMove(boolean turn) { int eval=negmax(1) return bestmove. }
public int negamax(int depth) { int max=-INFINITY; if( test for win,boardful,reachd maxdepth...) return... else { genMoves(); (for all moves) make eval=-negmax(depth+1) unmake if(eval>max) { if(depth==1) { bestMove=current } max=eval } } return max; }
I don't remember from where I got this pseudo-code, but it beats the normal way I wrote, and I am unable to reason why it happens so. I am also not getting the logic of if(depth==1) { bestMove=current } What if the bestMove wasnt found on 1st ply, but this works and works better than normal getMove, I am missing something kindly help. Thank you.
I don't know what you mean by "works better". They should return the exact same move. The second way of writing the code tries to minimize code duplication. The `if (depth==1)' part simply says "if this is the root node, save the best move in a global variable so getMove can retrieve it".
I actually prefer your way of writing it, because there are more things I want to do only at the root (iterative deepening, time control, print out information about the state of the search...) and things I don't want to do at the root (look up the position in the hash, null move pruning...). Having a separate function doing the search at the root makes the code cleaner in the long run.
I had second thoughts on my gomoku program and so I decided to spend some time trying to make a connect-4(6x7) game. I think its lot simpler to make a good playing connect-4 than to a gomoku ai. My program is tough and hasnt lost single game when playing first. But it drew one. This fact is enough to say that its not perfect player.
Since its not a perfect ai, and one can win by force playing first, I think I have chance to learn to implement machine learning algorithms. Its my first encounter with this type of algorithm. By reading on various links on internet, I came to a conclusion that to apply machine learning on a theme, we need many samples of the same thing. So I think in this case it will be many thousands of games played. But now I dont know what is to be done with them.
One way I can do is, let program play one line at a time, if the program wins on that line, increment by one. If it loses, decrement by one. Now after playing several line, there would be varying scores. Second is weighing squares. But this wont help much. squares are of great values but different lines will have different values for squares.
So my basic question is how to apply machine learning algorithms in a correct way. To make the ai perfect player is the goal, but my primarary goal is to understand and implement machine learning. If I want to make a perfect ai, I can feed in openings by hand, but this is not how I think to do more over later on I want to apply this learning mechanism to other board games aswell. So connect-4 is just a test bench.
If you want to make a good connect 4 AI, learn to play connect 4 well. The best way is probably by reading James Allen's book. You may also enjoy John Tromp's page.
@Alvaro: I want to learn to implement machine learning for games and how to proceed with this. Particularly I don't want to make perfect connect-4, rather let my program learn to play good moves on its own and based on previous experiences. I want to learn this basic technique so that I can apply this to other board games as well.
I see. You can get a database of games from somewhere (for instance from games played by some early version of your program), extract positions from it that are tagged with the result of the game and then creating an evaluation function that fits the data is a supervised learning problem.
However, I am not a big fan of just throwing some machine learning machinery at a problem. Most of the time you'll do much better if you can define features that are relevant to the problem at hand. For instance, identifying odd and even threats and combining them correctly is critical to playing connect 4 well. No machine-learning algorithm is going to discover that. This phenomenon is not particular to connect 4: In my experience, every time you want to use machine learning for anything, you do much better if you first prepare the data with some domain-specific knowledge.
@Alvaro: Currently my program reaches upto 12 plys in 2 seconds(800kN/s) and it checks for odd-even threats and values them accordingly. It also operates on column preferences which is in evaluation and not in move order, so the next time the moves are lined up through their cut-offs. I find my program to be a ok, better than many of online free connect-4 ais, but on the same hand its not perfect.
I have included normal alpha-beta with killers and hash-tables. WIthout odd even threats my program almost scales 25 plys in 10 seconds, which I think is ok kindly share your view on this.
